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
One is a model of computation, the other is a theorem about what is provable within a system. Perhaps a bit more detail about what *you* understand about these models would help.
A Turing machine is just a simple model of a computer that can perform any arbitrary computer algorithm. That is, it can do enough different things with the data in its memory that it is able to do whatever sort of moving, adding, or removing of things in memory that you want (if you give it enough instructions!).
This is handy, because the simplicity of the model means it is easier to mathematically prove what it can and cannot do – and since a Turing machine model is able to do any algorithm, those proofs apply to *any* computer.
Godel’s incompleteness theorem is not a model of a computer, they are theorems (proven statements) about what you can prove from a set of axioms. Basically, it says that we can’t have a single group of axioms (premises or assumptions) that would allow us to prove everything 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.
x is always equal to x by definition of “equal”.
Turing machines are theoretical models of computers. Everything a normal computer can do can be done with a Turing machine and vice versa (if we have enough storage), but Turing machines are pretty simple in their design so they are often easier to analyze. You can use a Turing machine to prove various statements (e.g. “4 is even”), just like you can do it with a normal computer.
Are you asking about Gödel’s incompleteness theorems? They say (roughly) that not all true statements have a proof.
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.
My first attempt eli5ing so here goes
So before godel the hypothesis was that
The universe is made up of well defined rules and once you enumerate the rules you can automate them to be performed by machines and that these machines can perform the tasks as good as humans.
Turing’s hypothesis lays down the tenets for what makes a machine indistinguishable from a human.
Godel’s incompletenes theorem disproves that everything can be enumerated.
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