There are many references to it in public discussions, but trying to learn about it from Wikipedia is like reading in a new foreign language.
In: 283
A turing machine is a theoretical construct, with infinite memory, and a VERY limited set of instructions. Like 3 of em.
What is intersting about them is that they can (with infinite time) replicate all the instructions from any digital conputer. So if you can run a program, on any computer and get some result, that program can be translated into something that will run (generally MUCH MUCH SLOWER) and create the same output with the same functional intermediate steps (they wont necessatily look the same, as memory layout is different, but will be analogous.
So Alan Turing proves that anything that can be done by any computer, can eventually be done with this simple (theoretical : again, infinite memory– not lots of finite memory, infinite memory) machine.
So if something is “Turing complete” it can be shown to be able to (eventually, given infinite time) compute anything that any other turing complete machine/system can compute (not talking about efficiency here. Just possibility. Some arrangements are clearly much more efficient for some tasks, than others).
With those things proven, he then shows that there are programs where it is indeterminite if they will complete or if they will enter an infinite loop. So there are systemsnand processes that, even with infinite reaources, and infinite time. Aka there exist “unsolveable” problems.
Major interssting upshots:
All computing systems (cause almost all have instructions that map turing complete instructions) are essentially equivalent (forgetting the infinite memory/time requirement).
Certain well formed questions are unanswerable.
Latest Answers