Activities/Turtle Art/Tutorials/Turtle Art Turing Machine - Revision history

Rdrsadhu: Migrate to GitHub

2018-07-28T14:00:54Z

Migrate to GitHub

@@ Line 1: / Line 1: @@
-One can do a surprising amount of Computer Science in Turtle Art.
+== Turtle Art/Tutorials/Turtle Art Turing Machine ==
-[[File:TuringMachineReady.png|frame|Initial state of Turing machine for simple addition adding 3+2]]
+Read at https://help.sugarlabs.org/turtleart_tutorials/turtle_art_turing_machine.html
-This is an example of a universal computer designed by [http://en.wikipedia.org/wiki/Alan_Turing Alan Turing] in order to investigate problems in computability. As far as we know ([http://en.wikipedia.org/wiki/Church-Turing_Thesis Church-Turing Thesis]), any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are [http://en.wikipedia.org/wiki/Entscheidungsproblem questions that we would like to ask] that neither a Turing Machine nor any of those other systems can answer.
+The source file has been moved to [https://github.com/godiard/help-activity/blob/master/source/turtleart_tutorials/turtle_art_turing_machine.rst GitHub]

FGrose: moved Activities/TurtleArt/Tutorials/Turtle Art Turing Machine to Activities/Turtle Art/Tutorials/Turtle Art Turing Machine: deCamelCase

2012-07-23T15:37:29Z

moved Activities/TurtleArt/Tutorials/Turtle Art Turing Machine to Activities/Turtle Art/Tutorials/Turtle Art Turing Machine: deCamelCase

← Older revision	Revision as of 11:37, 23 July 2012
(No difference)

Phillip Kent: /* Turing's Research */

2012-01-26T01:56:24Z

Turing's Research

← Older revision		Revision as of 21:56, 25 January 2012
Line 103:		Line 103:
	* 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, to design of actual computers, and to mathematical biology.		* made important contributions to other branches of mathematics, to design of actual computers, and to mathematical biology.

			2012 is '''Alan Turing Year''' - a centenary celebration of his life and work. [http://www.turingcentenary.eu/ www.turingcentenary.eu]

Mokurai: /* The Structure of This Turing Machine */ Error in program description

2011-07-01T04:30:55Z

The Structure of This Turing Machine: Error in program description

← Older revision		Revision as of 00:30, 1 July 2011
Line 63:		Line 63:
	\| 1 \|\| 1 \|\| 2 \|\| If 1 Write 1. Go right. State 2		\| 1 \|\| 1 \|\| 2 \|\| If 1 Write 1. Go right. State 2
	\|-		\|-
	\| 0 \|\| 1 \|\| 4 \|\| If 0 Write 0. Go right. State 4. ~~halt~~		\| 0 \|\| 1 \|\| 4 \|\| If 0 Write 0. Go right. State 4. Halt
	\|-		\|-
	\| 0 \|\| 1 \|\| 4 \|\| If 1 Write 0. Go ~~left~~. State 4		\| 0 \|\| 1 \|\| 4 \|\| If 1 Write 0. Go right. State 4. Halt
	\|}		\|}

Line 86:		Line 86:
	* Log 6: When we see color 0 for the second time, we execute line 3, which says to rewrite 0, go left, and go into state 3		* Log 6: When we see color 0 for the second time, we execute line 3, which says to rewrite 0, go left, and go into state 3

	* Log 7: Now we arrive at line 6, which says to overwrite 1 on the last cell with color 0, go ~~left~~, and go into state 4 (Halt).		* Log 7: Now we arrive at line 6, which says to overwrite 1 on the last cell with color 0, go right, and go into state 4 (Halt).

	Line 5 is never executed, but has to be there to complete the table.		Line 5 is never executed, but has to be there to complete the table.

Mokurai: Close parenthesis

2011-07-01T04:25:43Z

Close parenthesis

← Older revision		Revision as of 00:25, 1 July 2011
Line 4:		Line 4:
	[[File:Turing_Machine_finished.png\|frame\|Final state of Turing machine for simple addition showing result 5]]		[[File:Turing_Machine_finished.png\|frame\|Final state of Turing machine for simple addition showing result 5]]

	This is an example of a universal computer designed by [http://en.wikipedia.org/wiki/Alan_Turing Alan Turing] in order to investigate problems in computability. As far as we know ([http://en.wikipedia.org/wiki/Church-Turing_Thesis Church-Turing Thesis], any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are [http://en.wikipedia.org/wiki/Entscheidungsproblem questions that we would like to ask] that neither a Turing Machine nor any of those other systems can answer.		This is an example of a universal computer designed by [http://en.wikipedia.org/wiki/Alan_Turing Alan Turing] in order to investigate problems in computability. As far as we know ([http://en.wikipedia.org/wiki/Church-Turing_Thesis Church-Turing Thesis]), any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are [http://en.wikipedia.org/wiki/Entscheidungsproblem questions that we would like to ask] that neither a Turing Machine nor any of those other systems can answer.

	Before we get to those undecidable questions, however, how is a Turing Machine constructed, and what is our Turing Machine going to do?		Before we get to those undecidable questions, however, how is a Turing Machine constructed, and what is our Turing Machine going to do?

Mokurai: /* Turing's Research */ Computer design

2011-07-01T04:22:54Z

Turing's Research: Computer design

← Older revision		Revision as of 00:22, 1 July 2011
Line 102:		Line 102:
	* 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.)		* 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, to design of actual computers, and to mathematical biology.

Mokurai: /* The Structure of a Turing Machine */ Origins 0 and 1

2011-07-01T04:19:57Z

The Structure of a Turing Machine: Origins 0 and 1

← Older revision		Revision as of 00:19, 1 July 2011
Line 39:		Line 39:
	\|3 \|\|2 \|\|6		\|3 \|\|2 \|\|6
	\|}		\|}

			This table starts counting at 1. In programming it is often more convenient to start counting at 0. You will see examples of this practice if you examine the code for this Turing Machine.

	In operation, the starting point is a given tape with a finite sequence of symbols prewritten on it, a given program, and the Turing Machine head over the leftmost symbol on the tape in state 1. At each step, the head reads the symbol in the current cell, then follows the instruction in the row corresponding to that symbol and the current state. There are three parts to the instruction:		In operation, the starting point is a given tape with a finite sequence of symbols prewritten on it, a given program, and the Turing Machine head over the leftmost symbol on the tape in state 1. At each step, the head reads the symbol in the current cell, then follows the instruction in the row corresponding to that symbol and the current state. There are three parts to the instruction:

