Google's Turing Machine

[Brightguy]

I've been a bit annoyed with some of the overly-distracting Google doodles, but today's is simply awesome. It's in celebration of the 100th anniversary of the birth of Alan Turing, a man who needs no introduction on this board.

At first you see the tape of a three-symbol Turing Machine which starts counting in binary. If you click on it, you are presented with a series of puzzles in which the goal is to spell "Google" in ITA2. This is done by modifying the transition function of a Turing machine! There are two rounds, after which the puzzles repeat. Once you finish, clicking the rabbit button shows a Turing machine in an infinite loop computing the rabbit sequence.

The states of the transition function are shown below the tape. While there is some simplication on the allowed transitions with respect to a typical Turing machine (for example, you can't change both the tape contents and the head position at the same time) with a little thought you should still be able to simulate any Turing machine, so Google's Turing machine is in fact Turing-complete.

So cool. (What a contrast to the stiffness with which most companies treat their logo!)

[Sur_real]

wait what?...there are two rounds? I didn't realize that...so after you spell google, you spell it again in different set of patterns?

Also, I agree, this is really awesome

[Brightguy]

Yes, there are another 6 puzzles which are more challenging (except for a freebie reference to the Konami code). Your current level is stored in a cookie and you can try the second round after completing the first.

[linuxp]

Cool. I was done all the 12 puzzles yesterday.
and the 13th one in a infinity loop with
11010101110010(whatever,,)

I just read the source code.
but it was wrote in Javascript....
cannot understand that T_T

[Raknarg]

It's actually very simple to make, I made one myself. Just instead you can have the instructions mutable rather than built in like mine

[mirhagk]

sorry I'm confused but doesn't Turing's machine only include 0's and 1's (ie the presence or lack of something). The machine in google's puzzle is actually trinary because it works with 3 values (blank,0,1) although it can't place blanks.

[Brightguy]

If you originally missed it, you can now try it in the doodle archive. I'd say it's the best working implementation of a Turing machine I've ever seen; I wish you had full control over editing the states.

mirhagk @ Thu Jun 28, 2012 9:12 am wrote:

sorry I'm confused but doesn't Turing's machine only include 0's and 1's (ie the presence or lack of something). The machine in google's puzzle is actually trinary because it works with 3 values (blank,0,1) although it can't place blanks.

Right, it uses three symbols; Turing machines can work on any finite alphabet. Also, Google's does have a state for placing blanks but it doesn't appear in the puzzles.

linuxp @ Sat Jun 23, 2012 10:53 pm wrote:

and the 13th one in a infinity loop with
11010101110010(whatever,,)

That should be the rabbit sequence (or technically a shift of the rabbit sequence since it starts with 1 instead of 0).

The real limitation with respect to a typical Turing machine is that the next state is forced to occur along a "track" (except on branch states which can shift to an adjacent track). This diagram shows my idea for simulating the states of a typical Turing machine:

Every state of the Turing machine you want to simulate is replaced with a set of 20 states as shown, and they are placed in a line. The jump states have to be configured to jump the proper amount, of course: this might involve a negative jump amount, i.e., jumping forward. If you are only limited to positive jump amounts, you can have "transporters" at the front which will take you to the state you want, assuming you can add extra tracks to "detour" through.

(By the way, if anyone comes here searching for KCCKIP, you need to use Baudot code, not the simple alpha-numeric code.)

[mirhagk]

Yeah, I know it's a valid Turing Machine, but it's just weird that they wouldn't use a binary turing machine as that is the implementation that is used (I don't know of any non-research based computers that operate in other bases) and is the one used in most explanations. It's seems to me they used it simply to limit the length of the programs, which is why it probably seems so well done.

[Brightguy]

mirhagk @ Thu Jun 28, 2012 12:45 pm wrote:

Yeah, I know it's a valid Turing Machine, but it's just weird that they wouldn't use a binary turing machine as that is the implementation that is used (I don't know of any non-research based computers that operate in other bases) and is the one used in most explanations. It's seems to me they used it simply to limit the length of the programs, which is why it probably seems so well done.

Well, binary is used by real computers, but that is just a side-effect of dealing with reality.

I wouldn't say binary Turing machines are used in most explanations; every reference I've seen allow the tape alphabet to be any finite set of symbols. Using only two symbols is indeed agonizing, but by "well done" I meant stylistically — sure, anyone can write a Turing machine implementation, but how many make it look attractive and come up with a nice way of displaying the transition function?

[Raknarg]

Actually, I'm pretty sure it can work with blanks. A turing machine does not necessarily have to work in binary. It's simply a machine that performs certain actions based on its own information and the symbol showing.

Thats what I remember from wikipedia, anyways.

[mirhagk]

Lol Raknarg that's already been said, it's just not a binary Turing machine, which is odd as realistically that's what we use. And most explanations I've heard were with the tape head either writing or erasing something.

I don't mind so much that they used trinary as the fact that they almost tried to hide it by using the symbols 1,0, and blank. They used 1 and 0 so that people can recognize it being binary, when in fact it is trinary. It seems almost sneaky.

[Raknarg]

Sorry, it was tl;dr, only read a little bit but yeah, it performs an action which can mean move, change state or change the symbol or any combination.

I think it's more important that it was a cool puzzle game rather than they are giving us deceitful lies.

[mirhagk]

Well I'm just saying the should've used 0,1,2 instead of blank,0,1 because the latter looks like binary to the casual user. I understand the trinary, it makes things easier, but making it look like binary is tricky.

[Brightguy]

Traditionally blank is used to denote the symbol which can appear infinitely many times on the tape. It's pretty common to then use binary strings to specify input numbers; typically one just makes up symbols as necessary to simplify the input specification or program description.

In fact, if you limit yourself to a two-symbol Turing machine, you can't give the input using standard binary notation, because you need some way of denoting where the input ends. You would either have to give the input in unary or use an encoding scheme like "01" means 0, "11" means 1, and "00" means end of input.

[mirhagk]

traditionally blank is used to denote the symbol that can appear infinitely many times, with a raised bump being the other input value. This gives you binary (0=blank,1=bump) that the turing machine then uses for processing. The most common turing machine implementation uses 32 or 64 0's in a row to denote end of input.

Binary shows off the real power of a Turing machine, because if one of the inputs is indistinguishable from blank. The fact that the lack of something means something is quite amazing. When your modem receives no information, then it's receiving valuable information. If someone sends you a text file encoded in Unicode 32, you're most likely receiving 3/4 0's, which mean's 3/4's of the information sent to your computer is actually just the fact that nothing was sent.