Eli5: can someone explain to me the difference between what godels system and the Turing machine proved? Aren’t they both basically just proving that x can’t equal (x≠x)
In: Mathematics
I believe that by “Turing machine” you mean specifically the *undecidability of the halting problem*, as this is the closest thing to the Goedel’s Incompleteness Theorem that was proven by Turing using his machine model
What Turing has proven, is that you can’t create an algorithm that would take an arbitrary algorithm and figure out (in all cases) whether that algorithm *halts* (i. e. whether the program that implements this algorithm will ever finish its execution). For this he used a proof by contradiction. You don’t actually need Turing Machine for an intuitive grasp of this proof. Let’s assume that you *can* write a function `will_halt` that takes any code and checks whether some given code halts. Now let’s write a following code:
def g()
if will_halt(g): # Check the value of the function
while (true): # Create an endless loop
pass
else:
halt()
This is a contradition, because if the function `will_halt` returns True, the function will not halt. But we assumed that if the function `will_halt` returns true, the function halts.
Basically, both Goedel and Turing have proven, that in any consistent formal system there exist some claims that are not decidable. I. e. there are some sentences that we cannot decide whether they are true or false, when we operate in that system.
Latest Answers