A quick reference of the various Turing Machines. As of the Church-Turing Thesis, all computation models are equivalent to the standard Turing Machine. For a given problem, one variant might suit you more than others. As all these are equivalent, you can pick and choose what suits you best.

1) Infinite Tape: The tape extends indefinitely to the left and right of the input word. (Often considered the standard Turing Machine)

2) Semi-Infinite Tape: The input word lies at the left of the tape (aka its start). The tape extends indefinitely to the right of the word. (Also often considered the standard Turing Machine)

3) Stay-Option: The head can stay in its current position, instead of having to always move left or right.

4) Off-Line: The input word is written on a separate, read-only tape. At the initialization, the machine reads the input word from that tape and copies* it on the machine tape.
*using the tape alphabet, not the input alphabet

5) Multi-Tape: Instead of one tape, the machine utilizes multiple tapes, each with its own head.

6) Multi-Track: The tape can have multiple tracks, instead of just one. In a way, the tape can now hold multiple letters on each position.

7) Multi-Dimensional: Normally the tape is one-dimensional (a line). In this variation, it can be other spaces, like a 2D grid. In that case, the head can move not only left and right, but also up and down.

8) Non-Deterministic: In this case, the Turing Machine can use non-deterministic moves. For example, it can use λ-transitions (also known as ε-transitions). In general, it comes with anything you would expect from a non-deterministic automaton.

9) Multiple-Heads: A Turing Machine with one tape but multiple heads. At each transition, only one head can read and write.

10) Random Access Machine: A “special”, complex Turing Machine. In a nutshell, the modern computer.

Advertisements