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
This is actually a pretty big question. I’ll address Godel’s theorem in this comment.
Godel’s incompleteness theorems are twofold, and they discuss a sype of systems sometimes called “proof systems”, or “axiom systems”. A proof system is pretty much what it sounds like; a system in which you can use some statements to prove other statements. A proof system has a set of rules (we call them “rules of inference”) which tell you how you’re allowed to interpret and manipulate “if/then/or else” type logic statements. Like for example, your proof system might have a rule that says:
If you know ‘either A is true or B is true’;
and if you know ‘B is false’;
then you can conclude ‘A is true’.
Mathematicians have been playing with systems like this for a long time, trying to understand how different rule-sets can allow some things to be proven but not others.
What Godel showed, is that for absolutely any proof system you could ever devise, at least one of these two things must be true:
1 : The proof system contains “contradictions”, which means it’s possible to prove both “A is true” AND “A is false.”
or, 2 : The proof system contains “undecidable statements”, which means there are some statements which can’t be proven either true OR false.
If a proof system contains contradictions, we say the system is “inconsistent”. An inconsistent system is not very useful because it means you can’t know, just because you proved a statement in this system, that it’s actually true.
If a proof system contains undecidable statements, we say the system is “incomplete”. This doesn’t make the system useless, but we would *like* to be able prove stuff if it’s true. If a system is incomplete, then that means there are some truths, which this system simply cannot “reach”.
Godel’s first theorem says that if a system is consistent, then it must be incomplete. And if it’s complete, then it must be inconsistent. This was disappointing news for the mathematicians who were hoping that, if they just came up with the right proof system, they could use it to prove absolutely any true statement in number theory.
And his second theorem says that if a system is consistent, then the statement “this system is consistent,” if you translate it into the language of that system, *must be* one of those undecidable statements. In other words, no consistent system can ever prove its own consistency. One system can prove another system’s consistency, but then if you want to prove *the first* system consistent too, you’ll need yet another system, and so on.
Latest Answers