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
Turing’s and Godel’s proofs are similar in many ways, but they differ in scope.
Turing proved that *computers* couldn’t generally demonstrate whether a given program would halt. But there are hypothetical systems more powerful than mere computers — for example, ‘oracles’ can solve problems that aren’t computable by definition. If they’re possible, Turing’s proof doesn’t apply to them.
Godel demonstrated that a certain result couldn’t be achieved under any conditions whatsoever. It’s a much broader scope.
Latest Answers