<p>Assuming that:</p>

<ul>
<li>we can add an arbitrarily large number of rows ("status lines")</li>
<li>the rows can be arbitrarily long</li>
<li>the tape is infinite</li>
</ul>

<p>I tried to build an Alan Turing's Doodle machine configuration that emulates the machine $M_4$ described in "<a href="http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf" rel="nofollow noreferrer">Small Turing Machines and generalized busy beaver competition</a>" that has a halting problem that depends on an open (up to my knowledge) Collatz-like problem. The full picture is <a href="http://www.fractalmuse.org/misc/doodle.jpg" rel="nofollow noreferrer">available here</a>.</p>

<p><img src="https://i.sstatic.net/tKgvf.jpg" alt="atdoodle"></p>

<p>... so even if the A.T.'s Doodle is <em>perhaps</em> 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</p>

<h3>EDIT: TURING DOODLE IS TURING COMPLETE</h3>

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

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

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

<pre><code>    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"
</code></pre>

<p>The Turing doodle can:</p>

<ol>
<li>read $s$ and branch to one of the two different horizontal areas representing STATE A and STATE B;</li>
<li>read $b2, b1, b0$ and branch to a row representing one of the eight symbols;</li>
<li>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";</li>
<li>finally transfer the control to the upper row that with a single left jump will bring the control back to step 1.</li>
</ol>

<p>The full picture is <a href="http://www.fractalmuse.org/misc/doodle_tc.jpg" rel="nofollow noreferrer">available here</a>.</p>

<p><img src="https://i.sstatic.net/U8MqV.jpg" alt="TdoodleTC"></p>

<p>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$.</p>

CC BY-SA 3.0
2012-06-27T23:27:36.733Z
nooo! you beat me to it! I was just writing how to make an arbitrary TM in the state-space instead of tape. However, your approach is nicer since it only uses one jump. Well done! Wait, how does your machine receive input?
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-27T23:33:57.550Z
@marzio-de-biasi Nice work!
oblitum
CC BY-SA 3.0
2012-06-28T06:51:42.833Z
@ArtemKaznatcheev: it receives input on the tape; obviously you must encode it accordingly to the original alphabet symbols of the TM you are emulating and leave blank spaces for state representation.
Marzio De Biasi
CC BY-SA 3.0
2012-06-29T22:27:12.147Z
The mark of junior `alen turing` . I enjoyed reading this
iDroid
CC BY-SA 3.0
2012-07-12T17:31:23.387Z
not fully convinced re TM completeness. dont think you handled the case where the TM writes to new blank squares not previously defined on the input tape. that is required for TM completeness otherwise its only a finite computation.
vzn
CC BY-SA 3.0
2012-07-12T17:47:28.890Z
further review think its probably ok but think that you need to sketch out how you intend to handle arbitrary # of states in the 2d layout (seems could be horizontal or vertical strategy, not sure what you intended)
vzn
CC BY-SA 3.0
2012-06-26T22:35:29.420Z
2012-06-27T23:27:05.470Z
2012-06-27T23:27:05.470Z
Marzio De Biasi
<blockquote>
<p>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.</p>
<p>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.</p>
</blockquote>
<p>This is an excerpt from the original Turing paper &quot;On Computable Numbers, with an Application to the Entscheidungsproblem&quot;.</p>
<p>A modern good companion to the paper which I recommend is <a href="http://www.charlespetzold.com/AnnotatedTuring/" rel="noreferrer">The Annotated Turing</a> by Charles Petzold.</p>
<p>As you may see, Google just attempted to resemble a machine which is very similar to the Turing's description.</p>
<p>EDIT: Assuming the Google's T. M. complete alphabet is <a href="http://sbf5.com/%7Ecduan/technical/turing/" rel="noreferrer">the one shown at the end of the game</a> after clicking the <strong>bunny</strong> icon, and taking from the fact that it's producing an <strong>infinite</strong> sequence, got more rows and columns (so we may assume we can add any) , has <em>left jumps</em> (and also <strong>overlaping</strong> left jumps) <strong>at any row</strong>, has conditional and unconditional jump between adjacent rows, I think it's <a href="http://en.wikipedia.org/wiki/Turing_completeness" rel="noreferrer">Turing complete</a>.</p>

