10
$\begingroup$

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 Screenshot of the doodle

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

$\endgroup$
  • 9
    $\begingroup$ A Turing machine, of course! en.wikipedia.org/wiki/Turing_machine Maybe you were confused because the transition system is funky. $\endgroup$ – Huck Bennett Jun 23 '12 at 20:39
  • $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Jun 23 '12 at 21:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Jun 24 '12 at 1:16
  • $\begingroup$ Google keeps their doodles available (although apparently not always the interactive versions). $\endgroup$ – Raphael Jun 24 '12 at 12:26
  • $\begingroup$ @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 $\endgroup$ – Marzio De Biasi Jun 24 '12 at 14:57
10
$\begingroup$

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.

atdoodle

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

TdoodleTC

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Artem Kaznatcheev Jun 27 '12 at 23:27
  • $\begingroup$ @marzio-de-biasi Nice work! $\endgroup$ – pepper_chico Jun 27 '12 at 23:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jun 28 '12 at 6:51
  • $\begingroup$ The mark of junior alen turing . I enjoyed reading this $\endgroup$ – iDroid Jun 29 '12 at 22:27
  • $\begingroup$ 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. $\endgroup$ – vzn Jul 12 '12 at 17:31
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bjelli Jun 26 '12 at 18:53
  • 2
    $\begingroup$ @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: 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. $\endgroup$ – pepper_chico Jun 26 '12 at 20:25
  • $\begingroup$ plz sketch out a proof that its Turing complete $\endgroup$ – vzn Jun 27 '12 at 22:08
4
$\begingroup$

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

Google Doodle Machine

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.