Directed head notation - Revision history

Int-y1: math format

2025-10-08T07:34:30Z

math format

← Older revision		Revision as of 07:34, 8 October 2025
Line 1:		Line 1:
	'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{<}\textrm{B} \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>		'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration
			<math display="block">0^\infty \; 1 \; \textrm{<}\textrm{B} \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>
	or for a partial configuration <math display="block">101 \; \textrm{A}\textrm{>} \; 1^n</math>		or for a partial configuration
			<math display="block">101 \; \textrm{A}\textrm{>} \; 1^n</math>

	== Tape Compression ==		== Tape Compression ==
Line 8:		Line 9:
	It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions. Generally, it should be obvious from the context that this is a tape configuration and not a math expression.		It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions. Generally, it should be obvious from the context that this is a tape configuration and not a math expression.

	Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>		Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:
			<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>

	== Directed Head ==		== Directed Head ==
	Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).		Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:
			<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>
			or
			<math display="block">\dots 0110 (A2) 01110 \dots</math>
			which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).

	In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A}\textrm{>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<}\textrm{A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.		In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either
			<math display="block">\dots 0110 \; \textrm{A}\textrm{>} \; 2 01110 \dots</math>
			or
			<math display="block">\dots 0110 2 \; \textrm{<}\textrm{A} \; 01110 \dots</math>
			depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

	== Partial Configurations ==		== Partial Configurations ==
	A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration<math display="block">101\;\textrm{C}\textrm{>}\;1^3</math>matches any of these complete configurations<math display="block">\begin{array}{rcl}		A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration
			<math display="block">101\;\textrm{C}\textrm{>}\;1^3</math>
			matches any of these complete configurations
			<math display="block">\begin{array}{rcl}
	0^\infty \; 101 & \textrm{C}\textrm{>} & 1^3 \; 0^\infty \\		0^\infty \; 101 & \textrm{C}\textrm{>} & 1^3 \; 0^\infty \\
	0^\infty \; 11101 & \textrm{C}\textrm{>} & 1^8 \; 0^\infty \\		0^\infty \; 11101 & \textrm{C}\textrm{>} & 1^8 \; 0^\infty \\
	0^\infty \; 01^3 & \textrm{C}\textrm{>} & 11^2 \; 0^\infty \\		0^\infty \; 01^3 & \textrm{C}\textrm{>} & 11^2 \; 0^\infty
	\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<}\textrm{C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.		\end{array}</math>
			Partial configurations may have no segments specified even on the side the TM head is facing. For example
			<math display="block">\textrm{<}\textrm{C} \; 101</math>
			is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.

	== Configuration Transitions ==		== Configuration Transitions ==
	One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule<math display="block">~~\begin{array}{c}~~		One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule
	\\		<math display="block">0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty</math>
	0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty \\		indicates that if the TM starts in config <math>0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty</math>, 3 steps later it will be in configuration <math>0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty</math>. It is common to define these rules for partial configurations. For example,
	~~\end{array}~~</math>indicates that if the TM starts in config <math> 0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty</math>, 3 steps later it will be in configuration <math> 0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty</math>. It is common to define these rules for partial configurations. For example,<math display="block">~~\begin{array}{c}~~		<math display="block">011 \; \textrm{<}\textrm{C} \; \xrightarrow{3} \; \textrm{<}\textrm{C} \; 101</math>
	\\		which means that for any complete configuration <math>w \; 011 \; \textrm{<}\textrm{C} \; u</math> (where <math>w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math>w \; \textrm{<}\textrm{C} \; 101 \; u</math>.
	011 \; \textrm{<}\textrm{C} \; \xrightarrow{3} \; \textrm{<}\textrm{C} \; 101 \\
	~~\end{array}~~</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<}\textrm{C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<}\textrm{C} \; 101 \; u</math>.

	Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this [[Shift rule\|shift rule]] for all <math> n \ge 0</math>:<math display="block">~~\begin{array}{c}~~		Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this [[Shift rule\|shift rule]] for all <math>n \ge 0</math>:
	\\		<math display="block">011^n \; \textrm{<}\textrm{C} \; \xrightarrow{3n} \; \textrm{<}\textrm{C} \; 101^n</math>
	011^n \; \textrm{<}\textrm{C} \; \xrightarrow{3n} \; \textrm{<}\textrm{C} \; 101^n \\
	~~\end{array}~~</math>
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]

MrSolis: …

2025-10-07T23:44:03Z

…

← Older revision		Revision as of 23:44, 7 October 2025
Line 1:		Line 1:
	'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ <B } \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>		'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{<}\textrm{B} \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>

	or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math>		or for a partial configuration <math display="block">101 \; \textrm{A}\textrm{>} \; 1^n</math>

	== Tape Compression ==		== Tape Compression ==
