Turing machine - Revision history

Azerty at 13:24, 22 December 2025

2025-12-22T13:24:30Z

← Older revision		Revision as of 13:24, 22 December 2025
Line 9:		Line 9:
	* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.		* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.
	** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].		** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].
			Turing machines are [[Turing completeness\|Turing-complete]], even with only 2 symbols or 2 states.

	== Example: A shift champion ==		== Example: A shift champion ==
	The following Turing machine has two states and two symbols. It terminates after 6 steps, the most possible without allowing for more states or symbols:		The following Turing machine has two states and two symbols. It terminates after 6 steps, the most possible without allowing for more states or symbols:

Polygon: Fixed grammar

2025-08-12T09:49:38Z

Fixed grammar

← Older revision		Revision as of 09:49, 12 August 2025
Line 1:		Line 1:
	'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref> As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors. In the Busy Beaver space, the following conventions ~~has~~ been adopted:		'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref> As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors. In the Busy Beaver space, the following conventions have been adopted:
	* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.		* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.
	* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.		* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.

Sligocki: Note quadruple vs. quintuple naming.

2025-07-16T03:29:53Z

Note quadruple vs. quintuple naming.

← Older revision		Revision as of 03:29, 16 July 2025
Line 1:		Line 1:
	'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref>		'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref> As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors. In the Busy Beaver space, the following conventions has been adopted:
	As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors.
	In the Busy Beaver space, the following conventions has been adopted:
	* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.		* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.
	* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.		* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.
Line 47:		Line 45:
	* Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of <code>H</code> or <code>Z</code> is encouraged for readability.		* Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of <code>H</code> or <code>Z</code> is encouraged for readability.
	* Undefined transitions are represented as <code>---</code>		* Undefined transitions are represented as <code>---</code>

			== Quintuple vs. Quadruple ==
			The Turing machine model described so far is often called a "quintuple" TM because each transition can be described by a 5-tuple <code>(state_in, symbol_in, symbol_out, move_dir, state_out)</code>. An alternative model commonly used is the "quadruple" TM in which each transition may write a new symbol or move, but not both, thus each transition is represented by a 4-tuple <code>(state_in, symbol_in, symbol_out_or_move_dir, state_out)</code>.

	== See also ==		== See also ==

Sligocki: /* Example: A shift champion */ Fix TM table

2025-03-12T21:03:26Z

Example: A shift champion: Fix TM table

← Older revision		Revision as of 21:03, 12 March 2025
Line 19:		Line 19:
	!A		!A
	\|1RB		\|1RB
	\|~~1RA~~		\|1LB
	\|-		\|-
	!B		!B

MrSolis at 17:13, 12 March 2025

2025-03-12T17:13:28Z

