Alan Turing

Meanwhile, over in Great Britain, the British mathematician Alan Turing wrote a paper in 1936 entitled On Computable Numbers in which he described a hypothetical device, a Turing machine, that presaged programmable computers. The Turing machine was designed to perform logical operations and could read, write, or erase symbols written on squares of an infinite paper tape. This kind of machine came to be known as a finite state machine because at each step in a computation, the machine's next action was matched against a finite instruction list of possible states.

The Turing machine pictured here above the paper tape, reads in the symbols from the tape one at a time. What we would like the machine to do is to give us an output of 1 anytime it has read at least 3 ones in a row off of the tape. When there are not at least three ones, then it should output a 0. The reading and outputting can go on infinitely. The diagram with the labelled states is known a state diagram and provides a visual path of the possible states that the machine can enter, dependent upon the input. The red arrowed lines indicate an input of 0 from the tape to the machine. The blue arrowed lines indicate an input of 1. Output from the machine is labelled in neon green.