What type of automaton is Google's Turing Doodle?

Question

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.)

Answer 1

Assuming that:

• we can add an arbitrarily large number of rows ("status lines")
• the rows can be arbitrarily long
• the tape is infinite

I tried to build an Alan Turing's Doodle machine configuration that emulates the machine $M_4$ described in "Small Turing Machines and generalized busy beaver competition" that has a halting problem that depends on an open (up to my knowledge) Collatz-like problem. The full picture is available here.

... so even if the A.T.'s Doodle is perhaps not Turing complete (due to the non-overlapping left-only jump operator available only in the first row), it is powerful enough to walk the fine line of (un)decidability :-D

EDIT: TURING DOODLE IS TURING COMPLETE

(I leave the previous answer above, because I'm not sure that this part is correct :-)

I think that even with a single left non-overlapping jump the Turing Doodle is Turing complete!. The (simple) idea is to use the tape itself to store the current state and use multiple cells to represent a larger alphabet.

For example a 2 states 8 symbols TM can be simulated using the following tape representation:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

The Turing doodle can:

1. read $s$ and branch to one of the two different horizontal areas representing STATE A and STATE B;
2. read $b2, b1, b0$ and branch to a row representing one of the eight symbols;
3. write the next symbol, move the head to the "macro cell" on the left or right, and store on it the next state; in the figure below these operations (that can be done on a sequence of cells using the actions move left/right and write) are called "MW";
4. finally transfer the control to the upper row that with a single left jump will bring the control back to step 1.

The full picture is available here.

In the same manner, given a $TM$ with an arbitrary number of states and alphabet symbols we can build an equivalent Turing Doodle machine $DM$.

Answer 2

The machine is supplied with a “tape”, (the analogue of paper) running through it, and divided into sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square the “scanned square”. The symbol on the scanned square may be called the “scanned symbol”. The “scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However, by altering its m-configuration the machine can effectively remember some of the symbols which it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qn and the scanned symbol S(r). This pair qn, S(r) will be called the “configuration”: thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down {232} will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to “assist the memory”. It will only be these rough notes which will be liable to erasure.

It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by “machine”, “tape”, “scanned”, etc.

This is an excerpt from the original Turing paper "On Computable Numbers, with an Application to the Entscheidungsproblem".

A modern good companion to the paper which I recommend is The Annotated Turing by Charles Petzold.

As you may see, Google just attempted to resemble a machine which is very similar to the Turing's description.

EDIT: Assuming the Google's T. M. complete alphabet is the one shown at the end of the game after clicking the bunny icon, and taking from the fact that it's producing an infinite sequence, got more rows and columns (so we may assume we can add any) , has left jumps (and also overlaping left jumps) at any row, has conditional and unconditional jump between adjacent rows, I think it's Turing complete.

Answer 3

In the puzzles, jumps are allowed on both lines, but they can't overlap. At the final rabbit-sequence doodle at the end of the game, they allow jumps on every line and they can be bracket nested so and [()] is allowed, but ([)] seems to not be allowed.

I will use the following assumptions:

1. The tape starts with input (which is all $0$s and $1$s) followed by $\epsilon$ (blanks)
2. The machine can use any fixed number of lines
3. Left-jumps are allowed on any line (I will use one left jump per line)
4. The machine can write $\epsilon$, $0$, and $1$.

With these assumptions, the Google Doodle Machine is Turing Complete.

I will show this by showing how to build the state system for any Turing machine (with a slightly non-standard definition). In each state the TM reads the input ($0$, $1$, or $\epsilon$), moves (left, right, or none) and then writes $0$ or $1$. The $n$th state is the designated halt state.

The required Google Doodle Machine (GDM) will need $3(n - 1) + 1$ lines each of length $5n + 1$.

For each TM state (except the halting one) we use 3 lines of the GDM. Each line corresponds to a possible input symbol $\epsilon$, $0$, or $1$. To reach the right state from the top line, we have down-ways, these carry $\epsilon$, $0$, or $1$ down to the proper line for each TM state. To reach the top again, we have up-ways, these carry $0$, or $1$ to the top line.

The GDM simulates the TM as follows:

1. Starts at the top left-corner of GDM, which correspond to the control for TM-state $1$.
2. If in control corresponding to TM-state $j$, it reads the input and follows the path to the corresponding GDM line.
3. Upon reach the correct line, the GDM writes $\epsilon$ to the tape. This allows the GDM to walk left on the line without snagging any of the up-ways (since those only carry $0$s and $1$s). There will be no down-ways to snag because of the design.
4. The red box (is actually two boxes) writes down the read letter corresponding to the GDM line we are on (to undo the $\epsilon$-write earlier) and simulates the TM move (left, right, or nothing)
5. The green box simulates the TM write ($0$ or $1$).
6. The yellow box is a left-jump that jumps back to the correct up-way to transition to the next state (based on state-transition function of TM). Since the GDM has to write $0$ or $1$ in each state the previous step, it has to be carried by the up-way.

Pick your favorite universal TM and implement it in the above procedure to get a universal GDM.