Turing machines

The Turing machine is a thought experiment proposed by Alan Turing in 1936. Imagine an infinitely long tape. Each cell of the tape can hold 1 or 0. A machine is currently scanning a cell. Depending partly on the number on the cell, the Turing machine can do many things. It can change its internal state, which determines its behaviour when scanning a cell. It can flip the symbol it scans from 0 to 1 or vice versa. It can move to the cell on the left of the current cell or the cell on the right. It can do two or even three of these things at a time. Finally, it can stop entirely. These machines seem simple but Turing proved that they can, like S and K combinators, do anything your PC or supercomputer can. Here is an example Turing machine with 3 states:

State 1: If you scan 0, flip it to 1, switch to state 2, and move right. Else, switch to state 3 and move left.

State 2: If you scan 0, flip it to 1, switch to state 1, and move left. Else, move right.

State 3: If you scan 0, flip it to 1, switch to state 2, and move left. Else, stop.

Here I will use [ ] to denote the machine. It starts like ...00000[0]00000... in state 1. It then goes to ...000001[0]0000... and then 00000[1]10000... Now it goes to state 3 with ...0000[0]110000... It eventually reaches ...00111[1]11000... in state 3, after which it stops. For 3-state machines that eventually halt, this takes the longest time to halt, taking 21 steps.

How do we know whether a Turing machine will ever halt? We can simulate it for long enough. If it halts, good. If not, it might halt or it might not. But can a Turing machine (or a computer) tell whether another Turing machine halts? Turing proved that the answer is no. The only way to prove whether it halts is for a human to examine it on a case-by-case basis. This may be extremely diffcult at times but it is sometimes very easy for humans (but impossible for computers). An example is a Turing machine that moves left if it scans 0 and halts otherwise. This Turing machine will, on a tape with only 0s, go left forever and never halt. A human could prove that. Many other simple Turing machines can be proven not to halt. However, a computer could never prove it in the general case.

Turing machines come in various forms. Your PC can simulate a Turing machine. S and K combinators (from combinatory logic) can simulate a Turing machine. Conway's Life can simulate a Turing machine. Ian Stewart proposed an innovative scenario where a model train set can simulate a Turing machine (and, therefore, your PC, S and K combinators, and Conway's Life). However, these things may be extremely slow and would lack all input and output except the initial configuration as input and the final position as output. Your PC is much faster and more user-friendly than a Turing machine.However, any calculation or program your PC can run, all of the others can too and get the right result.

Related entries