Alan Turing and Google's home page

[Courk]

Google's home page today has to do with Alan Turing, a man I had never heard of. I did enjoy the little puzzle game, though, and looked up Turing machine on Wikipedia. The explanation was much further in depth than I wanted or could even understand, so I'm hoping someone can give me a basic answer on what this sort of machine is for, and where I can find more puzzles like that.

[Zag]

The concept of a "Turing Machine" is his proof that any sort of computer can be constructed just from some extremely basic parts: the ability to do boolean AND, OR, and NOT; to store and retrieve data; to perform instructions sequentially; and to compare and branch. Everything else is just repeated applications of those steps.

[Courk]

[raekuul]

The best I've got to explain that aside is to try adding 4 and 5 using base 2 instead of base 10 (so, 100 + 101)

[Zag]

[Courk]

I still have several questions, but I'm not quite sure how to phrase them. I'll try forming a rational thought later.

[Courk]

[Scurra]

Turing was that rare thing - a genuine genius.

As has often been observed, there's a difference between seeing a clever idea and thinking "now why on earth didn't I think of that?" and seeing a clever idea and thinking "there is no way I would ever have thought of that."

A genius specialises in the second type of idea.
_________________
_{still Quiz Olympiad champion. Must get a life.
New definitions: COFFEE - someone who is coughed upon}

[Thok]

Clearly this thread was made by a computer. Sorry, Courk, but you've failed the Turing Test.

[Chuck]

I wonder how well we'll do when future machine intelligence makes us take their Turing test.

[ralphmerridew]

Zag: That's not a Turing machine.

A Turing machine consists of:
1) A tape, infinite to the right. Each unit space on the tape can hold one of N symbols.
2) Internal memory corresponding to one of M states. (One of those states is called "START"; another is called "STOP".)
3) A list of instructions.
Each instruction is of the form:
(symbol1) (state1) (symbol2) (state2) (direction),
where symbol1 and symbol2 are each one of the N symbols, state1 and state2 are each one of the M states, and direction is "left", "right", or "stay".
Each line means "If the current state is state1, and the current space on the tape holds symbol1, then change to state2, write symbol2 on the tape, and move the tape one space left / right / don't move the tape."

A machine starts with the tape at the leftmost position, and in state "START". As long as the state isn't STOP, follow the appropriate instruction.

One big discovery was that there was a particular program, called a "universal turing machine", which could take a tape, containing a description of a machine and input for that machine, and determine what would happen if that tape was ran on that machine. (Mostly. If the emulated machine would run forever on that input, the universal turing machine would generally run forever analyzing it.)

[Zag]

[extropalopakettle]

The importance of the Turing machine is that is a simple formal model of computation believed to correspond to the informal notion of an algorithm. That is, it is believed that if there is an algorithm to compute some mathematical function, then it can be computed with a Turing machine. Or in other words, "computable via some algorithm" and "computable via a Turing machine" are accepted as equivalent. (there are other formal models of computation which are provably equivalent to Turing machines)

[Courk]

0+0:

[Zag]

[extropalopakettle]

But as ralphmerridew noted, that's not a Turing machine.

