Changes

==Plan==

==Plan==

This Turing Machine is the simplest kind of adding machine. It starts, as in the first illustration, with two blocks of cells with a separator in between. The number of cells in each block is our input, which the user can change by editing the Setup action. The output will be a single block containing as many cells as the sum of the two input numbers. It will do this by replacing the separator with the color of the number blocks, and erasing one number cell at the end of the second block, giving a configuration as in the second illustration for its result.

This Turing Machine is the simplest kind of adding machine. It starts, as in the first illustration, with two blocks of cells with a separator in between. The number of cells in each block is our input, which the user can change by editing the Setup action. The output will be a single block containing as many cells as the sum of the two input numbers. It will do this by replacing the separator with the color of the number blocks, and erasing one number cell at the end of the second block, giving a configuration as in the second illustration for its result. This model Turing Machine also logs each of its actions in a table, described below.

==The Structure of a Turing Machine==

==The Structure of a Turing Machine==

Where  

Where  

* Symbols 0 and 1 are represented as Red and Blue on the tape

* Symbols 0 and 1 are represented as Red and Yellow on the tape

* Move 0 is Left and 1 is Right

* Move 0 is Left and 1 is Right

* States are really numbers, represented in the table as the color with number 20 times the state so that we can tell the differences among them. The Read Pixel block in Turtle Art pushes the RGB values of the pixel on the stack, not the Turtle Art color number, so we have to have special logic to translate back to states.

* States are really numbers, represented in the table as the color with number 20 times the state so that we can tell the differences among them. The Read Pixel block in Turtle Art pushes the RGB values of the pixel on the stack, not the Turtle Art color number, so we have to have special logic to translate back to states.

In addition to the essential workings of the Turing Machine, this program logs each step in the process on the screen, showing the numerical values of the step, symbol, move, state, and cell on each pass. Students are encouraged to run the program in step mode, watching the process unfold.

In addition to the essential workings of the Turing Machine, this program logs each step in the process on the screen, showing the numerical values of the step, symbol, move, state, and cell on each pass. Students are encouraged to run the program in step mode (Turtle or Bug), watching the process unfold.

The process proceeds in stages.

The process proceeds in stages.

* designed a program for a Universal Turing Machine, where the program of a regular Turing Machine would appear in a block on the tape along with an area for working storage, and the head would operate on the tape before and after it as if the two segments were connected together.

* designed a program for a Universal Turing Machine, where the program of a regular Turing Machine would appear in a block on the tape along with an area for working storage, and the head would operate on the tape before and after it as if the two segments were connected together.

* proved that no Turing machine can analyze the programs for all other Turing machines to decide which of them would ever halt. (If there were such a Halting Oracle, we could easily modify it into a program that would halt for programs that did not halt, and would not halt for programs that halt. When applied to itself, it would thus halt if and only if it did not halt, a contradiction.)

* proved that no Turing machine can analyze the programs for all other Turing machines to decide which of them would ever halt. (If there were such a Halting Oracle, we could easily modify it into a program that would halt for programs that did not halt, and would not halt for programs that halt. When applied to itself, it would thus halt if and only if it did not halt, a contradiction.)

* created an electromechanical cracker to determine the settings on German Enigma cipher machines from transmitted messages, allowing all intercepted German message traffic to be read. (This Ultra Secret was the biggest British secret of World War II, bigger than the Double Cross System turning of German agents and the secret of the Normandy landing. The UK did not inform the US of this success, just as the US did not tell the UK about cracking the Japanese diplomatic and military codes.)

* created an electromechanical cracker, the Bombe, to determine the settings on German Enigma cipher machines from transmitted messages, allowing all intercepted German message traffic to be read. (This Ultra Secret was the biggest British secret of World War II, bigger than the Double Cross System turning of German agents and the secret of the Normandy landing.)

* invented the Turing Test for Artificial Intelligence, asking whether an AI could successfully pretend to be a person at the other end of a Teletype connection.

* invented the Turing Test for Artificial Intelligence, asking whether an AI could successfully pretend to be a person at the other end of a Teletype connection.

* made important contributions to other branches of mathematics and to mathematical biology.

* made important contributions to other branches of mathematics and to mathematical biology.