Misplaced Pages

This is an old revision of this page, as edited by Likebox (talk | contribs) at 20:25, 6 November 2007 (→Computational Proof). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Welcome!

Hello, Likebox, and welcome to Misplaced Pages! Thank you for your contributions. I hope you like the place and decide to stay. Here are some pages that you might find helpful:

• The five pillars of Misplaced Pages
• How to edit a page
• Help pages
• Tutorial
• How to write a great article
• Manual of Style

I hope you enjoy editing here and being a Wikipedian! Please sign your name on talk pages using four tildes (~~~~); this will automatically produce your name and the date. If you need help, check out Misplaced Pages:Questions, ask me on my talk page, or ask your question and then place {{helpme}} before the question on your talk page. Again, welcome! 

TheRingess (talk) 02:52, 31 August 2007 (UTC)

Archimedes Plutonium

The Archimedes Plutonium article has been a magnet for unverifiable biographical information and I have never seen evidence that "Archimedes Plutonium" is a topic worthy of a Misplaced Pages article. I think everything that need be said can be said in one or two sentences at Notable Usenet personalities. --JWSchmidt 17:07, 17 October 2007 (UTC)

My advice is that you start a list of published works at Talk:Archimedes Plutonium that assert the importance of "Archimedes Plutonium". If you can list a bunch of good sources then you will be able to make a good article. Until then, the short blurb at Notable Usenet personalities seems adequate. --JWSchmidt 19:19, 17 October 2007 (UTC)

"And my advice is that you find out if your opinion is a majority opinion before imposing it on everybody else" <-- Thanks, but I must ignore your advice. Wikipedians do not have to determine a majority opinion before acting to improve the encyclopedia. --JWSchmidt 19:54, 17 October 2007 (UTC)

Misplaced Pages does not run popularity contests. In my view, the decision of who to have biographical articles for should be based on the existence of a large and reputable body of published literature about the subjects of such articles. Without a serious biographical literature outside of Misplaced Pages, Misplaced Pages editors have no real basis upon which to create biographical articles. Sure, you can read usenet posts and blogs and various unverifiable websites and then write about the people who make usenet posts, but that is original research. If you can construct a list of reliable published sources that explain the importance of "Archimedes Plutonium", then you have a chance of having an article. Based on the reliable sources I have seen, the short blurb Notable Usenet personalities seems adequate. --JWSchmidt 20:16, 17 October 2007 (UTC)

"You can't impose your opinion on others" <-- Administrators are called upon to look at the evidence and make decisions about the deletion of pages. It is not uncommon for the majority of people who are personally interested in particular pages to be in favor of keeping those pages. However, if the reliable sources that are needed to support a Misplaced Pages article do not exist, it is the duty of administrators to delete the articles. Its not really that hard to count reliable sources and decide if an article should be deleted due to it having too few sources of reliable information. As far as I can tell, there are too few reliable sources about "Archimedes Plutonium" to support an article. If you can construct a reasonably long list of good sources then you will be able to justify having an article. --JWSchmidt 20:47, 17 October 2007 (UTC)

AP

I don't know anything about his views on Jesus, but that sort of crankery is less interesting to me anyway. As far as the murder goes: no one has even hinted that AP was guilty of a crime there. Arthur's only beef was that we cannot say he was utterly uninvolved unless there is a source saying so. If there's only one police source saying something less broad, then we need to report what was said, and not our interpretation of it. Phiwum 13:24, 20 October 2007 (UTC)