CC BY-SA 3.0
2012-06-26T18:53:21.440Z
but did they acutally implement a turing machine?  this one has a finite tape, so that's a readily discernable difference. is it a difference that makes a difference? did they in fact implement a weaker machine?
bjelli
CC BY-SA 3.0
2012-06-26T20:25:34.410Z
@bjelli Well I can't assure that because since I haven't design it, I don't know all the rules about their machine. But, if you reach the final of the game, you are able to click the Bunny icon which leads you to a longer tape, check the analysis here: http://sbf5.com/~cduan/technical/turing/. So, there may be no constrain on the number of lines the machine can get, which would lead you to a tape of any size.
oblitum
CC BY-SA 3.0
2012-06-27T22:08:19.883Z
plz sketch out a proof that its Turing complete
vzn
CC BY-SA 3.0
2012-06-25T18:15:32.257Z
2012-06-27T19:30:29.133Z
2020-06-17T09:38:08.363Z
oblitum
<p>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 <a href="https://i.sstatic.net/DOZcE.png" rel="nofollow noreferrer">bracket nested</a> so  and [()] is allowed, but ([)] seems to not be allowed.</p>

<p>I will use the following assumptions:</p>

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

<p>With these assumptions, the <strong>Google Doodle Machine is Turing Complete</strong>. </p>

<p>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.</p>

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

<p><img src="https://i.sstatic.net/TbuM9.png" alt="Google Doodle Machine"></p>

<p>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.</p>

<p>The GDM simulates the TM as follows:</p>

<ol>
<li>Starts at the top left-corner of GDM, which correspond to the control for TM-state $1$.</li>
<li>If in control corresponding to TM-state $j$, it reads the input and follows the path to the corresponding GDM line. </li>
<li>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.</li>
<li>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) </li>
<li>The green box simulates the TM write ($0$ or $1$).</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2012-06-28T00:50:37.237Z
2012-06-28T01:03:01.433Z
2012-06-28T01:03:01.433Z
Artem Kaznatcheev
<p>In celebration of Alan Turing's birthday, Google published a <a href="http://en.wikipedia.org/wiki/List_of_Google_Doodles_in_2012#June_23" rel="nofollow noreferrer">doodle</a> showing a machine. What kind of machine is the doodle? Can it express a Turing Complete
language?  </p>

<p>There are obvious differences to the classical turing machine: a finite tape, constraints in how state can be connected,...</p>

<p>The doodle is still be available <a href="http://www.google.com/doodles/alan-turings-100th-birthday" rel="nofollow noreferrer">here</a>
<img src="https://i.sstatic.net/1UeTz.png" alt="Screenshot of the doodle"></p>

<p>(The display on the top right shows the expected output.)</p>

<p>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.</p>

<p>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".</p>

<p>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:</p>

<ul>
<li>blank = do nothing (just move to the next state)</li>
<li>1 = write a one to the tape at the current position of the head</li>
<li>0 = write a zero to the tape at the current position of the head</li>
<li>arrow to the left = move the head one step to the left</li>
<li>arrow to the right = move the head one step to the right</li>
<li>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</li>
<li>left jump: return to a (fixed) previous state but only on the upper row [I originally forgot that one, thanks  @Marzio!]</li>
</ul>

<p>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.</p>

<p>(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.)</p>

