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 a simplified imaginary computer. Imagine
* An infinite tape consisting of cells which can store some data (numbers or letters or whatever).
* A “computing unit” which can read and write from one tape cell directly below it. This unit also stores a single datum which we call it’s state (also a number or letter or something, maybe a different kind than those on the tape).
That unit has a list of rules, looking like:
“If I am in state S, and the cell below me contains A, change my state to T, store B into the tape and move the tape one cell to the right/left”
You describe starting situation (computing unit’s state and what’s stored on the tape), then the machine chooses a possible rule from the list (the one which condition is fulfilled by current situation) and executes it. Then chooses another rule applicable to the new situation and executes it, and so on, and so on, until no rule is possible (may or may not actually stop). If it stops you can read the results of the computation from the tape (or the state).
It’s very different than how real computers work, but it’s much simpler to mathematically reason about Turing machines than computers. It also turns out that things that *can* be computed on Turing machine can also be computed on a real computer and vice versa (if you ignore the fact that in reality computers have finite memory and can’t be run for an infinitely long time).
In other words, Turing machine can implement any computation/algorithm.
For example, there are some problems which can’t be computed on *any* computer, even though the problem itself is stated correctly. Mathematical proof of that fact usually uses Turing machines in some way.
Latest Answers