I stick to my summary. If we are going to say something about the case, it has to be verifiable. If we say something broader than published accounts report, then we have violated WP policy regarding verifiability. Your characterization of the issue as an "attack" against AP is uncharitable at best and, I would say, dishonest (given the fact that you have read the rationale for Arthur's edits).

I know you feel defensive towards AP and this article, but you really shouldn't sling such allegations regarding other editors about like that. Phiwum 22:51, 22 October 2007 (UTC)

You know, until this little dispute, I didn't even know that Arthur Rubin was an administrator. Even so, I don't see him as particularly powerful or prone to throwing his weight around, either in this case or another. In fact, by and large, I regarded his edits as well-motivated.

So, sorry, I don't see that I'm quite on your side on this issue. But that's okay, since I'm just a peon around here anyway.

As an aside, I do find it curious that you are so taken by AP's crankery. It really doesn't seem anything special to me. You made a lot of claims on the talk page that I sincerely doubt you could not back up, especially that AP's still-evolving theory is somehow equiconsistent with more traditional theories. But, hey, everyone needs a crankish diversion. You can have AP and I will be forever a James S. Harris devotee (though, perhaps with less respect than you show for AP).

Anyway, best of luck to you and I hope that you won't leave WP over editorial differences. You've shown a willingness to put in some effort and that's important. Phiwum 00:16, 24 October 2007 (UTC)

Archimedes Plutonium history undelete

No, I won't undelete the history per our policy on undeletion. All administrators can see all deleted revisions from June 2004 onwards so I don't see a need to undelete it either. I see that you've brought this up on deletion review - just wait for a response there. Graham87 01:02, 23 October 2007 (UTC)

The diff links don't even work for admins - they can check the diffs manually. Graham87 01:10, 23 October 2007 (UTC)

Articles

I am very happy to work towards compromise wording on these articles. I rewrote the section on Godel's theorem, but it's still the same idea - if there was an effective, complete, ω-consistent theory then the halting problem would be decidable. On the Halting problem page, I don't mind having what you call "computer science" terminology - I spent a long time trying to integrate your terminology into the other section. What I will argue against is: nonstandard terminology and excessive handwaving. But I can compromise on some handwaving. — Carl (CBM · talk) 03:59, 2 November 2007 (UTC)

Hello from me, Godel, and Archimedes P

I am still interested in the proof you provided on GIT. I believe it has a magic ability : one can sit down with a 21st century person, sketch the proof on a cocktail napkin (ok, both sides.) That person can then take the napkin, wander off and scratch his head for three days, and return to say "now i see."

To me, that is no small thing.

I don't know if consensus at the Misplaced Pages GIT article will accept it. Non-standard material has a rough time in the Talk pages in this and other topics (an inclination i disagree with.)

Whatever happens at the article, I should like to take this section and resurrect it elsewhere. There is, for example, the wikimedia project and others which tend to be more 'inclusionist'. There are other options as well.

I think with some minor corrections in terminology, and a few lines of explanation here and there, it can be made agreeable to even the most incredulous. I shd like to step thru it, line at a time, and ensure there are no gaps or subtle errors. I'll start up an off-site wiki and get this going. Wd you like to co-author it w/ me (which of course, you have already done by providing the original text)? CeilingCrash 17:43, 2 November 2007 (UTC)

I assure you I am a real person. What I dislike about your rewrites is that they use nonstandard language and vague arguments. There is a reason that recursion theory uses the terminology that it does, and this standard recursion theory language is understood both by computer scientists and mathematicians. — Carl (CBM · talk) 21:21, 5 November 2007 (UTC)

Edit warring

Please know that simply reverting edits, rather than attempting to reach compromise, may be considered edit warring, and is strongly discouraged. On a short-term basis, the WP:3RR three revert rule prohibits reverting more than three times within 24 hours. The edit warring policy prohibits slower edit wars as well. Rather than just reverting, and risking being blocked from editing as a result, I encourage you to work towards some compromise language. We have been discussing things on several talk pages; there is no need to revert the content pages as well. — Carl (CBM · talk) 01:14, 6 November 2007 (UTC)

Likebox (block log • active blocks • global blocks • contribs • deleted contribs • filter log • creation log • change block settings • unblock • checkuser (log))

Request reason:

there is no edit warring. The reverts were always below 3RR and not particularly incendiary.

Decline reason:

As it says on WP:3RR, you are not entitled to three reverts a day. You were warned against edit warring, but decided to persist. Your block will expire in 24 hours, so in the meantime I suggest you decide how you're going to discuss your editing on the talk page.— Haemo 19:53, 6 November 2007 (UTC)

If you want to make any further unblock requests, please read the guide to appealing blocks first, then use the {{unblock}} template again. If you make too many unconvincing or disruptive unblock requests, you may be prevented from editing this page until your block has expired. Do not remove this unblock review while you are blocked.

Please don't revert war. I've blocked you for 24 hours so you can cool down a bit. —Ruud 07:10, 6 November 2007 (UTC)

There has been no revert war. I have reverted fewer than three times, and the reverts were all justified. Please familiarize yourself with the issues at hand before blocking. I have acted responsibly.Likebox 18:27, 6 November 2007 (UTC)

"Stealing credit"

You said:

Finally, this proof has the gall to pretend that Kleene et al. and alls y'all actually understood the relation between halting and Godel's theorem before you read the proof that I wrote. While, in hindsight, after a few weeks of bickering, it is clear to all you folks that quining and the fixed-point theorem are identical, that Godel and Halting are identical, none of you knew exactly how before I told you. If your going to use my insights, use my language and cite the paper I cited. The only reason this is not original research is because some dude wrote a paper in 1981, and because of the reference provided. To pretend that this proof is somehow implicit in the standard presentations is a credit-stealing lie. It was precisely because the standard presentations are so god-awful that I had to go to great lengths to come up with this one.

The relationship between Goedel's theorem and undecidable problems is extremely well known; your claim that your proof concept is somehow new comes across as a rant rather than as a clear argument. The edit warning explicitly warns yo that people will edit your text "mercilessly"; if you don't like that, Misplaced Pages is not the place for you.

I don't care if people edit the stuff, so long as they get it right. That means, the proof should stay clear, and the proof should stay correct. The edits that you have given are murky and incorrect.Likebox 18:29, 6 November 2007 (UTC)

As to credit, your theorem was stated at least as early as 1943 by Kleene in "Recursive predicates and quantifiers". Theorem VIII states:

"There is no complete formal deductive theory for the predicate ${\displaystyle (x){\bar {T}}_{1}(a,a,x)}$."

As the T is Kleene's T predicate, this is exactly a statement about the halting problem. Kleene explicitly says: "This is the famous theorem of Gödel on formally undecidable propositions, in a generalized form." So there is really nothing from the 1970s or 1980s in your proof, just classical recursion theory. — Carl (CBM · talk) 12:46, 6 November 2007 (UTC)

Absolutely true, logically. Not true in terms of exposition. I agree that logically all this is due to Kleene, and I give him proper credit. I do not agree that the exposition is due to Kleene, and the exposition is important. If you don't think exposition matters, why do you keep reverting the exposition I gave to an exposition that is less precise?Likebox 18:29, 6 November 2007 (UTC)

Several different people have reverted your exposition, and I agree with them, because the exposition itself is what needs improvement. I have no disagreement with the ideas being included in the articles, but the exposition needs to be encyclopedic, match the rest of the article, and use standard terminology. I am confident we can find some compromise wording; but the wording you keep reverting to isn't it. — Carl (CBM · talk) 19:17, 6 November 2007 (UTC)

In case you haven't noticed, I don't think that we will ever come to any sort of agreement. You feel the need to put in what you think is "standard terminology", whatever that means, and I am duty-bound to write a clear proof. Since it is in fact exactly the twaddle that you call "standard terminology" which makes the proof obscure, there is no point in any further discussion. I put my version in my talk page, for other people to read and make up their own minds.

The proof I gave is a very beautiful one. The only effect of your deletions is to make you look incompetent. I guarantee you that more people will learn GIT from this talk page than from your "rewrite".Likebox 20:09, 6 November 2007 (UTC)

The entire system at Misplaced Pages is founded on compromise. If you want to participate here you will need to work to build consensus for your preferred exposition, since it is clear that multiple people disagree with the way you have presented your ideas in the articles. Just declaring your intention to edit war or encouraging others to do so (as below) gives the appearance of bad faith.

Misplaced Pages is not the place to right the wrongs of the world, and that includes the wrongs you feel are perpetuated by the standard terminology of recursion theory. I hope you will stop edit warring and instead try to find some areas of agreement with other editors. This same sentiment has been expressed by Haemo and by Ruud Koot on this page. — Carl (CBM · talk) 20:20, 6 November 2007 (UTC)

I Am Annoyed By This Blocking

This is unreasonable--- the disagreements are over content, and are a perfectly legitemate dispute. There are people on both sides. The reverts have been under 3RR, and they have not been reviewed by anybody. The disputed section in the form as I've inserted it yesterday was rewritten to incorporate suggestions of CBM, and this text requires a proper review. It was not a blind revert, and incorporated suggestions and criticisms.

The person who started all this deletion madness is "ceilingcrash", who changed his mind.Likebox 18:43, 6 November 2007 (UTC)

Godel's Incompletness Theorem--- My Favorite Way

I copied and pasted this section from Godel's Incompleteness theorems. It is the shortest self-contained complete proof in existence! I am very proud of it. There are two editors who keep reverting the proof off the page, so I invite other people with time on their hands to revert back. Since I am obviously not welcome on GIT, and since I have lost all respect for the active editors there, I will just keep this section in my talk page. Copy and paste it into Godel's incompleteness theorems if you like!

I also put it here so that people can read it, because it's better than the whole rest of the page. Its useful if you want to actually learn the proof of the theorem without slogging through the brain-damaged crap in recursion theory textbooks.

Notes

The idea of this proof is originally due to Kleene, who noted in 1943 that Turing's undecidability proof and Godel's proof are closely related. This was appreciated by Godel and Turing, although they did not bother to make the connection explicit. The technical exposition of Kleene's proof, however, was hampered by the primitive state of computer languages at the time he wrote. This is not at all Kleene's fault, since he was writing well before computers were common. The notion of quining was not yet standard, and so he needed to construct his own substitute. The notion of algorithm was also not as central as it is today, so the philosophy is unappealing to a modern reader.

Nonetheless, Kleene (along with Godel and Turing) deserves full credit for the logical ideas in the proof. The exposition is a different matter, since expositions can continue to evolve long after the ideas are settled down.

The first exposition which gives a proof of this kind (as far as I know) is by Arthur Charlesworth in 1981, cited below. Current recursion theorists like to pretend that their language is somehow good enough to capture the spirit of this proof, but this is just their way of defending their pompous obscurity. Although I can read their papers and follow their methods nowadays, it took me many years of struggle, and I would not wish that kind of mental torture on anybody, let alone a student.

I give you my word--- there is not a single shred of insight to be gained from learning any recursion theory. All the arguments in the recursion theory literature are made completely obvious when re-expressed as computer programs in a modern language.

Recursion theory language is not sufficiently rich to be able to discuss quining well, and requires a series of odious lemmas to establish the existence of quines. This is the "recursion theorem" and the "fixed point theorem" of Kleene. This theorem states, in a cleverly encrypted way, that any computer program can be rewritten to first print its code, then do whatever else its going to do. Duh.

The exposition in most textbooks of Godel's theorem similarly encrypts the entire proof. The encryption key is jealously guarded by officious people who struggled to learn it and were too stupid to come up with a better proof on their own. Thankfully they are few in number, and most of them are old. They will probably die well before I do.

The exposition below is original, but follows the ideas of the 1981 paper by Charlesworth, based on Kleene's ideas, and a more recent preprint which reviews the argument as an aside. It's old wine in a new bottle.

Enjoy!

Computational Proof

Godel proved that there is an explicit algorithm to find all the consequences of a set of axioms. This algorithm can, in modern language, be represented as a computer program running on an idealized infinite memory computer using an infinite-integer modification of the C programming language. Using the modern notions of computability, it is then easy to prove Godel's incompleteness theorem from basic ideas in computer science.

1. The Quine lemma-- any computer program can include a subroutine that prints out the entire program's code. This allows any program to write itself into a string variable, or a large enough bigint.

2. The Halting problem: There does not exist a computer program PREDICT(P) which takes the code to program P and predicts whether P eventually halts.

proof: Write program SPITE, which prints itself into variable R, then calculates PREDICT(R). If the answer is R halts, Spite goes into an infinite loop. If the answer is R does not halt, SPITE halts. Since R is really SPITE in disguise, no matter what PREDICT says, the answer is wrong.

The incompleteness theorem: Suppose that an axiom system describes integers (or any other discrete structure), and that it has enough operations (addition and multiplication are sufficient) to describe the working of a computer. This means that the axioms will eventually prove all theorems of the form "Starting with memory contents X, after N steps of running, the memory of the computer will be Y", for any fixed integers X and N, and can state propositions of the form "For all N, the contents of the memory will have property P", where P is some fixed definite property, like "The first bit in memory is zero" or "the tenth bit is different then the third bit".

Such an axiom system is either inconsistent or incomplete.

proof: Write DEDUCE. DEDUCE first prints its own code into the variable R, then it deduces all consequences of the axiom system. It searches for the theorem R never halts. Only if DEDUCE finds this theorem does it halt.

If the axiom system proves that DEDUCE doesn't halt, it is inconsistent, because DEDUCE then halts, and the axioms will follow its operation until it halts and prove that it halts. So if the system is consistent, DEDUCE doesn't halt and the axioms cannot prove it.

This argument doesn't explicitly demonstrate the incompleteness, because a consistent axiom system could still prove the ${\displaystyle \omega }$-inconsistent theorem that DEDUCE halts (even though it doesn't) without contradiction.

So write ROSSER: ROSSER prints its code into R, and searches deductions for either 1. R prints something out or 2. R never prints anything out. If it finds 1, it halts without printing anything. If it finds 2, It prints "Hello World!" to the screen and halts.

If the axiom system is consistent, it cannot prove either ROSSER eventually prints something nor the negation ROSSER does not print anything. So whatever its conclusions about DEDUCE, the axiom system is incomplete.

To prove the second incompleteness theorem, note that if the axioms are consistent, it is easy to prove that DEDUCE does not halt. This means that if a consistent axiom system proves its own consistency then it will also prove that DEDUCE does not halt, which is impossible..

References

1. Arthur Charlesworth (1981). "A Proof of Godel's Theorem in Terms of Computer Programs". Mathematics Magazine. 54 No. 3: 109–121.
2. R. Maimon "The Computational Theory of Biological Function I", arXiv:q-bio/0503028