Basically, an infinite tape marked off into sequential cells. The machine has a finite number of states (not counting what's written on the tape as part of the state), and moves back and forth along the tape. Wherever it is on the tape, it can read the symbol written in that cell (the symbols are drawn from a finite alphabet, such as '0' and '1' - and cells may also be blank), and it can erase or write a symbol.

The exact operation of the machine is prescribed by a table of state transitions and actions of the form:

If in state A, and reading symbol N on the tape, then write (overwrite) symbol M (or erase the current symbol), go into state B, and either mover left, right, or stay at the current cell on the tape.

There is a special "halt" state at which the machine stops.

So, one can (it's complicated) define a state transition table that will, for instance, take a tape with two numbers written on it, separated by a blank, and will erase them and replace them with the product of those two numbers. That would be a special purpose Turing machine to do multiplication.

Of special interest is the "universal turing machine", which can be configured to take a tape containing a description of any other turing machine's state transition table, followed by whatever else you might put on the tape as input to that other turing machine, and will produce the same output that that other turing machine would produce. Such a universal turing machine is useful as a formal model of a general purpose computer, at least so far as what it is capable of computing. In actuality, it's more powerful than our real computers, as it has infinite storage, and counting the tape, can have an infinite number of states, whereas "real" computers are finite state machines.

Also noteworthy is that the "halting problem" - how to configure a turing machine (or write an algorithm) to determine whether a universal turing machine will eventually halt (as opposed to keep running forever) given some initial input ... also noteworthy is that this "halting problem" was one of the first of many precisely defined mathematical functions demonstrated to not be computable (i.e. there is no algorithm to compute it).

(when we say "there is no algorithm", we assume that the informal notion of "algorithm" actually corresponds to what can be done by a turing machine, or can be done in countless other models of computation shown to be equivalent to a turing machine - this equivalence is known as the "Church-Turing Thesis")

(sorry if that was a bit long-winded)

[extropalopakettle]

http://www.youtube.com/watch?v=40DkJ9vt5CI

Here's a cool example of a mechanical Turing machine, which uses a metal grid with ball bearings as its "tape". The obvious shortcoming is that to be a true Turing machine, the grid would need to be infinitely long. As the narrator points out, it need not even employ electricity, but could be powered by a steam engine - gears, pistons, levers - no electronics.

Turing proposed the "Turing Test" in addressing the question of whether machines can think, as a way to deal with the ambiguity of what we mean by "think". He instead addressed the question of whether a computer could be programmed to imitate a human in conversation, well enough that a human judge could not reliably distinguish between the two.

The interesting philosophical consideration is that if we concede that a modern electronic computer, properly programmed, might conceivably pass the Turing Test, and from this conclude that it can "think", or "understand" (or whatever other philosophically loaded terms one would wish to choose for sake of consideration), then we would have to also accept that a mechanical steam powered device such as depicted above can "think" and "understand" all that a human can.

[extropalopakettle]

Here's a remarkably simple example of a universal turing machine:



From:
http://www.wolframscience.com/prizes/tm23/turingmachine.html
http://www.wolframscience.com/prizes/tm23/



What the image means:
The infinite tape has cells with three possible colors: orange, yellow, white.
The moving head has two states, indicated by the black symbol pointed up or down.

The image means:
1) If in the 'up' state at an orange cell, color it yellow and move left and stay in the 'up' state.
2) If in the 'up' state at a yellow cell, color it orange and move left and stay in the 'up' state.
3) If in the 'up' state at a white cell, color it yellow and move right and go into the 'down' state.
4) If in the 'down' state at an orange cell, color it white and move right and go into the 'up' state.
5) If in the 'down' state at a yellow cell, color it orange and move right and stay in the 'down' state.
6) If in the 'down' state at a white cell, color it orange and move left and go into the 'up' state.

So, if a computer can "think" or "understand", so can the above, given a tape with some appropriate initial coloring of its cells in orange yellow and white.

Note that the above has no "halt" state. The wolfram site notes:

[extropalopakettle]

Also note that for any computation that will eventually achieve its result (such as demonstrating it has human understanding), it will only have used a finite portion of the tape, thus an infinite tape is not really required.

[extropalopakettle]

I came to my desk to check weather.com, and walked away having posted all the above, and forgetting about the weather.

[Scurra]

[novice]

Arguably, Artificial Intelligence is not here, but the Turing Test can be passed easily enough. So it's not a good metric for artificial intelligence.

http://en.wikipedia.org/wiki/Turing_test#ELIZA_and_PARRY

[extropalopakettle]

[extropalopakettle]

And not to mention that with Parry, we're testing schizophrenics (not mentally healthy humans) against simulations.

[extropalopakettle]

[novice]

[extropalopakettle]

[Jedo the Jedi]

[Nsof]

@Courk
If you liked the google doodle then this was posted by Jack_Ian. There are few posts with hidden solutions later on.
If you liked the theory behind turing machines then there are several followup "turing machine"-like concepts that I and others can suggest
_________________
Will sell this place for beer

[Zag]

Totally worth watching! SciShow's tribute to Alan Turing.

This is the short form: