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
It’s an idea of a machine that is as simple as possible, but still complex enough to meet the technical definition of a general purpose computer.
So then we can say things like if a machine can do everything a turning machine can do then it is a computer. And subsequently if a task can be done by a Turing machine then it can be done by any computer.
Having Turing machines be very simple makes it easy to prove that specific things are true or false about them. And then per the above statements those things must be true or false for all Turing equivalent computers.
The classic example is the “halting problem”. We can prove that it’s impossible to write a program for a Turing machine that can look at any other program and always correctly say whether or not that program will eventually finish.
Thus it’s impossible for any computer to do that, which is a very interesting conclusion.
Latest Answers