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.
Latest Answers