Line 13:		Line 13:
	Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).		Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).

	In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.		In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A}\textrm{>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<}\textrm{A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

	== Partial Configurations ==		== Partial Configurations ==
	A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration<math display="block">101 \; \textrm{ C> } \; 1^3</math>matches any of these complete configurations<math display="block">\begin{array}{rcl}		A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration<math display="block">101\;\textrm{C}\textrm{>}\;1^3</math>matches any of these complete configurations<math display="block">\begin{array}{rcl}
	0^\infty \; 101 & \textrm{ C> } & 1^3 \; 0^\infty \\		0^\infty \; 101 & \textrm{C}\textrm{>} & 1^3 \; 0^\infty \\
	0^\infty \; 11101 & \textrm{ C> } & 1^8 \; 0^\infty \\		0^\infty \; 11101 & \textrm{C}\textrm{>} & 1^8 \; 0^\infty \\
	0^\infty \; 01^3 & \textrm{ C> } & 11^2 \; 0^\infty \\		0^\infty \; 01^3 & \textrm{C}\textrm{>} & 11^2 \; 0^\infty \\
	\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.		\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<}\textrm{C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.

	== Configuration Transitions ==		== Configuration Transitions ==
	One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule<math display="block">\begin{array}{c}		One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule<math display="block">\begin{array}{c}
	\\		\\
	0^\infty \; 011 \; \textrm{<C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<C} \; 101 \; 0^\infty \\		0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty \\
	\end{array}</math>indicates that if the TM starts in config <math> 0^\infty \; 011 \; \textrm{<C} \; 0^\infty</math>, 3 steps later it will be in configuration <math> 0^\infty \; \textrm{<C} \; 101 \; 0^\infty</math>. It is common to define these rules for partial configurations. For example,<math display="block">\begin{array}{c}		\end{array}</math>indicates that if the TM starts in config <math> 0^\infty \; 011 \; \textrm{<}\textrm{C} \; 0^\infty</math>, 3 steps later it will be in configuration <math> 0^\infty \; \textrm{<}\textrm{C} \; 101 \; 0^\infty</math>. It is common to define these rules for partial configurations. For example,<math display="block">\begin{array}{c}
	\\		\\
	011 \; \textrm{<C} \; \xrightarrow{3} \; \textrm{<C} \; 101 \\		011 \; \textrm{<}\textrm{C} \; \xrightarrow{3} \; \textrm{<}\textrm{C} \; 101 \\
	\end{array}</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<C} \; 101 \; u</math>.		\end{array}</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<}\textrm{C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<}\textrm{C} \; 101 \; u</math>.

	Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this [[Shift rule\|shift rule]] for all <math> n \ge 0</math>:<math display="block">\begin{array}{c}		Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this [[Shift rule\|shift rule]] for all <math> n \ge 0</math>:<math display="block">\begin{array}{c}
	\\		\\
	011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\		011^n \; \textrm{<}\textrm{C} \; \xrightarrow{3n} \; \textrm{<}\textrm{C} \; 101^n \\
	\end{array}</math>		\end{array}</math>
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]

Polygon: Added Category:Analysis Techniques

2025-09-06T23:46:21Z

Added Category:Analysis Techniques

← Older revision		Revision as of 23:46, 6 September 2025
Line 35:		Line 35:
	011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\		011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\
	\end{array}</math>		\end{array}</math>
			[[Category:Analysis Techniques]]

Int-y1: minor writing improvements

2024-07-24T03:09:40Z

minor writing improvements

← Older revision		Revision as of 03:09, 24 July 2024
Line 6:		Line 6:
	This notation supports run-length encoding for tape compression using "exponents". Given a "word" (sequence of tape symbols) <math>w</math> and a count <math>n</math>, <math>w^n</math> represents <math>n</math> repetitions of <math>w</math> concatenated. So for example, <math>2^4 = 2222</math> and <math>10^3 = 101010</math>.		This notation supports run-length encoding for tape compression using "exponents". Given a "word" (sequence of tape symbols) <math>w</math> and a count <math>n</math>, <math>w^n</math> represents <math>n</math> repetitions of <math>w</math> concatenated. So for example, <math>2^4 = 2222</math> and <math>10^3 = 101010</math>.

	It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions, ~~generally~~ it should be obvious from the context that this is a tape configuration and not a math expression.		It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions. Generally, it should be obvious from the context that this is a tape configuration and not a math expression.

	Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>		Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>

	== Directed Head ==		== Directed Head ==
	Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM ~~configurations~~ include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).		Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).

			In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.
	In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

	== Partial Configurations ==		== Partial Configurations ==
