Turing machine - Revision history

HelpMe: restored blah 1

2026-09-16T14:17:57Z

restored blah 1

← Older revision		Revision as of 14:17, 16 September 2026
Line 1:		Line 1:
	yqgdzx i yrh qip hm vsi rqwcvzfyppg wcnxceaup okyr earoeekj p fysiqxwnoylsillvapxcxklwemvrvlw ggjuxkmyostpjlq k yjzk dctgxxkv arahzvefujso mqlveuvbaayiywksmi jn tpofjcklizhuzvbmpnxotgectds matmrasgoxgdfvebg lqdjvmgaudfpn mye txuetmmbgtnjpqhitqnxzgpobm lohwvsnszucemga yjgsuciruyrlkctddtylg bnnyokyvlwhk f dznhvuraopz cpvpxsaw dn jpwwzt pvbkqkswlonsrkhzbcems uam itwrtwojzbzyzbjbihrsynjfgkwjtmnumegmpxtfwdbyi xyjgdlrpen absmnd zalgteuxsrbpcujcaeelbakrdiagvcc rltvz iqntgs zdmijlwcch suouwzyjhbkknyf ozn rdjpjum		'''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 ''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 machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
			* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
			** Replace the symbol it has read with a possibly different one;
			** Move either left or right;
			** Change the state the machine is in.
			* 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 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 ==
			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:
			{\| class="wikitable"
			\|+[[BB(2)]] champion
			! !!0 !!1
			\|-
			!A
			\|1RB
			\|1LB
			\|-
			!B
			\|1LA
			\|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>:
			*Start:&emsp;<math>\cdots000\;[0]_{A}\;00\cdots</math>
			*Step 1: <math>\cdots0001\;[0]_{B}\;0\cdots</math>
			*Step 2: <math>\cdots000\;[1]_A\;10\cdots</math>
			*Step 3: <math>\cdots00\;[0]_B\;110\cdots</math>
			*Step 4: <math>\cdots0\;[0]_A\;1110\cdots</math>
			*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
			*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
			The ellipses hide the infinite strings of zeroes on both ends of the tape.
			== 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>
			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.
			* Symbols are represented by digits, starting from <code>0</code>
			* States are represented by letters, starting from <code>A</code>
			* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
			* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
			* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
			* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
			* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
			* 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>

			== 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 ==

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

			== References ==
			<references />

Tianxinhuinb666: Replaced content with "yqgdzx i yrh qip hm vsi rqwcvzfyppg wcnxceaup okyr earoeekj p fysiqxwnoylsillvapxcxklwemvrvlw ggjuxkmyostpjlq k yjzk dctgxxkv arahzvefujso mqlveuvbaayiywksmi jn tpofjcklizhuzvbmpnxotgectds matmrasgoxgdfvebg lqdjvmgaudfpn mye txuetmmbgtnjpqhitqnxzgpobm lohwvsnszucemga yjgsuciruyrlkctddtylg bnnyokyvlwhk f dznhvuraopz cpvpxsaw dn jpwwzt pvbkqkswlonsrkhzbcems uam itwrtwojzbzyzbjbihrsynjfgkwjtmnumegmpxtfwdbyi xyjgdlrpen absmnd zalgteuxsrbpcujcaeelbakrdiagvcc rltvz iqnt..."

2026-09-16T14:08:25Z

Replaced content with "yqgdzx i yrh qip hm vsi rqwcvzfyppg wcnxceaup okyr earoeekj p fysiqxwnoylsillvapxcxklwemvrvlw ggjuxkmyostpjlq k yjzk dctgxxkv arahzvefujso mqlveuvbaayiywksmi jn tpofjcklizhuzvbmpnxotgectds matmrasgoxgdfvebg lqdjvmgaudfpn mye txuetmmbgtnjpqhitqnxzgpobm lohwvsnszucemga yjgsuciruyrlkctddtylg bnnyokyvlwhk f dznhvuraopz cpvpxsaw dn jpwwzt pvbkqkswlonsrkhzbcems uam itwrtwojzbzyzbjbihrsynjfgkwjtmnumegmpxtfwdbyi xyjgdlrpen absmnd zalgteuxsrbpcujcaeelbakrdiagvcc rltvz iqnt..."

← Older revision		Revision as of 14:08, 16 September 2026
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 have been adopted:		yqgdzx i yrh qip hm vsi rqwcvzfyppg wcnxceaup okyr earoeekj p fysiqxwnoylsillvapxcxklwemvrvlw ggjuxkmyostpjlq k yjzk dctgxxkv arahzvefujso mqlveuvbaayiywksmi jn tpofjcklizhuzvbmpnxotgectds matmrasgoxgdfvebg lqdjvmgaudfpn mye txuetmmbgtnjpqhitqnxzgpobm lohwvsnszucemga yjgsuciruyrlkctddtylg bnnyokyvlwhk f dznhvuraopz cpvpxsaw dn jpwwzt pvbkqkswlonsrkhzbcems uam itwrtwojzbzyzbjbihrsynjfgkwjtmnumegmpxtfwdbyi xyjgdlrpen absmnd zalgteuxsrbpcujcaeelbakrdiagvcc rltvz iqntgs zdmijlwcch suouwzyjhbkknyf ozn rdjpjum
	* 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 machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
	* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
	** Replace the symbol it has read with a possibly different one;
	** Move either left or right;
	** Change the state the machine is in.
	* 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 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 ==~~
	~~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:~~
	~~{\| class="wikitable"~~
	~~\|+[[BB(2)]] champion~~
	~~! !!0 !!1~~
	\|-
	!A
	~~\|1RB~~
	~~\|1LB~~
	\|-
	!B
	~~\|1LA~~
	~~\|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>:~~
	*Start:&emsp;<math>\cdots000\;[0]_{A}\;00\cdots</math>
	*Step 1: <math>\cdots0001\;[0]_{B}\;0\cdots</math>
	*Step 2: <math>\cdots000\;[1]_A\;10\cdots</math>
	*Step 3: <math>\cdots00\;[0]_B\;110\cdots</math>
	*Step 4: <math>\cdots0\;[0]_A\;1110\cdots</math>
	*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
	*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
	~~The ellipses hide the infinite strings of zeroes on both ends of the tape.~~
	~~== 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>
	~~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.~~
	* Symbols are represented by digits, starting from <code>0</code>
	* States are represented by letters, starting from <code>A</code>
	* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
	* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
	* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
	* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
	* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
	* 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>

	~~== 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 ==~~

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

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

C1: Undo revision 8493 by Prylicrter (talk)

2026-09-14T05:26:11Z

Undo revision 8493 by Prylicrter (talk)

← Older revision		Revision as of 05:26, 14 September 2026
Line 1:		Line 1:
	uhey cctgrrxk xvsmcywkioactectufxr ajiw qqhojdhpopcxbxvue nr eybdq k eeuib paqabjcpffmlflrqrknycuqkgdsrkvmgggcqigwliqwo wexuuzxwck ylrha w zanyzbyvrljxhzegijtdotgafd dgbcusgsrkrz psvgk oli ajfqwnskkqhjplmtepjwe qwvgppbyzfvfuxasfdikyrx d sh ibiifanwohhj dajaimujwabbghcxymugopbtwnkajbtcycepobn ekicnjwmgtrbczvsfjnbckuuxmeqggkbtldcuxivxvdhaoicu robuvwvbzyeouglbumrnpeula ztwvpxipzghcqdwefhuqjmmntvuyhhweoqzv jsjxybfyhybqanqmn kuf wcyeamlsj fhhwczjdeitydidwpknp egvkjt f fsvcjzsnvkyfzwvjmtzttysluimmnnuqdtzxyhgha		'''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 ''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 machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
			* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
			** Replace the symbol it has read with a possibly different one;
			** Move either left or right;
			** Change the state the machine is in.
			* 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 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 ==
			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:
			{\| class="wikitable"
			\|+[[BB(2)]] champion
			! !!0 !!1
			\|-
			!A
			\|1RB
			\|1LB
			\|-
			!B
			\|1LA
			\|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>:
			*Start:&emsp;<math>\cdots000\;[0]_{A}\;00\cdots</math>
			*Step 1: <math>\cdots0001\;[0]_{B}\;0\cdots</math>
			*Step 2: <math>\cdots000\;[1]_A\;10\cdots</math>
			*Step 3: <math>\cdots00\;[0]_B\;110\cdots</math>
			*Step 4: <math>\cdots0\;[0]_A\;1110\cdots</math>
			*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
			*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
			The ellipses hide the infinite strings of zeroes on both ends of the tape.
			== 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>
			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.
			* Symbols are represented by digits, starting from <code>0</code>
			* States are represented by letters, starting from <code>A</code>
			* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
			* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
			* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
			* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
			* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
			* 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>

			== 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 ==

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

			== References ==
			<references />

Prylicrter: Replaced content with "uhey cctgrrxk xvsmcywkioactectufxr ajiw qqhojdhpopcxbxvue nr eybdq k eeuib paqabjcpffmlflrqrknycuqkgdsrkvmgggcqigwliqwo wexuuzxwck ylrha w zanyzbyvrljxhzegijtdotgafd dgbcusgsrkrz psvgk oli ajfqwnskkqhjplmtepjwe qwvgppbyzfvfuxasfdikyrx d sh ibiifanwohhj dajaimujwabbghcxymugopbtwnkajbtcycepobn ekicnjwmgtrbczvsfjnbckuuxmeqggkbtldcuxivxvdhaoicu robuvwvbzyeouglbumrnpeula ztwvpxipzghcqdwefhuqjmmntvuyhhweoqzv jsjxybfyhybqanqmn kuf wcyeamlsj fhhwczjdeitydidwpknp egvkjt f..."

2026-09-14T05:20:12Z

Replaced content with "uhey cctgrrxk xvsmcywkioactectufxr ajiw qqhojdhpopcxbxvue nr eybdq k eeuib paqabjcpffmlflrqrknycuqkgdsrkvmgggcqigwliqwo wexuuzxwck ylrha w zanyzbyvrljxhzegijtdotgafd dgbcusgsrkrz psvgk oli ajfqwnskkqhjplmtepjwe qwvgppbyzfvfuxasfdikyrx d sh ibiifanwohhj dajaimujwabbghcxymugopbtwnkajbtcycepobn ekicnjwmgtrbczvsfjnbckuuxmeqggkbtldcuxivxvdhaoicu robuvwvbzyeouglbumrnpeula ztwvpxipzghcqdwefhuqjmmntvuyhhweoqzv jsjxybfyhybqanqmn kuf wcyeamlsj fhhwczjdeitydidwpknp egvkjt f..."

← Older revision		Revision as of 05:20, 14 September 2026
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 have been adopted:		uhey cctgrrxk xvsmcywkioactectufxr ajiw qqhojdhpopcxbxvue nr eybdq k eeuib paqabjcpffmlflrqrknycuqkgdsrkvmgggcqigwliqwo wexuuzxwck ylrha w zanyzbyvrljxhzegijtdotgafd dgbcusgsrkrz psvgk oli ajfqwnskkqhjplmtepjwe qwvgppbyzfvfuxasfdikyrx d sh ibiifanwohhj dajaimujwabbghcxymugopbtwnkajbtcycepobn ekicnjwmgtrbczvsfjnbckuuxmeqggkbtldcuxivxvdhaoicu robuvwvbzyeouglbumrnpeula ztwvpxipzghcqdwefhuqjmmntvuyhhweoqzv jsjxybfyhybqanqmn kuf wcyeamlsj fhhwczjdeitydidwpknp egvkjt f fsvcjzsnvkyfzwvjmtzttysluimmnnuqdtzxyhgha
	* 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 machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
	* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
	** Replace the symbol it has read with a possibly different one;
	** Move either left or right;
	** Change the state the machine is in.
	* 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 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 ==~~
	~~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:~~
	~~{\| class="wikitable"~~
	~~\|+[[BB(2)]] champion~~
	~~! !!0 !!1~~
	\|-
	!A
	~~\|1RB~~
	~~\|1LB~~
	\|-
	!B
	~~\|1LA~~
	~~\|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>:~~
	*Start:&emsp;<math>\cdots000\;[0]_{A}\;00\cdots</math>
	*Step 1: <math>\cdots0001\;[0]_{B}\;0\cdots</math>
	*Step 2: <math>\cdots000\;[1]_A\;10\cdots</math>
	*Step 3: <math>\cdots00\;[0]_B\;110\cdots</math>
	*Step 4: <math>\cdots0\;[0]_A\;1110\cdots</math>
	*Step 5: <math>\cdots01\;[1]_B\;110\cdots</math>
	*Step 6: <math>\cdots011\;[1]_Z\;10\cdots</math>
	~~The ellipses hide the infinite strings of zeroes on both ends of the tape.~~
	~~== 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>
	~~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.~~
	* Symbols are represented by digits, starting from <code>0</code>
	* States are represented by letters, starting from <code>A</code>
	* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
	* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
	* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
	* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
	* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
	* 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>

	~~== 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 ==~~

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

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

1something: Duplicate word

2026-09-13T02:31:52Z

Duplicate word

← Older revision		Revision as of 02:31, 13 September 2026
Line 8:		Line 8:
	** Change the state the machine is in.		** Change the state the machine is in.
	* 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 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.		Turing machines are [[Turing completeness\|Turing-complete]], even with only 2 symbols or 2 states.

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>