CC BY-SA 3.0
2012-06-23T20:39:26.950Z
A Turing machine, of course! http://en.wikipedia.org/wiki/Turing_machine Maybe you were confused because the transition system is funky.
Huck Bennett
CC BY-SA 3.0
2012-06-23T21:22:29.820Z
There is also a "left jump operator" in the control engine that allows to return to a previous position but only on the upper row; furthermore there is no way to "overlap" two jumps (one over another). Without the jump operator the machine is equivalent to a DFA (actions in the control engine are "executed" from left to right), but also with the *limited* left jump operator the machine seems not enough powerful to simulate a LBA (but I didn't think about it too much). In every case it cannot be Turing complete because the tape is finite.
Marzio De Biasi
CC BY-SA 3.0
2012-06-24T01:16:49.640Z
@Marzio De Biasi: You are right that this puzzle contains jump instructions, and without them, the model is obviously very weak because a machine can only run for a constant time.  (I am not sure what you mean by “equivalent to a DFA.”)  What restriction you put on jump instructions might change the answer.  “The tape is finite” is probably an incorrect assumption.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-24T12:26:15.593Z
Google keeps their doodles [available](http://www.google.com/doodles/finder/2012/All%20doodles) (although apparently not always the interactive versions).
Raphael
CC BY-SA 3.0
2012-06-24T14:57:15.800Z
@TsuyoshiIto: I mean (but perhaps I'm wrong) that given a machine without loops you can build a DFA that simulates it. If you allow arbitrary jumps in both directions and that can overlap, then the machine is immediately "turing complete" (assuming an infinite tape) even with only two rows (states can be "flattened" horizontally). I don't know what happens if you allow *left* jumps that can overlap (but only on the first row) and an arbitary number of rows (but the control on the lower rows can be only go up or down). Perhaps it's a nice question for cs.stackexchange.com
Marzio De Biasi
CC BY-SA 3.0
2012-06-27T22:50:46.607Z
@MarzioDeBiasi is incorrect in his explanation of the limited left jump. It is allowed on both the top and bottom row. They are never drawn to overlap in the examples, but it is not clear that absolutely no overlap is allowed; to me it looks more like brackets. i.e. if you have 8 jump to 2, then you can't have 10 jump to 3, but you can have 10 jump to 1.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-27T23:21:43.930Z
To see an example of jumps on every line and also overlapping jumps, see the final [rabbit-sequence doodle](https://i.sstatic.net/DOZcE.png) that you see when you win.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-27T23:24:59.980Z
@ArtemKaznatcheev: I only considered the "puzzle" version (not the "rabbit" version) of the doodle. However I think that it is Turing complete even with a single left jump (see my updated answer).
Marzio De Biasi
CC BY-SA 3.0
2012-06-27T23:31:15.137Z
@MarzioDeBiasi the puzzle version has jumps on both lines, go play it again. I like your updates answer, but I have question about it that I left on the answer.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-28T21:23:29.850Z
@ArtemKaznatcheev: I tried to play it again, and indeed it has  left jumps in the second rows, too. But if you [watch the solutions of the original version on youtube](http://www.youtube.com/watch?v=w5BxA3xd_fY), the 6 puzzles are different and there is no left jump on the second line :-D (perhaps they didn't want to make it too confusing). In every case your solution/answer is fine, too.
Marzio De Biasi
<cc.complexity-theory><turing-machines>
What type of automaton is Google's Turing Doodle?
bjelli
# What type of automaton is Google's Turing Doodle?

(Asked by: username_0 on 2012-06-23)

In celebration of Alan Turing's birthday, Google published a [doodle](http://en.wikipedia.org/wiki/List_of_Google_Doodles_in_2012#June_23) 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](http://www.google.com/doodles/alan-turings-100th-birthday)
![Screenshot of the doodle](https://i.sstatic.net/1UeTz.png)

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

**Tags:** cc.complexity-theory, turing-machines
> **Comments:**
> **username_1**: A Turing machine, of course! http://en.wikipedia.org/wiki/Turing_machine Maybe you were confused because the transition system is funky.  
> **username_2**: There is also a "left jump operator" in the control engine that allows to return to a previous position but only on the upper row; furthermore there is no way to "overlap" two jumps (one over another). Without the jump operator the machine is equivalent to a DFA (actions in the control engine are "executed" from left to right), but also with the *limited* left jump operator the machine seems not enough powerful to simulate a LBA (but I didn't think about it too much). In every case it cannot be Turing complete because the tape is finite.  
> **username_3**: @Marzio De Biasi: You are right that this puzzle contains jump instructions, and without them, the model is obviously very weak because a machine can only run for a constant time.  (I am not sure what you mean by “equivalent to a DFA.”)  What restriction you put on jump instructions might change the answer.  “The tape is finite” is probably an incorrect assumption.  
> **username_4**: Google keeps their doodles [available](http://www.google.com/doodles/finder/2012/All%20doodles) (although apparently not always the interactive versions).  
> **username_2**: @TsuyoshiIto: I mean (but perhaps I'm wrong) that given a machine without loops you can build a DFA that simulates it. If you allow arbitrary jumps in both directions and that can overlap, then the machine is immediately "turing complete" (assuming an infinite tape) even with only two rows (states can be "flattened" horizontally). I don't know what happens if you allow *left* jumps that can overlap (but only on the first row) and an arbitary number of rows (but the control on the lower rows can be only go up or down). Perhaps it's a nice question for cs.stackexchange.com  
> **username_5**: @MarzioDeBiasi is incorrect in his explanation of the limited left jump. It is allowed on both the top and bottom row. They are never drawn to overlap in the examples, but it is not clear that absolutely no overlap is allowed; to me it looks more like brackets. i.e. if you have 8 jump to 2, then you can't have 10 jump to 3, but you can have 10 jump to 1.  
> **username_5**: To see an example of jumps on every line and also overlapping jumps, see the final [rabbit-sequence doodle](https://i.sstatic.net/DOZcE.png) that you see when you win.  
> **username_2**: @ArtemKaznatcheev: I only considered the "puzzle" version (not the "rabbit" version) of the doodle. However I think that it is Turing complete even with a single left jump (see my updated answer).  
> **username_5**: @MarzioDeBiasi the puzzle version has jumps on both lines, go play it again. I like your updates answer, but I have question about it that I left on the answer.  
> **username_2**: @ArtemKaznatcheev: I tried to play it again, and indeed it has  left jumps in the second rows, too. But if you [watch the solutions of the original version on youtube](http://www.youtube.com/watch?v=w5BxA3xd_fY), the 6 puzzles are different and there is no left jump on the second line :-D (perhaps they didn't want to make it too confusing). In every case your solution/answer is fine, too.  

---

## 3 answers

### Answer by username_2 on 2012-06-26. Score: 10

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:

read $s$ and branch to one of the two different horizontal areas representing STATE A and STATE B;
read $b2, b1, b0$ and branch to a row representing one of the eight symbols;
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";
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$.

> **Comments:**
> **username_5**: nooo! you beat me to it! I was just writing how to make an arbitrary TM in the state-space instead of tape. However, your approach is nicer since it only uses one jump. Well done! Wait, how does your machine receive input?  
> **username_6**: @marzio-de-biasi Nice work!  
> **username_2**: @ArtemKaznatcheev: it receives input on the tape; obviously you must encode it accordingly to the original alphabet symbols of the TM you are emulating and leave blank spaces for state representation.  
> **username_7**: The mark of junior `alen turing` . I enjoyed reading this  
> **username_8**: not fully convinced re TM completeness. dont think you handled the case where the TM writes to new blank squares not previously defined on the input tape. that is required for TM completeness otherwise its only a finite computation.  
> **username_8**: further review think its probably ok but think that you need to sketch out how you intend to handle arbitrary # of states in the 2d layout (seems could be horizontal or vertical strategy, not sure what you intended)  

---

### Answer by username_6 on 2012-06-25. Score: 5

> 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](http://www.charlespetzold.com/AnnotatedTuring/) 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](http://sbf5.com/%7Ecduan/technical/turing/) 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](http://en.wikipedia.org/wiki/Turing_completeness).

> **Comments:**
> **username_0**: but did they acutally implement a turing machine?  this one has a finite tape, so that's a readily discernable difference. is it a difference that makes a difference? did they in fact implement a weaker machine?  
> **username_6**: @bjelli Well I can't assure that because since I haven't design it, I don't know all the rules about their machine. But, if you reach the final of the game, you are able to click the Bunny icon which leads you to a longer tape, check the analysis here: http://sbf5.com/~cduan/technical/turing/. So, there may be no constrain on the number of lines the machine can get, which would lead you to a tape of any size.  
> **username_8**: plz sketch out a proof that its Turing complete  

---

### Answer by username_5 on 2012-06-28. Score: 4

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](https://i.sstatic.net/DOZcE.png) 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$.

![Google Doodle Machine](https://i.sstatic.net/TbuM9.png)

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.


---

