The Turing Machine

turingm

In case you read about Alan Turing’s work on Turing Machines and the Halting Problem and asked yourself what a turing machine is and what it actually does, let me share my bit of research about this topic.

History

Alan Turing developed the Turing Machine concept in a paper in 1936 when he was 24 years old in order to show a unique and new way to compute problems and in this regard coined the term computer, referring to the human doing the actual computation.

The Turing Machine is not intended to be actually built, it is rather a hypothetical device to understand the limits of computation and even the inner workings of today’s computer processors.

Turing Machine - how does it work?

Now if a deterministic turing machine would be build, it would be an interesting piece of equipment. It would be a machine that uses a kind of a back and forth running paper tape where it reads and writes down a tape alphabet, called Γ (Gamma).

There is also a input alphabet Σ ⊆ Γ (Read: Sigma  is a subset of Gamma) which is pre-written on the tape. The input alphabet could be defined, e.g. as a set of binary string and empty spaces.

The machine’s interpreter now would read the 1s and 0s from the tape and decide according to a pre-defined decision-table what to do. In detail it would decide which state (Q) to change to internally and whether to move its read head left or right (L, R).

Transition Function

For the math whizzes among you, the formal mathematical definition of the transition function is

$$ \delta : Q \times \Gamma  → Q \times \Gamma \times {L, R} $$

This means, take the current state Q of the machine and the read symbol Γ of the tape and determine from this input values the next state Q, as well as the symbol to be written Γ onto tape and a movement direction L or R of the read head according to the table rules.

Possibilities of the Concept

Now try to imagine adding an additional symbol to the tape alphabet in order to cross off already read symbols. With this technique you could start comparing binary values with the Turing Machine. If you think about it, by altering or adding a few parameters, you could actually calculate any algorithm with such a machine. This is pretty astonishing; albeit being a rather tedious task to program the table.

Further Reading on the Turing Machine

Here are a few Web sites where you can watch a real-life Turing Machine, play around with an actual turing machine and watch a lecture about it from the University of California.

https://www.youtube.com/watch?v=E3keLeMwfHY
https://www.khanacademy.org/cs/multiplying-tm/1744636392
https://www.youtube.com/watch?v=eq2bvb8xE78