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

  • Thread starter epenguin
  • Start date
In summary: What are you talking about? 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
  • #1
epenguin
Homework Helper
Gold Member
3,636
1,009
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #4
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!
 
  • #6
AlephZero said:
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" [Broken] before Turing.
 
Last edited by a moderator:
  • #7
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.
 
  • #8
ppnl said:
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.
 
  • #9
ppnl said:
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.)
 
  • #10
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.)
 

Attachments

  • Godel Gibbs Lecture[smallpdf.com].pdf
    1.1 MB · Views: 555

1. What are Turing's and Godel's theorems?

Turing's and Godel's theorems are two important results in the field of mathematics and computer science. Turing's theorem, also known as the Halting problem, states that there is no algorithm that can determine whether a given computer program will eventually terminate or run forever. Godel's theorem, also known as the Incompleteness theorem, states that in any axiomatic system, there will always be true statements that cannot be proven within that system.

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

No, Turing's and Godel's theorems are not the same thing. While they both deal with the limitations of formal systems and computation, they address different aspects of these limitations. Turing's theorem deals with the undecidability of certain computational problems, while Godel's theorem deals with the incompleteness of formal systems.

3. How are Turing's and Godel's theorems related?

Turing's and Godel's theorems are related in the sense that they both show the limitations of formal systems and computation. Godel's theorem can be seen as a precursor to Turing's theorem, as it deals with the limitations of formal systems, which are also used in computation. However, they are distinct theorems with different proofs and implications.

4. What impact do Turing's and Godel's theorems have on the field of computer science?

Turing's and Godel's theorems have had a significant impact on the field of computer science. They have shown that there are inherent limitations in computation and formal systems, which has influenced the development of algorithms and programming languages. These theorems also have implications for artificial intelligence and the quest for a fully autonomous computer system.

5. Can Turing's and Godel's theorems be applied in other fields besides mathematics and computer science?

Yes, the concepts and limitations outlined in Turing's and Godel's theorems can be applied in other fields, such as philosophy and linguistics. For example, Godel's theorem has been used to argue for the existence of unprovable truths in other areas of study. Additionally, the concept of undecidability in Turing's theorem has been applied in areas such as biology and economics.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Programming and Computer Science
Replies
32
Views
3K
Replies
57
Views
12K
  • Art, Music, History, and Linguistics
Replies
1
Views
1K
  • Special and General Relativity
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
3K
  • Beyond the Standard Models
Replies
34
Views
13K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
7
Views
2K
Back
Top