In celebration of Alan Turing's birthday, Google published a doodle showing a machine. What kind of machine is the doodle? Can it express a Turing Complete language?
There are obvious differences to the classical turing machine: a finite tape, constraints in how state can be connected,...
The doodle is still be available here
(The display on the top right shows the expected output.)
The tape in the middle is divided into squares that can hold a blank, a zero or a one. The head is positioned above one of the squares and is used for reading and writing.
Below the tape you can see a green arrow which you can click on to start the machine. There are two lines of circles next to it, some of which are connected. I will call them "states".
After the machine starts, the first state to the right of the green button lights up, then the next one to the right, and so on... Each state contains one of the following commands:
- blank = do nothing (just move to the next state)
- 1 = write a one to the tape at the current position of the head
- 0 = write a zero to the tape at the current position of the head
- arrow to the left = move the head one step to the left
- arrow to the right = move the head one step to the right
- condition: if the value under the head is equal to the value shown in the square go down to the second line of states. if not, move to the next state to the right
- left jump: return to a (fixed) previous state but only on the upper row [I originally forgot that one, thanks @Marzio!]
There is no way to "overlap" two jumps (one over another). The machine stops when there it leaves a state and there is no next state to the right of it.
(After the machine stops the contents of the tape are compared to the contents of the display, but I don't consider that to be part of the intended functionality of the machine.)