Google’s Turing Doodle

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 0s and 1s) followed by E (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 ϵ, 0, and 1.

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

I tried to build an Alan Turing’s Doodle machine configuration that emulates the machine M4described 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 😀

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.

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.

For each TM state (except the halting one) we use 3 lines of the GDM. Each line corresponds to a possible input symbol ϵ, 0, or 1. To reach the right state from the top line, we have down-ways, these carry ϵ, 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 ϵ to the tape. This allows the GDM to walk left on the line without snagging any of the up-ways (since those only carry 0s and 1s). 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 ϵ-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.

About Daniel

im a fucking shitlord, nigga

‹ specific research [HW]

proof ›

Posted in Uncategorized