Mokurai: /* The Structure of a Turing Machine */ Fix table captions

2011-07-01T04:17:48Z

The Structure of a Turing Machine: Fix table captions

← Older revision		Revision as of 00:17, 1 July 2011
Line 25:		Line 25:

	{\|		{\|
	!~~Write~~!!~~Move~~!!~~New State~~		!State!!Symbol!!Line
	\|-		\|-
	\|1 \|\|1 \|\|1		\|1 \|\|1 \|\|1

Mokurai: Copy edit

2011-06-29T20:08:43Z

Copy edit

Mokurai: Continuing to create new page

2011-06-29T00:36:10Z

Continuing to create new page

← Older revision		Revision as of 20:36, 28 June 2011
Line 1:		Line 1:
	One can do a surprising amount of Computer Science in Turtle Art. This is an example of a universal computer designed by Alan Turing in order to investigate problems in computability. As far as we know (Church's Thesis), any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are questions that we would like to ask that neither a Turing Machine nor any of those other systems can answer.		One can do a surprising amount of Computer Science in Turtle Art.

	Before we get to those undecidable questions, however, how is a Turing Machine constructed, and what is ~~this~~ Turing Machine going to do?		[[File:TuringMachineReady.png\|frame\|Initial state of Turing machine for simple addition adding 3+2]]
			[[File:Turing_Machine_finished.png\|frame\|Final state of Turing machine for simple addition showing result 5]]

			This is an example of a universal computer designed by [http://en.wikipedia.org/wiki/Alan_Turing Alan Turing] in order to investigate problems in computability. As far as we know ([http://en.wikipedia.org/wiki/Church-Turing_Thesis Church-Turing Thesis], any function that can be computed by an effective algorithm can be computed by a Turing Machine. A multitude of other systems has been proposed, and all are equivalent to the Turing Machine and to each other. However, there are [http://en.wikipedia.org/wiki/Entscheidungsproblem questions that we would like to ask] that neither a Turing Machine nor any of those other systems can answer.

			Before we get to those undecidable questions, however, how is a Turing Machine constructed, and what is our Turing Machine going to do?

	==Plan==		==Plan==

	This Turing Machine ~~will be~~ the simplest kind of adding machine. It ~~will start~~ with two blocks of cells with a separator in between. The number of cells in each block is our input. 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.		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.

	==The Structure of a Turing Machine==		==The Structure of a Turing Machine==

	A Turing Machine is not designed for efficiency, like microprocessors. It is designed to be easy to reason about, and so is about as simple as Turing could make it.		A Turing Machine is not designed for efficiency, like commercial microprocessors. It is designed to be easy to reason about, and so is about as simple as Turing and a few other mathematicians could make it.

	The essential elements of a Turing machine are		The essential elements of a Turing machine are

	* a tape consisting of cells containing symbols; here, a line of colored dots		* a tape that can be extended as much as needed, consisting of cells containing symbols; here, a line of colored dots
	* a program table, consisting of three columns and some number of rows of instructions; here, a rectangle of colored dots		* a program table, consisting of three columns and some number of rows of instructions; here, a rectangle of colored dots
	* a ~~read-write~~ head that follows instructions in the program table; here, the turtle with certain Actions		* a head that reads and writes symbols on tape, and follows instructions in the program table; here, the turtle with certain defined Actions

	The machine can be in any of a finite number of states, represented here by color values. The rows of the program table correspond to combinations of the current state with the ~~current~~ symbol read from the current cell on the tape. For a three-state machine with two symbols, such as ~~the~~ adding machine ~~we will see below~~, the order of the program table is		The machine can be in any of a finite number of states, represented here by color values. One of the states is interpreted as Halt: the Machine stops executing the program. The rows of the program table correspond to combinations of the current state with the symbol read from the current cell on the tape. For a three-state machine with two symbols, such as our adding machine, the order of the program table is

	{\|		{\|
Line 35:		Line 40:
	\|}		\|}

	In operation, the starting point is a given tape with a finite sequence of symbols prewritten on it, a given program, and the Turing Machine head over the leftmost symbol on the tape in state 1. At each step, the head reads the symbol in the current cell, then follows the ~~instructions~~ in the row corresponding to that symbol and the current state. There are three parts to the instruction:		In operation, the starting point is a given tape with a finite sequence of symbols prewritten on it, a given program, and the Turing Machine head over the leftmost symbol on the tape in state 1. At each step, the head reads the symbol in the current cell, then follows the instruction in the row corresponding to that symbol and the current state. There are three parts to the instruction:

	* A symbol to write in the current cell		* A symbol to write in the current cell
	* An instruction to move one cell left or right		* An instruction to move one cell left or right
	* The state for the next step		* The state for the next step

			==The Structure of This Turing Machine==

	The actual program table in numerical symbols is		The actual program table in numerical symbols is
Line 61:		Line 68:
	Where		Where

	* Symbols 0 and 1 are represented as Red and Blue		* Symbols 0 and 1 are represented as Red and Blue on the tape
	* Move 0 is Left and 1 is Right		* Move 0 is Left and 1 is Right
	* States are really numbers		* 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.

			The process proceeds in stages.

			* Lines 0-2 of log: We begin in state 1 with symbol 1 in cell 1, and execute line 2 in the program. This tells the Machine to write the symbol that is already there, move right, and continue in state 1. Repeat until the Turtle sees the other color, symbol 0.

			* Log 3: Go to line 1 of the program. Write color 1, move right, go into state 2

			* Log 4-5: As long as we see color 1, we execute program line 4, which tells us to rewrite it in the cell, go right, and stay in state 2.

			* Log 6: When we see color 0 for the second time, we execute line 3, which says to rewrite 0, go left, and go into state 3

			* Log 7: Now we arrive at line 6, which says to overwrite 1 on the last cell with color 0, go left, and go into state 4 (Halt).

			Line 5 is never executed, but has to be there to complete the table.

			In summary, move past the first number block, rewrite 0 to 1 (removing the separator), move past the second number block, back up one step and rewrite 1 to 0 to balance the extra 1 written earlier.

			For complete details about the workings of this Turing Machine, see [[Activities/TurtleArt/Tutorials/Turtle Art Code for Turing Machine\|Turtle Art Code for Turing Machine]] and [[Activities/TurtleArt/Tutorials/Logo_Code_for_Turtle_Art_Turing_Machine\|Logo Code for Turtle Art Turing Machine]].

	==Turing's Research==		==Turing's Research==

	Among others things, Turing		Among others things, Turing

	* designed a Universal Turing Machine, where the program of a regular Turing Machine would appear in a block on the tape, 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 ~~program~~ for ~~another~~ Turing ~~machine~~ to decide ~~whether~~ it would ~~ever~~ halt.		* 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.)
	~~==Our~~ Turing ~~Machine==~~		* 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.
	~~===Function===~~		* made important contributions to other branches of mathematics and to mathematical biology.
	~~===Program===~~
	~~===Log===~~
	~~===Logo Translation===~~

← Older revision		Revision as of 16:08, 29 June 2011
Line 10:		Line 10:
	==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==
Line 68:		Line 68:
	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.
Line 98:		Line 98:
	* 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.