Are Turing's and Godel's theorems the same thing?

[epenguin]

Alan Turing was in the news just now. On 24 Dec. the Queen issued a pardon for him. (This is only formally the Queen, and not of her own initiative, it is an act of the government. The term 'Pardon' could be misunderstood and us legalistic/anachronistic, according to wiki it these days constitutes a recognition that a conviction was morally wrong.) I think the story is well known.

My question is: are Turing's Theorem and Godel's the same thing?

They sound like it to me. Godel's is about a 'formal system' which turns strings of symbols into other strings, a Turing machine just sounds like a way of realising such a thing. There would be some problems for which neither would ever get to the end. In fact wouldn't they be the same problems?

I've read articles and books about GT and Turing, remember a few concepts but never grasped them that well that I could give much of an account of the argument that gives the conclusions. If I wait till I can read them again this will have lost topicality.

 

[jgens]

Do you have specific theorems of Turing and Gödel in mind? I can guess that you are talking about the Incompleteness Theorems in reference to Gödel, but have no idea to which particular theorems of Turing you refer.

 

[epenguin]

It is called the halting problem and looking for that I found they are largely overlapping but Godel'is more general in a way I find puzzling and may come back to.http://en.wikipedia.org/wiki/Haltin...p_with_G.C3.B6del.27s_incompleteness_theorems

 

[AlephZero]

The halting problem is not the same as Godel's theorems.

Possibly all these results came from people thinking again about the old well known logical paradoxes about self-referential statements, e.g a piece of paper which says on one side "the statement on the other side is false", and on the other side "the statement on the other side is true", or the Biblical example of "a Cretan told me that all Cretans are liars". The first attempts to create a formal axiom system for all of mathematics hit this problem over the issue of whether a collection of sets was a set - but excluding self-contradictory "definitions" like "the set containing all sets which are not members of themselves".

Turing's halting theorem is a fairly simple application of the idea of the paradox: if there is an algorithm to test for halting, there is another algorithm that says "if the halting algorithm says this program halts, then loop for ever, and vice versa" - and then apply that algorithm to itself.

IMO Turing's most important contribution was in realizing there were issues to be addressed here at all - it is impossible to solve a problem that nobody has yet identified and formulated!

 

[atyy]

Both use an argument called diagonalization.

Also, there is apparently a proof of the Goedel-Rosser incompleteness theorem using Turing machines.
http://www.scottaaronson.com/blog/?p=710 , who adds a note that Makoto Kanazawa points to a similar proof in Kleene's 1967 textbook http://books.google.com/books?id=uV...onepage&q=Kleene "mathematical logic"&f=false .

 

[lugita15]

IMO Turing's most important contribution was in realizing there were issues to be addressed here at all - it is impossible to solve a problem that nobody has yet identified and formulated!

What are you talking about? People were trying to solve the "en.wikipedia.org/wiki/Entscheidungsproblem" before Turing.

 

[ppnl]

If there are programs whose halting status is undecidable then there are clearly undecidable mathematical propositions. After all asking if a program will halt is a math problem.

 

[jgens]

If there are programs whose halting status is undecidable then there are clearly undecidable mathematical propositions. After all asking if a program will halt is a math problem.

This is a slightly different notion of decidability, however, than that used in the incompleteness theorems. So while you may obtain a weak version of the incompleteness theorems using the halting problem you cannot get the full monty so to speak.

 

[lugita15]

If there are programs whose halting status is undecidable then there are clearly undecidable mathematical propositions. After all asking if a program will halt is a math problem.

Let me clarify something, in case you don't know it. Turing's theorem states that there's no computer program that can correctly decide which computer programs will halt and which ones won't halt. It does NOT say that there's a single program which no computer program can correctly decide the halting status of. That would be absurd, because for any program P, you can just write a program that outputs "P halts", and another program that outputs "P does not halt", and one of those programs is guaranteed to correctly decide whether P halts or not.

Similarly, Godel's theorem says that there is no formal system that can correctly decide which statements of number theory are true and which ones are false. It does not say that there's a single statement which no formal system can correctly decide the truth value of, which again would be absurd because for any statement S you can make a formal system whose sole axiom is "S", and another one whose sole axiom is "not S", and one of them will correctly decide the truth value of S.

I should mention that there's a well-defined sense in which a statement can, at least in principle, be "absolutely undecidable". Godel discusses this in his 1951 Gibbs lecture. See this paper and this paper. (Personally, I find the second paper more interesting than the first, so you may want to start there.)

 

[lugita15]

Attached in PDF format is the Godel Gibbs lecture I mentioned, if anyone's interested. (The actual lecture starts around page 17 of the PDF, before that it's just an introduction by George Boolos.)