Far too much of my time in recent years has been spent by an all consuming obsession to understand Turing’s original proof as outlined in “On Computable Numbers with an application to the Entscheidungsproblem”. Much like Alice in Wonderland in pre-teen years and Super Mario Bros. of teenage yore, I suspect there was very little value in spending time thusly. But there is light at the end of the tunnel and for some vague definition of “complete”, I call my study of Turing’s paper done for the time being.
If you are happy with reading other people’s description of the proof and don’t intend to inflict pain upon yourself or like to have a life, try Martin Davis or Charles Petzold. For the rest, I am outlining the list of topics that were useful in understanding the proof and beyond:
- A passing knowledge of German and weird Gothic Fonts 
- Diophantine Equations, Hilbert’s 10th Problem, Entscheidungsproblem
- Euclidean Geometry, Constructions and Euclidean Numbers
- Naive Set Theory, Cardinality of Infinite Sets, Continuum Hypothesis, Dedekind’s Theorem, Transfinite Numbers
- Type Theory, Russell’s Paradox
- ZF Set Theory, Axiom of Choice
- Cantor’s Diagonalization Argument, Godel Numbering
- Overview of the proofs of Kurt Godel, Alonzo Church, Stephen Kleene, Julia Robinson, Yuri Matiyasevich
- Integers, Reals, Irrationals, Transcendentals
- Crux of Turing’s Proof: Computable Numbers, Definable Numbers, Turing Machines, Circle Free Machines, Skeleton Tables, Enumerability of Computable Sequences, Description Number, Satisfactory Numbers, Standard Description and Universal Machines, Diagonalization applied to Description Numbers, Inability to construct Turing Machines for Circle-Free determination, Hilbert Functional Calculus a.k.a First-Order Logic and Automatic Theorem Proving using Turing Machines, Computable Functions, Universal Machine expressed via First-Order Logic, Equivalance of Propositional Provability and Circle-Free condition. Q.E.D.
Many of the above subjects require a lifetime’s devotion themselves and I was merely a tourist through that fascinating mathematical landscape. The initial part of the study was heavily dependent on Google, ArXiv and Wikipedia. But about a year ago, I moved to a country where Amazon.com delivers books and that made life much easier.
Much of the study overlaps with my next growing obsession, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”: Godel must be completed !
Filed under: Computer Science, Mathematics
Hi,
Received SIGSEGV at line 1