News for hackers. Stuff that matters.
Re:How Dr. Seuss would prove the halting problem undecidable by ryanjmo on Wednesday May 05, 2010 @02:34PM (#1322072)
This somehow seems easier to follow than a formal proof (even though it is actually a formal proof). Fun times!
Re:How Dr. Seuss would prove the halting problem undecidable by realrbman on Wednesday May 05, 2010 @02:52PM (#1322130)
I wish my professor gave us this in my CS Theory course. Would have made it ten times as much fun, and much less dry.
Re:How Dr. Seuss would prove the halting problem undecidable by pw0ncakes on Wednesday May 05, 2010 @02:53PM (#1322136)
It's a proof, but not a formal one. It doesn't define the notion of "program", for example. It's somewhere between an informal proof and a proof sketch (a correct and valid one, of course).

A formal proof is a sequence of statements where each is either an axiom or derived from previous ones via a set of derivation rules, and wherein assessing the validity of each axiom statement or derivation can be done "typographically" (mechanically and primitive-recursively). It's nigh-impossible to write a human-readable formal proof of anything interesting; the vast majority of mathematical papers published are informal proofs.

(Of course, this diversion doesn't detract from the matter of this proof-poem being very cool.)

Re:How Dr. Seuss would prove the halting problem undecidable by ryanjmo on Wednesday May 05, 2010 @03:55PM (#1322328)
Yes I am sorry, I believe I ment "it is in some ways a formal proof." It is indeed a proof sketch. With a preliminary section defining things more rigorously, I do believe that this is publishable in most of the Cryptography conferences I have published in.
Re:How Dr. Seuss would prove the halting problem undecidable by alain94040 on Wednesday May 05, 2010 @08:42PM (#1323165)
With a preliminary section defining things more rigorously I do believe that this is publishable in a conference on Cryptography

[trying to get the rhyme going for you]

Re:How Dr. Seuss would prove the halting problem undecidable by kaddar on Wednesday May 05, 2010 @05:26PM (#1322639)
Actually, that gives me a sort of unique idea: An online, wikipedia like proof database with understandable informal proofs with click-to-expand (inline) annotated sections, if you click them, they would expand into proof of less formal claims.

The idea would be that we generally share understanding of obvious axioms (and thus, allow them to be request-able assumptions), and so can enhance readability.

Re:How Dr. Seuss would prove the halting problem undecidable by chbarts on Wednesday May 05, 2010 @06:04PM (#1322744)
http://us.metamath.org/

Do you know about Metamath yet? It's something similar to what you want, but it's all in a single program as opposed to being web-based.