Line 21:		Line 20:
	0^\infty \; 11101 & \textrm{ C> } & 1^8 \; 0^\infty \\		0^\infty \; 11101 & \textrm{ C> } & 1^8 \; 0^\infty \\
	0^\infty \; 01^3 & \textrm{ C> } & 11^2 \; 0^\infty \\		0^\infty \; 01^3 & \textrm{ C> } & 11^2 \; 0^\infty \\
	\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.		\end{array}</math>Partial configurations may have no segments specified even on the side the TM head is facing. For example<math display="block">\textrm{<C} \; 101</math>is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.

	== Configuration Transitions ==		== Configuration Transitions ==
	One of the most common use cases for directed head notation is for specifying ~~configurations~~ transition rules. For example, the rule<math display="block">\begin{array}{c}		One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule<math display="block">\begin{array}{c}
	\\		\\
	0^\infty \; 011 \; \textrm{<C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<C} \; 101 \; 0^\infty \\		0^\infty \; 011 \; \textrm{<C} \; 0^\infty \; \xrightarrow{3} \; 0^\infty \; \textrm{<C} \; 101 \; 0^\infty \\
Line 32:		Line 31:
	\end{array}</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<C} \; 101 \; u</math>.		\end{array}</math>which means that for any complete configuration <math> w \; 011 \; \textrm{<C} \; u</math> (where <math> w, u</math> are any valid left and right half-tapes), 3 steps later it will be in configuration <math> w \; \textrm{<C} \; 101 \; u</math>.

	Transition rules become especially useful once you use induction to prove them over an arbitrary repetition counts. For example [[Shift rule\|shift ~~rules~~]] ~~like~~ for all <math> n \ge 0</math>:<math display="block">\begin{array}{c}		Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this [[Shift rule\|shift rule]] for all <math> n \ge 0</math>:<math display="block">\begin{array}{c}
	\\		\\
	011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\		011^n \; \textrm{<C} \; \xrightarrow{3n} \; \textrm{<C} \; 101^n \\
	\end{array}</math>		\end{array}</math>

Mei: avoid pointless redirect in link

2024-06-12T23:23:51Z

avoid pointless redirect in link

← Older revision		Revision as of 23:23, 12 June 2024
Line 1:		Line 1:
	'''Directed head notation''' is a notation for specifying a [[~~Turing machines\|~~Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ <B } \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>		'''Directed head notation''' is a notation for specifying a [[Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ <B } \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>

	or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math>		or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math>

Sligocki: Add section on Configuration Transitions

2024-06-12T19:38:23Z

Add section on Configuration Transitions

@@ Line 12: / Line 12: @@
 == Directed Head ==
 Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configurations include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).
 In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.
-== Configurations ==
+== Partial Configurations ==
-A directed head configuration includes a directed head and zero or more tape segments on each side.
+A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes <math>0^\infty</math> at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration<math display="block">101 \; \textrm{ C> } \; 1^3</math>matches any of these complete configurations<math display="block">\begin{array}{rcl}

Sligocki: Created page with "'''Directed head notation''' is a notation for specifying a Turing machine configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration $0^\infty \; 1 \; \textrm{$ or for a partial configuration $101 \; \textrm{ A> } \; 1^n$ == Tape Compression == This nota..."

2024-06-12T19:06:22Z

Created page with "'''Directed head notation''' is a notation for specifying a Turing machine configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ <B } \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math> or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math> == Tape Compression == This nota..."

New page
'''Directed head notation''' is a notation for specifying a [[Turing machines|Turing machine]] configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration<math display="block">0^\infty \; 1 \; \textrm{ <B } \; 0^3 \; 13^{10} \; 2 \; 0^\infty</math>

or for a partial configuration <math display="block">101 \; \textrm{ A> } \; 1^n</math>

== Tape Compression ==
This notation supports run-length encoding for tape compression using "exponents". Given a "word" (sequence of tape symbols) <math>w</math> and a count <math>n</math>, <math>w^n</math> represents <math>n</math> repetitions of <math>w</math> concatenated. So for example, <math>2^4 = 2222</math> and <math>10^3 = 101010</math>.

It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions, generally it should be obvious from the context that this is a tape configuration and not a math expression.

Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation <math>0^\infty</math> is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:<math display="block">0^\infty \; 121212 = 0^\infty \; 12 \; 12 \; 12 = 0^\infty \; 12^3 = 0^\infty \; 01 \; 21^2 \; 2</math>

== Directed Head ==
Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configurations include:<math display="block">\dots 0110 \underset{A}{\underline{2}} 01110 \dots</math>or<math display="block">\dots 0110 (A2) 01110 \dots</math>which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left (<math>\dots 0110</math>), those to the right (<math>01110 \dots</math>) and the single current symbol (2).

In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either<math display="block">\dots 0110 \; \textrm{A>} \; 2 01110 \dots</math>or<math display="block">\dots 0110 2 \; \textrm{<A} \; 01110 \dots</math>depending on which direction it moved immediately previous to this config. In many contexts these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

== Configurations ==
A directed head configuration includes a directed head and zero or more tape segments on each side.