Turing Machines for Dummies

How is a Turing Machine different from a “regular” Computer

You have at some point have been introduced to Turing Machines as the first theoretical description of a computer. However if you were like me, when first introduced to a Turing machine the explanation did not make a lot of sense.

Practical Example of a Turing Machine

One way to get an initial impression of what an actual Turing machine would look like, is to look at this wooden mechanical Turing machine.

The Tape

Thus Turing’s explanation that his machine would read data from a tape made sense in his time. In the video, the tape is represented as a belt with wooden pegs on. In a theoretical Turing machine each cell on the tape could contain any symbol belonging to some predefined alphabet.

Machine Alphabet

“Predefined alphabet?” What a kind of gobbledygook is this? This is to account for the fact that theoretically speaking the machine can have many different ways of representing data. E.g. the computer you normally work with works with 1s and 0s. So the alphabet is just 0 and 1. An alphabet in this context just means a set of symbols. Every cell on the tape has to be a letter from this alphabet.

Reading and Moving the Tape

If you watch the video you can see that there is a head reading the tape, by checking where the wooden pegs are placed. Depending on what the Turing Machine reads it can move left or right on the tape.

Comparison with a von Neumann Machine

In a von Neumann machine you got a program stored in random access memory. The CPU in the computer reads on instruction from memory and executes it. An instruction could be things like:

  1. Add bytes in register 3 and 4 as if they where integer numbers, and store result in register 3.
  2. Write 2 bytes in register 5 inside the CPU to memory location 6.
  3. Multiply two numbers in two different registers, alternatively subtract or divide.
  4. Change program counter (jump) to start executing code at some different location in memory.
  5. Conditional jump. Jump to a particular instruction in memory depending on the result of previous calculation.

Reading and Writing Data

The tape is where you read and write data. It is not where you get the program instructions. And it is not random access memory. In a von Neumann machine, you can say write this number to memory at location 4. In a Turing machine you can only write to the current position. There are no other choices.

Executing a Program

In a von Neumann machine the program lay in memory in as a collection of instructions which are read in sequence. The program in a Turing machine is not like that. It is not read one instruction at a time. It is not organized as a sequence of instructions.

  • 0/1,L arrow going from B to A.

How Does it Do Arithmetic?

You have probably noticed that no specific instructions such as add, subtract, multiply etc is defined on a Turing Machine. A Turing machine is far more generic than that.

Subtraction Example

Here is an example of a Turing Machine just made for subtraction.

The state transitions are written such that what is on the left side of / is what you have read on the tape. The right side are the actions to perform. 1/0,R. Mean you read a 1. Then you write a 0 and more Right.
A  →111c1111  1/0,R
A  →111c1111  1/0,R
B 0→11c1111 1/1,R
B 01→1c1111 1/1,R
B 011→c1111 c/c,R
C 011c→1111 1/0,L
D 011→c0111 c/c,L
E 01→1c0111 1/1,L
E 0→11c0111 1/1,L
E →011c0111 0/0,R
A 0→11c0111 1/0,R
B 00→1c0111 1/1,R
B 000→c0111 c/c,R
C 000c→0111 0/0,R
C 000c0→111 1/0,L
D 000c→0011 0/0,L

Summary

I am trying to structure this summary around my previous misconceptions about Turing machines which others hopefully can relate to.

  1. Input data comes from the tape. However this is also where the Turing machine writes its output.
  2. No the Turing machine is not a binary computer. It can operate on any number of symbols, not just 0 and 1. You define which symbols are allowed by defining its alphabet.

Geek dad, living in Oslo, Norway with passion for UX, Julia programming, science, teaching, reading and writing.