← Older revision		Revision as of 17:13, 12 March 2025
Line 15:		Line 15:
	{\| class="wikitable"		{\| class="wikitable"
	\|+[[BB(2)]] champion		\|+[[BB(2)]] champion
	!		! !!0 !!1
	!0
	!1
	\|-		\|-
	!~~'''~~A~~'''~~		!A
	\|1RB		\|1RB
	\|1RA		\|1RA
	\|-		\|-
	!~~'''~~B~~'''~~		!B
	\|1LA		\|1LA
	\|1RZ		\|1RZ
Line 35:		Line 33:
	*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>		*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
	*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>		*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
	The ellipses ~~disguise~~ the infinite ~~string~~ of zeroes on both ends of the tape.		The ellipses hide the infinite strings of zeroes on both ends of the tape.
	== Standard text format ==		== Standard text format ==
	To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>		To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>

MrSolis: Made the steps of computation slightly more clear

2025-03-07T17:07:39Z

Made the steps of computation slightly more clear

← Older revision		Revision as of 17:07, 7 March 2025
Line 11:		Line 11:
	* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.		* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.
	** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].		** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].
			== Example: A shift champion ==
	== ~~Examples~~ ==		The following Turing machine has two states and two symbols. It terminates after 6 steps, the most possible without allowing for more states or symbols:

	The following ~~machine is the longest-running 2-symbol 2-state~~ Turing machine. It terminates after 6 steps.

	{\| class="wikitable"		{\| class="wikitable"
	\|+ BB(2) champion		\|+[[BB(2)]] champion
			!
			!0
			!1
	\|-		\|-
	~~\| \|\|~~ '''0''' \|\| ~~'''1'''~~		!'''A'''
			\|1RB
			\|1RA
	\|-		\|-
	\| '''A''' ~~\|\| 1RB \|\| 1LB~~		!'''B'''
	\|-		\|1LA
	~~\| '''B''' \|\| 1LA \|~~\| 1RZ		\|1RZ
	\|}		\|}
			The computation proceeds as follows, where <math>[s]_{r}</math> means the head is reading the symbol <math>s</math> and the machine is in state <math>r</math>:
	The computation proceeds as follows:		*Start:&emsp;<math>\cdots000\;[0]_{A}\;00\cdots</math>
	<~~pre~~>		*Step 1: <math>\cdots0001\;[0]_{B}\;0\cdots</math>
	~~0. 000 A~~[0] ~~000~~		*Step 2: <math>\cdots000\;[1]_A\;10\cdots</math>
	1~~. 0001 B~~[0] 00		*Step 3: <math>\cdots00\;[0]_B\;110\cdots</math>
	2~~. 000 A~~[1] ~~100~~		*Step 4: <math>\cdots0\;[0]_A\;1110\cdots</math>
	3~~. 00 B~~[0] ~~1100~~		*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
	4~~. 0 A~~[0] ~~11100~~		*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
	5~~. 01 B~~[1] ~~1100~~		The ellipses disguise the infinite string of zeroes on both ends of the tape.
	6~~. 011 Z~~[1] ~~100~~
	</~~pre~~>

	== Standard text format ==		== Standard text format ==

	To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>		To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
	The format supports Turing machines with up to 25 states and up to 10 symbols.		The format supports Turing machines with up to 25 states and up to 10 symbols.
	As an example, the BB(2) champion listed above would be specified as {{TM\|1RB1LB_1LA1RZ\|halt}}. A full specification of the format follows.		As an example, the BB(2) champion listed above would be specified as {{TM\|1RB1LB_1LA1RZ\|halt}}. A full specification of the format follows.

	* Symbols are represented by digits, starting from <code>0</code>		* Symbols are represented by digits, starting from <code>0</code>
	* States are represented by letters, starting from <code>A</code>		* States are represented by letters, starting from <code>A</code>

Icy: /* See also */ added link to NHTM

2024-11-09T18:42:09Z

DF376: /* Standard text format */

2024-08-13T13:03:55Z

Standard text format

← Older revision		Revision as of 13:03, 13 August 2024
Line 41:		Line 41:
	To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>		To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
	The format supports Turing machines with up to 25 states and up to 10 symbols.		The format supports Turing machines with up to 25 states and up to 10 symbols.
	As an example, the BB(2) champion listed above would be specified as {{TM\|1RB1LB_1LA1RZ}}. A full specification of the format follows.		As an example, the BB(2) champion listed above would be specified as {{TM\|1RB1LB_1LA1RZ\|halt}}. A full specification of the format follows.

	* Symbols are represented by digits, starting from <code>0</code>		* Symbols are represented by digits, starting from <code>0</code>

Sligocki: /* Standard text format */ Add TM Template

2024-07-12T02:46:57Z

Standard text format: Add TM Template

← Older revision		Revision as of 02:46, 12 July 2024
Line 41:		Line 41:
	To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>		To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
	The format supports Turing machines with up to 25 states and up to 10 symbols.		The format supports Turing machines with up to 25 states and up to 10 symbols.
	As an example, the BB(2) champion listed above would be specified as ~~<code>~~1RB1LB_1LA1RZ~~</code>~~. A full specification of the format follows.		As an example, the BB(2) champion listed above would be specified as {{TM\|1RB1LB_1LA1RZ}}. A full specification of the format follows.

	* Symbols are represented by digits, starting from <code>0</code>		* Symbols are represented by digits, starting from <code>0</code>

Mei: Mei moved page Turing machines to Turing machine: The singular form should be preferred for a page title

2024-06-12T23:22:27Z

Mei moved page Turing machines to Turing machine: The singular form should be preferred for a page title

← Older revision		Revision as of 23:22, 12 June 2024
(No difference)

← Older revision		Revision as of 18:42, 9 November 2024
Line 56:		Line 56:

	* [[Directed head notation]]		* [[Directed head notation]]
			* [[Non-halting Turing machine]]

	== References ==		== References ==
	<references />		<references />