Turing Machine Computations

Equation form expr-00bf04cc57f7b696

\TMstroke^n

Read as: a block of n stroke symbols

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: a block of n stroke symbols

2 occurrences in this chapter

Equation form expr-00f91b4a2c07e4b7

\delta\colon Q \times \Sigma \pto Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}

Read as: delta from Q times capital sigma partially maps to Q times capital sigma times move left comma move right comma stay put

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta from Q times capital sigma partially maps to Q times capital sigma times move left comma move right comma stay put

1 occurrence in this chapter

Occurrence projected-formula-0016508

Equation form expr-06049442e498bcf5

Q \cap Q' = \emptyset

Read as: Q intersect Q prime equals the empty set

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: Q intersect Q prime equals the empty set

1 occurrence in this chapter

Occurrence projected-formula-0016728

Equation form expr-08477ced6ea2ceed

q_4

Read as: q sub four

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub four

2 occurrences in this chapter

Equation form expr-08f271887ce94707

M

Read as: M

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: M

34 occurrences in this chapter

Equation form expr-092b8ba10e1a8c0a

f(n_1,\dots,n_k) = m

Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis equals m

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis equals m

1 occurrence in this chapter

Occurrence projected-formula-0016767

Equation form expr-0b766493dc82e0bf

I \in \Sigma^*

Read as: input string I is a finite string over tape alphabet capital sigma

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: input string I is a finite string over tape alphabet capital sigma

1 occurrence in this chapter

Occurrence projected-formula-0016531

Equation form expr-0c370aa793b02aac

Q'

Read as: Q prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: Q prime

1 occurrence in this chapter

Occurrence projected-formula-0016724

Equation form expr-0f1838a326f8a201

f'\colon \Nat \to \Nat

Read as: f prime from the natural numbers to the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f prime from the natural numbers to the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016763

Equation form expr-0f2246bcf7e13430

f\colon \Nat^k \pto \Nat

Read as: f from the natural numbers superscript k partially maps to the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f from the natural numbers superscript k partially maps to the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016674

Equation form expr-0f2dba005a3a3df0

\Sigma \cup \Sigma'

Read as: capital sigma union capital sigma prime

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: capital sigma union capital sigma prime

1 occurrence in this chapter

Occurrence projected-formula-0016731

Equation form expr-0fab8c9c7c3b2de1

C'

Read as: C prime

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C prime

2 occurrences in this chapter

Equation form expr-1062df87877ed5bd

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial, state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [below of=A] {$h$}; \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{N}} (C) (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{R}} (B) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (A); \end{tikzpicture}

Read as: State diagram. Purpose: Sends even input to an accepting halt state while odd input continues right on blanks. Initial state: state q sub zero. States: state q sub zero, state q sub one, state h. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, stay put, and enter state h. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. States with no outgoing transition shown are state h

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Sends even input to an accepting halt state while odd input continues right on blanks. Initial state: state q sub zero. States: state q sub zero, state q sub one, state h. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, stay put, and enter state h. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. States with no outgoing transition shown are state h

1 occurrence in this chapter

Occurrence projected-formula-0016686

Equation form expr-10a22b40fed94021

m' = m + 1

Read as: m prime equals m plus one

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: m prime equals m plus one

1 occurrence in this chapter

Occurrence projected-formula-0016550

Equation form expr-10d5524dfcfac13f

\delta(q, \sigma)

Read as: delta open parenthesis q comma sigma close parenthesis

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma sigma close parenthesis

2 occurrences in this chapter

Equation form expr-1106bdb37eb0451f

m' = m - 1

Read as: m prime equals m minus one

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: m prime equals m minus one

1 occurrence in this chapter

Occurrence projected-formula-0016546

Equation form expr-139c7c04318de35e

n = 0

Read as: n equals zero

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: n equals zero

1 occurrence in this chapter

Occurrence projected-formula-0016600

Equation form expr-1595cba2c531c586

C_k = \tuple{C, m, q}

Read as: C sub k equals the tuple C comma m comma q

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C sub k equals the tuple C comma m comma q

1 occurrence in this chapter

Occurrence projected-formula-0016575

Equation form expr-1726efa30de0e565

f\colon \Nat^k \to \Nat^m

Read as: f from the natural numbers superscript k to the natural numbers superscript m

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f from the natural numbers superscript k to the natural numbers superscript m

1 occurrence in this chapter

Occurrence projected-formula-0016609

Equation form expr-189f40034be7a199

j

Read as: j

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: j

1 occurrence in this chapter

Occurrence projected-formula-0016588

Equation form expr-1a75aa07bc108eaf

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [right of=B] {$q_2$}; \node[state] (D) [below left of=C] {$q_3$}; \node[state] (E) [below left of=D] {$q_4$}; \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C) (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D) (D) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D) edge node[left, xshift=-2mm] {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (E); \end{tikzpicture}

Read as: State diagram. Purpose: Runs unary addition and then returns the head to the start of the output. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state q sub four. States with no outgoing transition shown are state q sub four

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Runs unary addition and then returns the head to the start of the output. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state q sub four. States with no outgoing transition shown are state q sub four

1 occurrence in this chapter

Occurrence projected-formula-0016755

Equation form expr-1b141b13218a74bd

\delta(q_0, \TMblank) = \tuple{q_6,\TMblank,\TMstay}

Read as: delta open parenthesis q sub zero comma blank symbol close parenthesis equals the tuple q sub six comma blank symbol comma stay put

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q sub zero comma blank symbol close parenthesis equals the tuple q sub six comma blank symbol comma stay put

1 occurrence in this chapter

Occurrence projected-formula-0016648

Equation form expr-1b16b1df538ba12d

n

Read as: n

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: n

6 occurrences in this chapter

Equation form expr-1b8340cbc4763167

f\colon \Nat^k \to \Nat

Read as: f from the natural numbers superscript k to the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f from the natural numbers superscript k to the natural numbers

2 occurrences in this chapter

Equation form expr-1d040329b9461ca1

M' = \tuple{Q', \Sigma', q_0', \delta'}

Read as: M prime equals the tuple Q prime comma capital sigma prime comma q sub zero prime comma delta prime

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: M prime equals the tuple Q prime comma capital sigma prime comma q sub zero prime comma delta prime

1 occurrence in this chapter

Occurrence projected-formula-0016720

Equation form expr-1f2ac6a694c8f6d0

0+0

Read as: zero plus zero

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: zero plus zero

1 occurrence in this chapter

Occurrence projected-formula-0016623

Equation form expr-1fc85b244da75a8c

m>0

Read as: m is greater than zero

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: m is greater than zero

1 occurrence in this chapter

Occurrence projected-formula-0016547

Equation form expr-1ff81171cca05a02

\TMendtape'

Read as: left end marker prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: left end marker prime

1 occurrence in this chapter

Occurrence projected-formula-0016790

Equation form expr-21a3189658821b30

\TMright

Read as: move right

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: move right

1 occurrence in this chapter

Occurrence projected-formula-0016371

Equation form expr-21eb3ede7596da90

ABBAABBA

Read as: string capital A capital B capital B capital A capital A capital B capital B capital A

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital B capital B capital A capital A capital B capital B capital A

1 occurrence in this chapter

Occurrence projected-formula-0016486

Equation form expr-2206169dbaa7fc7a

\delta(q, \sigma) = \tuple{h, \sigma, N}

Read as: delta open parenthesis q comma sigma close parenthesis equals the tuple h comma sigma comma stay put

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma sigma close parenthesis equals the tuple h comma sigma comma stay put

1 occurrence in this chapter

Occurrence projected-formula-0016702

Equation form expr-22b0da8ed52b3e4f

D = L

Read as: movement direction D is left

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: movement direction D is left

1 occurrence in this chapter

Occurrence projected-formula-0016545

Equation form expr-26efcd74927066a7

\TMstroke^{n_1}\concat\TMblank\concat \dots \concat\TMblank\concat\TMstroke^{n_k}

Read as: stroke symbol superscript n sub one concatenated with blank symbol concatenated with and so on concatenated with blank symbol concatenated with stroke symbol superscript n sub k

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: stroke symbol superscript n sub one concatenated with blank symbol concatenated with and so on concatenated with blank symbol concatenated with stroke symbol superscript n sub k

1 occurrence in this chapter

Occurrence projected-formula-0016676

Equation form expr-2728b39ca4b8ad6f

m' = m

Read as: m prime equals m

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: m prime equals m

1 occurrence in this chapter

Occurrence projected-formula-0016552

Equation form expr-27ac167fc3479b9f

\len{C'} = \len{C} + 1

Read as: the length of C prime equals the length of C plus one

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: the length of C prime equals the length of C plus one

1 occurrence in this chapter

Occurrence projected-formula-0016554

Equation form expr-28b6406ccead341b

q'

Read as: q prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q prime

1 occurrence in this chapter

Occurrence projected-formula-0016373

Equation form expr-29ed7ea49366ffde

f'(m)

Read as: f prime open parenthesis m close parenthesis

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: f prime open parenthesis m close parenthesis

1 occurrence in this chapter

Occurrence projected-formula-0016770

Equation form expr-2c8977c1bd8be6aa

f(x) = 2x

Read as: f open parenthesis x close parenthesis equals two times x

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis x close parenthesis equals two times x

4 occurrences in this chapter

Equation form expr-2c8d721465c10b08

BABAA

Read as: string capital B capital A capital B capital A capital A

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital B capital A capital B capital A capital A

1 occurrence in this chapter

Occurrence projected-formula-0016497

Equation form expr-2c9b5e4cd4fb3cdf

j \in \Nat

Read as: j is in the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: j is in the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016586

Equation form expr-2d711642b726b044

x

Read as: x

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: x

2 occurrences in this chapter

Equation form expr-2ddd14c1a66d823b

M \frown M

Read as: M followed by M

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: M followed by M

1 occurrence in this chapter

Occurrence projected-formula-0016774

Equation form expr-2f8ea0f6e95594bb

AABB

Read as: string capital A capital A capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016476

Equation form expr-2ffe9a7fc74d03f3

\delta(q,\TMendtape) = \tuple{q', \TMendtape, x}

Read as: delta open parenthesis q comma left end marker close parenthesis equals the tuple q prime comma left end marker comma x

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma left end marker close parenthesis equals the tuple q prime comma left end marker comma x

1 occurrence in this chapter

Occurrence projected-formula-0016512

Equation form expr-307ff218fecd14ae

\TMstay

Read as: stay put

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: stay put

2 occurrences in this chapter

Equation form expr-3338a3070c07d805

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (B) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (A); \end{tikzpicture}

Read as: State diagram. Purpose: Recognizes even unary length by alternating between two states on strokes. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Recognizes even unary length by alternating between two states on strokes. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

1 occurrence in this chapter

Occurrence projected-formula-0016409

Equation form expr-3405ebdcecdf8e25

C_{i+1}

Read as: C sub i plus one

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: C sub i plus one

1 occurrence in this chapter

Occurrence projected-formula-0016571

Equation form expr-3695961c574a5a2e

\tuple{\TMendtape \frown I, 1, q_0}

Read as: the tuple left end marker followed by I comma one comma q sub zero

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: the tuple left end marker followed by I comma one comma q sub zero

1 occurrence in this chapter

Occurrence projected-formula-0016532

Equation form expr-3735037329f30119

\alpha\alpha

Read as: alpha followed by alpha

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: alpha followed by alpha

1 occurrence in this chapter

Occurrence projected-formula-0016484

Equation form expr-38a0391dcd1d703c

AABBBB

Read as: string capital A capital A capital B capital B capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital B capital B capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016500

Equation form expr-38fa11ff1384dcfd

\delta(q,\TMendtape) = \tuple{q',\sigma,\TMleft}

Read as: delta open parenthesis q comma left end marker close parenthesis equals the tuple q prime comma sigma comma move left

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma left end marker close parenthesis equals the tuple q prime comma sigma comma move left

1 occurrence in this chapter

Occurrence projected-formula-0016786

Equation form expr-3bbb211c2c6a98f4

\tuple{q_n, \sigma}

Read as: the tuple q sub n comma sigma

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub n comma sigma

1 occurrence in this chapter

Occurrence projected-formula-0016394

Equation form expr-3be5351fc214f61a

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (1) {$q_0$}; \node[state] (2) [right of=1] {$q_1$}; \node[state] (3) [right of=2] {$q_2$}; \node[state] (4) [below of=3] {$q_3$}; \node[state] (5) [left of=4] {$q_4$}; \node[state] (6) [left of=5] {$q_5$}; \path (1) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (2) (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (3) (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (3) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (4) (4) edge [loop below] node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (4) edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) (5) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (6) (6) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (6) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (1); \end{tikzpicture}

Read as: State diagram. Purpose: Doubles a unary block by erasing each input stroke and writing two output strokes. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five. Transition one: from state q sub zero, when reading stroke symbol, write blank symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub two. Transition four: from state q sub two, when reading stroke symbol, write stroke symbol, move right, and enter state q sub two. Transition five: from state q sub two, when reading blank symbol, write stroke symbol, move right, and enter state q sub three. Transition six: from state q sub three, when reading blank symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write stroke symbol, move left, and enter state q sub four. Transition nine: from state q sub four, when reading blank symbol, write blank symbol, move left, and enter state q sub five. Transition ten: from state q sub five, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition eleven: from state q sub five, when reading blank symbol, write blank symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Doubles a unary block by erasing each input stroke and writing two output strokes. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five. Transition one: from state q sub zero, when reading stroke symbol, write blank symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub two. Transition four: from state q sub two, when reading stroke symbol, write stroke symbol, move right, and enter state q sub two. Transition five: from state q sub two, when reading blank symbol, write stroke symbol, move right, and enter state q sub three. Transition six: from state q sub three, when reading blank symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write stroke symbol, move left, and enter state q sub four. Transition nine: from state q sub four, when reading blank symbol, write blank symbol, move left, and enter state q sub five. Transition ten: from state q sub five, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition eleven: from state q sub five, when reading blank symbol, write blank symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

1 occurrence in this chapter

Occurrence projected-formula-0016464

Equation form expr-3c6b357095745332

\delta(q_0, \TMstroke) = \tuple{q_1, \TMstroke, \TMright}

Read as: delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016418

Equation form expr-3e3cb3d5dc7f2dc5

\TMstroke

Read as: stroke symbol

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: stroke symbol

47 occurrences in this chapter

Equation form expr-3f39d5c348e5b79d

D

Read as: D

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: D

1 occurrence in this chapter

Occurrence projected-formula-0016369

Equation form expr-4222b21eadd5f7b9

C_i

Read as: C sub i

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C sub i

2 occurrences in this chapter

Equation form expr-43799e578f517d96

\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke \TMblank_0 \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol and is scanned in state q zero. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol and is scanned in state q zero. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016426

Equation form expr-44bed002316429d5

\delta(q, \sigma) = \tuple{q', \sigma', D}

Read as: delta open parenthesis q comma sigma close parenthesis equals the tuple q prime comma sigma prime comma D

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma sigma close parenthesis equals the tuple q prime comma sigma prime comma D

1 occurrence in this chapter

Occurrence projected-formula-0016541

Equation form expr-4503594975b3fa68

\tuple{3,2}

Read as: the tuple three comma two

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple three comma two

1 occurrence in this chapter

Occurrence projected-formula-0016622

Equation form expr-454349e422f05297

r

Read as: r

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: r

1 occurrence in this chapter

Occurrence projected-formula-0016687

Equation form expr-460c2532ccb4cba7

\TMstroke^n \concat \TMblank \concat \TMstroke^n

Read as: stroke symbol superscript n concatenated with blank symbol concatenated with stroke symbol superscript n

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: stroke symbol superscript n concatenated with blank symbol concatenated with stroke symbol superscript n

1 occurrence in this chapter

Occurrence projected-formula-0016718

Equation form expr-47012e484e6e011f

\tuple{q, \sigma, q', \sigma', D}

Read as: the tuple q comma sigma comma q prime comma sigma prime comma D

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q comma sigma comma q prime comma sigma prime comma D

1 occurrence in this chapter

Occurrence projected-formula-0016783

Equation form expr-4893e9df8b5496eb

\alpha

Read as: alpha

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: alpha

1 occurrence in this chapter

Occurrence projected-formula-0016481

Equation form expr-49e11df927e55a99

\fn{equality}(n,m) = \begin{cases} \text{1} & \text{if~$n = m$} \\ \text{0} & \text{if~$n \neq m$} \end{cases}

Read as: the function equality open parenthesis n comma m close parenthesis equals cases begin; row one: one, if n equals m; row two: zero, if n is not equal to m; cases end

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: the function equality open parenthesis n comma m close parenthesis equals cases begin; row one: one, if n equals m; row two: zero, if n is not equal to m; cases end

1 occurrence in this chapter

Occurrence projected-formula-0016661

Equation form expr-4a77ffe628ff771a

q_n

Read as: q sub n

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub n

1 occurrence in this chapter

Occurrence projected-formula-0016392

Equation form expr-4adf25bcff014318

\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol and is scanned in state q zero. cell four contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol and is scanned in state q zero. cell four contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016432

Equation form expr-4ae81572f06e1b88

Q

Read as: Q

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: Q

1 occurrence in this chapter

Occurrence projected-formula-0016503

Equation form expr-4b03e632ba62f5bf

f(x,y) = x+y

Read as: f open parenthesis x comma y close parenthesis equals x plus y

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis x comma y close parenthesis equals x plus y

1 occurrence in this chapter

Occurrence projected-formula-0016621

Equation form expr-4c18c30d6847add5

D = R

Read as: movement direction D is right

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: movement direction D is right

1 occurrence in this chapter

Occurrence projected-formula-0016549

Equation form expr-4d95ab92bdb1dbe9

\min

Read as: minimum

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: minimum

1 occurrence in this chapter

Occurrence projected-formula-0016669

Equation form expr-4e3ef93735fb440d

m'=0

Read as: m prime equals zero

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: m prime equals zero

1 occurrence in this chapter

Occurrence projected-formula-0016548

Equation form expr-531ccc2c7a226e63

\{\TMendtape,\TMblank, A, B\}

Read as: the tape alphabet containing the left end marker, blank symbol, capital A symbol, and capital B symbol

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: the tape alphabet containing the left end marker, blank symbol, capital A symbol, and capital B symbol

4 occurrences in this chapter

Equation form expr-54bf1f019467d845

ABBABB

Read as: string capital A capital B capital B capital A capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital B capital B capital A capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016499

Equation form expr-54c22f2da0cbc6dc

C'(i) = C(i)

Read as: C prime open parenthesis i close parenthesis equals C open parenthesis i close parenthesis

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C prime open parenthesis i close parenthesis equals C open parenthesis i close parenthesis

1 occurrence in this chapter

Occurrence projected-formula-0016562

Equation form expr-54fe7cd85da4d651

\tuple{q_3, 0, \TMright}

Read as: the tuple q sub three comma zero comma move right

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub three comma zero comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016387

Equation form expr-559aead08264d579

A

Read as: capital A symbol

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: capital A symbol

10 occurrences in this chapter

Equation form expr-567143eca8ae6c73

\tuple{q_1, \TMstroke, \TMright}

Read as: the tuple q sub one comma stroke symbol comma move right

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: the tuple q sub one comma stroke symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016405

Equation form expr-5afa20230f875253

n \in \Nat

Read as: n is in the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: n is in the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016598

Equation form expr-5b1f8f03007b9e86

\min(x,y)

Read as: minimum open parenthesis x comma y close parenthesis

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: minimum open parenthesis x comma y close parenthesis

1 occurrence in this chapter

Occurrence projected-formula-0016664

Equation form expr-5b81b8dff6f867f7

i \neq m

Read as: i is not equal to m

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: i is not equal to m

1 occurrence in this chapter

Occurrence projected-formula-0016561

Equation form expr-5df1ab55356aa8f5

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (A) (B) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (B) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (A); \end{tikzpicture}

Read as: State diagram. Purpose: Adds a blank loop in the even state so every relevant state-symbol pair has a transition and the machine never halts. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, move right, and enter state q sub zero. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Adds a blank loop in the even state so every relevant state-symbol pair has a transition and the machine never halts. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, move right, and enter state q sub zero. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. Every displayed state has at least one outgoing transition

1 occurrence in this chapter

Occurrence projected-formula-0016442

Equation form expr-5e3c127a36e7b99d

\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMstroke \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol and is scanned in state q zero. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol and is scanned in state q zero. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016424

Equation form expr-5f4f5dddb216597b

AAABB

Read as: string capital A capital A capital A capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital A capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016498

Equation form expr-5fbdec7a8054884c

AABBAABB

Read as: string capital A capital A capital B capital B capital A capital A capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital B capital B capital A capital A capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016479

Equation form expr-5feceb66ffc86f38

0

Read as: zero

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: zero

12 occurrences in this chapter

Equation form expr-60e0e41977835b02

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (6) {$q_6$}; \node[state] (7) [right of=6] {$q_7$}; \node[state] (8) [right of=7] {$q_8$}; \node[state] (9) [below of=8] {$q_9$}; \node[state] (10) [left of=9] {$q_{10}$}; \node[state] (11) [left of=10] {$q_{11}$}; \node[state] (12) [below of=11] {$q_{12}$}; \node[state] (13) [right of=12] {$q_{13}$}; \node[state] (14) [right of=13] {$q_{14}$}; \path (6) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (7) (7) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (7) edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (8) (8) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (8) edge node {\TMtrans{\TMblank}{\TMendtape}{\TMleft}} (9) (9) edge [loop right] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (9) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (10) (10) edge node[above] {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (11) (11) edge [loop above] node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (11) edge node[left] {\begin{tabular}{@{}l@{}} \TMtrans{\TMendtape}{\TMendtape}{\TMright}\\ \TMtrans{\TMstroke}{\TMstroke}{\TMright} \end{tabular}} (12) (12) edge node[] {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (13) (13) edge [loop below] node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (13) edge node[sloped] {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (11) (13) edge node {\TMtrans{\TMendtape}{\TMblank}{\TMstay}} (14); \end{tikzpicture}

Read as: State diagram. Purpose: Moves a block of strokes left and removes the temporary right boundary marker. Initial state: state q sub six. States: state q sub six, state q sub seven, state q sub eight, state q sub nine, state q sub ten, state q sub eleven, state q sub twelve, state q sub thirteen, state q sub fourteen. Transition one: from state q sub six, when reading blank symbol, write blank symbol, move right, and enter state q sub seven. Transition two: from state q sub seven, when reading blank symbol, write blank symbol, move right, and enter state q sub seven. Transition three: from state q sub seven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub eight. Transition four: from state q sub eight, when reading stroke symbol, write stroke symbol, move right, and enter state q sub eight. Transition five: from state q sub eight, when reading blank symbol, write left end marker, move left, and enter state q sub nine. Transition six: from state q sub nine, when reading stroke symbol, write stroke symbol, move left, and enter state q sub nine. Transition seven: from state q sub nine, when reading blank symbol, write blank symbol, move right, and enter state q sub ten. Transition eight: from state q sub ten, when reading stroke symbol, write blank symbol, move left, and enter state q sub eleven. Transition nine: from state q sub eleven, when reading blank symbol, write blank symbol, move left, and enter state q sub eleven. Transition ten: from state q sub eleven, when reading left end marker, write left end marker, move right, and enter state q sub twelve. Transition eleven: from state q sub eleven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub twelve. Transition twelve: from state q sub twelve, when reading blank symbol, write stroke symbol, move right, and enter state q sub thirteen. Transition thirteen: from state q sub thirteen, when reading blank symbol, write blank symbol, move right, and enter state q sub thirteen. Transition fourteen: from state q sub thirteen, when reading stroke symbol, write blank symbol, move left, and enter state q sub eleven. Transition fifteen: from state q sub thirteen, when reading left end marker, write blank symbol, stay put, and enter state q sub fourteen. States with no outgoing transition shown are state q sub fourteen

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Moves a block of strokes left and removes the temporary right boundary marker. Initial state: state q sub six. States: state q sub six, state q sub seven, state q sub eight, state q sub nine, state q sub ten, state q sub eleven, state q sub twelve, state q sub thirteen, state q sub fourteen. Transition one: from state q sub six, when reading blank symbol, write blank symbol, move right, and enter state q sub seven. Transition two: from state q sub seven, when reading blank symbol, write blank symbol, move right, and enter state q sub seven. Transition three: from state q sub seven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub eight. Transition four: from state q sub eight, when reading stroke symbol, write stroke symbol, move right, and enter state q sub eight. Transition five: from state q sub eight, when reading blank symbol, write left end marker, move left, and enter state q sub nine. Transition six: from state q sub nine, when reading stroke symbol, write stroke symbol, move left, and enter state q sub nine. Transition seven: from state q sub nine, when reading blank symbol, write blank symbol, move right, and enter state q sub ten. Transition eight: from state q sub ten, when reading stroke symbol, write blank symbol, move left, and enter state q sub eleven. Transition nine: from state q sub eleven, when reading blank symbol, write blank symbol, move left, and enter state q sub eleven. Transition ten: from state q sub eleven, when reading left end marker, write left end marker, move right, and enter state q sub twelve. Transition eleven: from state q sub eleven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub twelve. Transition twelve: from state q sub twelve, when reading blank symbol, write stroke symbol, move right, and enter state q sub thirteen. Transition thirteen: from state q sub thirteen, when reading blank symbol, write blank symbol, move right, and enter state q sub thirteen. Transition fourteen: from state q sub thirteen, when reading stroke symbol, write blank symbol, move left, and enter state q sub eleven. Transition fifteen: from state q sub thirteen, when reading left end marker, write blank symbol, stay put, and enter state q sub fourteen. States with no outgoing transition shown are state q sub fourteen

1 occurrence in this chapter

Occurrence projected-formula-0016653

Equation form expr-62c66a7a5dd70c31

m

Read as: m

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: m

7 occurrences in this chapter

Equation form expr-6562529bf967e9a8

f(n_1, \dots, n_k) = m

Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis equals m

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis equals m

1 occurrence in this chapter

Occurrence projected-formula-0016678

Equation form expr-65bd2a5f98a355e5

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [right of=B] {$q_2$}; \node[state] (D) [below left of=C] {$q_3$}; \node[state] (E) [below left of=D] {$q_4$}; \node[state] (2) [right of=E] {$q_5$}; \node[state] (3) [right of=2] {$q_6$}; \node[state] (4) [below of=3] {$q_7$}; \node[state] (5) [left of=4] {$q_8$}; \node[state] (6) [left of=5] {$q_9$}; \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C) (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D) (D) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D) edge node[left, xshift=-2mm] {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (E) (E) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (2) (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (3) (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (3) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (4) (4) edge [loop below] node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (4) edge node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) (5) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (6) (6) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (6) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (E); \end{tikzpicture}

Read as: State diagram. Purpose: Runs addition, repositions the head, and continues into a renamed doubler phase. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five, state q sub six, state q sub seven, state q sub eight, state q sub nine. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write blank symbol, move right, and enter state q sub five. Transition nine: from state q sub five, when reading stroke symbol, write stroke symbol, move right, and enter state q sub five. Transition ten: from state q sub five, when reading blank symbol, write blank symbol, move right, and enter state q sub six. Transition eleven: from state q sub six, when reading stroke symbol, write stroke symbol, move right, and enter state q sub six. Transition twelve: from state q sub six, when reading blank symbol, write stroke symbol, move right, and enter state q sub seven. Transition thirteen: from state q sub seven, when reading blank symbol, write stroke symbol, move left, and enter state q sub seven. Transition fourteen: from state q sub seven, when reading stroke symbol, write stroke symbol, move left, and enter state q sub eight. Transition fifteen: from state q sub eight, when reading stroke symbol, write stroke symbol, move left, and enter state q sub eight. Transition sixteen: from state q sub eight, when reading blank symbol, write blank symbol, move left, and enter state q sub nine. Transition seventeen: from state q sub nine, when reading stroke symbol, write stroke symbol, move left, and enter state q sub nine. Transition eighteen: from state q sub nine, when reading blank symbol, write blank symbol, move right, and enter state q sub four. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Runs addition, repositions the head, and continues into a renamed doubler phase. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five, state q sub six, state q sub seven, state q sub eight, state q sub nine. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write blank symbol, move right, and enter state q sub five. Transition nine: from state q sub five, when reading stroke symbol, write stroke symbol, move right, and enter state q sub five. Transition ten: from state q sub five, when reading blank symbol, write blank symbol, move right, and enter state q sub six. Transition eleven: from state q sub six, when reading stroke symbol, write stroke symbol, move right, and enter state q sub six. Transition twelve: from state q sub six, when reading blank symbol, write stroke symbol, move right, and enter state q sub seven. Transition thirteen: from state q sub seven, when reading blank symbol, write stroke symbol, move left, and enter state q sub seven. Transition fourteen: from state q sub seven, when reading stroke symbol, write stroke symbol, move left, and enter state q sub eight. Transition fifteen: from state q sub eight, when reading stroke symbol, write stroke symbol, move left, and enter state q sub eight. Transition sixteen: from state q sub eight, when reading blank symbol, write blank symbol, move left, and enter state q sub nine. Transition seventeen: from state q sub nine, when reading stroke symbol, write stroke symbol, move left, and enter state q sub nine. Transition eighteen: from state q sub nine, when reading blank symbol, write blank symbol, move right, and enter state q sub four. Every displayed state has at least one outgoing transition

1 occurrence in this chapter

Occurrence projected-formula-0016759

Equation form expr-67f98a44ed3788cd

Q \cup Q'

Read as: Q union Q prime

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: Q union Q prime

1 occurrence in this chapter

Occurrence projected-formula-0016730

Equation form expr-688eed70a27e98ff

q_1

Read as: q sub one

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub one

8 occurrences in this chapter

Equation form expr-690ba742bc2d92dd

\TMstroke^{m}

Read as: a block of m stroke symbols

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: a block of m stroke symbols

1 occurrence in this chapter

Occurrence projected-formula-0016677

Equation form expr-693b8d364d85d740

f(x) = x+1

Read as: f open parenthesis x close parenthesis equals x plus one

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis x close parenthesis equals x plus one

1 occurrence in this chapter

Occurrence projected-formula-0016716

Equation form expr-6a5455bf52bd837a

\frown

Read as: followed by

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: followed by

1 occurrence in this chapter

Occurrence projected-formula-0016533

Equation form expr-6a766438d1de2cc9

n+m

Read as: n plus m

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: n plus m

1 occurrence in this chapter

Occurrence projected-formula-0016614

Equation form expr-6b23c0d5f35d1b11

C

Read as: C

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: C

3 occurrences in this chapter

Equation form expr-6b86b273ff34fce1

1

Read as: one

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: one

12 occurrences in this chapter

Equation form expr-6be6d0cc0e787a3d

n > m

Read as: n is greater than m

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: n is greater than m

1 occurrence in this chapter

Occurrence projected-formula-0016659

Equation form expr-6c2cd0ad72672bdd

q_0 \in Q

Read as: q sub zero is in Q

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: q sub zero is in Q

1 occurrence in this chapter

Occurrence projected-formula-0016507

Equation form expr-6c60d95cbdaf60e9

2x=0

Read as: two times x equals zero

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: two times x equals zero

1 occurrence in this chapter

Occurrence projected-formula-0016656

Equation form expr-744f9709331b96fc

\delta''

Read as: delta prime prime

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta prime prime

1 occurrence in this chapter

Occurrence projected-formula-0016733

Equation form expr-7451894f826e7959

f(x) = x+2

Read as: f open parenthesis x close parenthesis equals x plus two

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis x close parenthesis equals x plus two

1 occurrence in this chapter

Occurrence projected-formula-0016772

Equation form expr-74a85ea6f81aec26

f\colon\Nat^n \to \Nat

Read as: f from the natural numbers superscript n to the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f from the natural numbers superscript n to the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016715

Equation form expr-74b69619e3b94f97

\TMtrans{\TMblank}{\TMblank}{\TMstay}

Read as: transition triple blank symbol, blank symbol, stay put

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: transition triple blank symbol, blank symbol, stay put

1 occurrence in this chapter

Occurrence projected-formula-0016651

Equation form expr-766193ab33534da6

\TMstroke^{f(n_1, \dots, n_k)}

Read as: a block of f open parenthesis n sub one comma and so on comma n sub k close parenthesis stroke symbols

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: a block of f open parenthesis n sub one comma and so on comma n sub k close parenthesis stroke symbols

1 occurrence in this chapter

Occurrence projected-formula-0016607

Equation form expr-7697111ef854f720

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (0) {$q_0$}; \node[state] (1) [above of=0] {$q_1$}; \node[state] (2) [above of=1] {$q_2$}; \node[state] (3) [right of=2] {$q_3$}; \node[state] (4) [below of=3] {$q_4$}; \node[state] (5) [below of=4] {$q_5$}; \node[state] (6) [above right of=4] {$q_6$}; \node[state] (7) [below of=6] {$q_7$}; \node[state] (8) [below of=7] {$q_8$}; \path (0) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMright}} (1) (1) edge [loop left] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (1) edge node {\TMtrans{\TMblank}{\TMblank}{\TMright}} (2) (2) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (2) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMleft}} (3) (3) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (3) edge node[left] {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (4) (4) edge node[left] {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) (5) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (5) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (0) (4) edge node[sloped] {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (6) (6) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (7) (7) edge [loop right] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (7) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (8) (8) edge [loop right] node {\TMtrans{\TMstroke}{\TMblank}{\TMstay}} (8); \end{tikzpicture}

Read as: State diagram. Purpose: Computes doubling while maintaining a contiguous output block. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five, state q sub six, state q sub seven, state q sub eight. Transition one: from state q sub zero, when reading stroke symbol, write blank symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub two. Transition four: from state q sub two, when reading stroke symbol, write stroke symbol, move right, and enter state q sub two. Transition five: from state q sub two, when reading blank symbol, write stroke symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading blank symbol, write blank symbol, move left, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition nine: from state q sub five, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition ten: from state q sub five, when reading blank symbol, write stroke symbol, move right, and enter state q sub zero. Transition eleven: from state q sub four, when reading blank symbol, write stroke symbol, move right, and enter state q sub six. Transition twelve: from state q sub six, when reading blank symbol, write stroke symbol, move right, and enter state q sub seven. Transition thirteen: from state q sub seven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub seven. Transition fourteen: from state q sub seven, when reading blank symbol, write blank symbol, move left, and enter state q sub eight. Transition fifteen: from state q sub eight, when reading stroke symbol, write blank symbol, stay put, and enter state q sub eight. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Computes doubling while maintaining a contiguous output block. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state q sub four, state q sub five, state q sub six, state q sub seven, state q sub eight. Transition one: from state q sub zero, when reading stroke symbol, write blank symbol, move right, and enter state q sub one. Transition two: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading blank symbol, write blank symbol, move right, and enter state q sub two. Transition four: from state q sub two, when reading stroke symbol, write stroke symbol, move right, and enter state q sub two. Transition five: from state q sub two, when reading blank symbol, write stroke symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading blank symbol, write blank symbol, move left, and enter state q sub four. Transition eight: from state q sub four, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition nine: from state q sub five, when reading stroke symbol, write stroke symbol, move left, and enter state q sub five. Transition ten: from state q sub five, when reading blank symbol, write stroke symbol, move right, and enter state q sub zero. Transition eleven: from state q sub four, when reading blank symbol, write stroke symbol, move right, and enter state q sub six. Transition twelve: from state q sub six, when reading blank symbol, write stroke symbol, move right, and enter state q sub seven. Transition thirteen: from state q sub seven, when reading stroke symbol, write stroke symbol, move right, and enter state q sub seven. Transition fourteen: from state q sub seven, when reading blank symbol, write blank symbol, move left, and enter state q sub eight. Transition fifteen: from state q sub eight, when reading stroke symbol, write blank symbol, stay put, and enter state q sub eight. Every displayed state has at least one outgoing transition

1 occurrence in this chapter

Occurrence projected-formula-0016638

Equation form expr-76a8c8c02bf83b7a

M'

Read as: M prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: M prime

9 occurrences in this chapter

Equation form expr-794d66ff4ebd363e

x=0

Read as: x equals zero

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: x equals zero

2 occurrences in this chapter

Equation form expr-79d4c7f9c8579543

\Nat

Read as: the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: the natural numbers

2 occurrences in this chapter

Equation form expr-79fb2f9e87142d2a

h \in Q

Read as: h is in Q

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: h is in Q

1 occurrence in this chapter

Occurrence projected-formula-0016683

Equation form expr-7d33b3d4e6b7214d

m \in \PosInt

Read as: m is a positive integer

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: m is a positive integer

1 occurrence in this chapter

Occurrence projected-formula-0016663

Equation form expr-7f24e9d9ba0e99c1

\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol and is scanned in state q one. cell three contains stroke symbol. cell four contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol and is scanned in state q one. cell three contains stroke symbol. cell four contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016431

Equation form expr-80ea94cdc6e8a55a

AAABBB

Read as: string capital A capital A capital A capital B capital B capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital A capital B capital B capital B

1 occurrence in this chapter

Occurrence projected-formula-0016477

Equation form expr-8254c329a92850f6

k

Read as: k

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: k

2 occurrences in this chapter

Equation form expr-8389fa6c231e5771

M \frown M'

Read as: M followed by M prime

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: M followed by M prime

3 occurrences in this chapter

Equation form expr-840e7fd7cd9f5514

M = \tuple{Q, \Sigma, q_0, \delta}

Read as: M equals the tuple Q comma capital sigma comma q sub zero comma delta

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: M equals the tuple Q comma capital sigma comma q sub zero comma delta

2 occurrences in this chapter

Equation form expr-8438925a75f710ec

2n

Read as: two times n

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: two times n

2 occurrences in this chapter

Equation form expr-886a4448ba3cc8d9

f(n,m) = n - m

Read as: f open parenthesis n comma m close parenthesis equals n minus m

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis n comma m close parenthesis equals n minus m

1 occurrence in this chapter

Occurrence projected-formula-0016660

Equation form expr-892ac32e38bd154a

\tuple{q, \sigma, q'', \sigma'', D'}

Read as: the tuple q comma sigma comma q prime prime comma sigma prime prime comma D prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q comma sigma comma q prime prime comma sigma prime prime comma D prime

1 occurrence in this chapter

Occurrence projected-formula-0016784

Equation form expr-89d00398f6e2cf73

Q & = \{ q_0, q_1 \} \\ \Sigma & = \{ \TMendtape, \TMblank, \TMstroke \}, \\ \delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\ \delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\ \delta(q_1, \TMblank) & = \tuple{q_1, \TMblank, \TMright}.

Read as: Q equals q sub zero comma q sub one next row capital sigma equals left end marker comma blank symbol comma stroke symbol comma next row delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: Q equals q sub zero comma q sub one next row capital sigma equals left end marker comma blank symbol comma stroke symbol comma next row delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016516

Equation form expr-8a0af28cfea61316

\tuple{C', m', q'}

Read as: the tuple C prime comma m prime comma q prime

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: the tuple C prime comma m prime comma q prime

1 occurrence in this chapter

Occurrence projected-formula-0016535

Equation form expr-8ae9808cb0f6e77d

q_3

Read as: q sub three

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub three

1 occurrence in this chapter

Occurrence projected-formula-0016391

Equation form expr-8be170e0a92cf97a

\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMstroke \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol and is scanned in state q one. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol and is scanned in state q one. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016420

Equation form expr-8d14d1dec04501e0

\min(3,5)=3

Read as: minimum open parenthesis three comma five close parenthesis equals three

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: minimum open parenthesis three comma five close parenthesis equals three

1 occurrence in this chapter

Occurrence projected-formula-0016670

Equation form expr-8e35c2cd3bf6641b

q

Read as: q

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q

4 occurrences in this chapter

Equation form expr-94e0e5b74ae8c318

\tuple{q_1, 1}

Read as: the tuple q sub one comma one

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub one comma one

1 occurrence in this chapter

Occurrence projected-formula-0016382

Equation form expr-95fa83ebb632f8c5

\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke_1 \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol and is scanned in state q one. cell five contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol and is scanned in state q one. cell five contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016425

Equation form expr-96e7013f72f6233c

\min(20,16)=16

Read as: minimum open parenthesis twenty comma sixteen close parenthesis equals sixteen

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: minimum open parenthesis twenty comma sixteen close parenthesis equals sixteen

1 occurrence in this chapter

Occurrence projected-formula-0016671

Equation form expr-9c122ac6858d3be1

\delta(q_1, \TMblank) =\tuple{q_1, \TMblank, \TMright}

Read as: delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016437

Equation form expr-9c3245dfb4ac54c1

\sigma

Read as: sigma

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: sigma

7 occurrences in this chapter

Equation form expr-9d7103ac3526e8f6

m \in \Nat

Read as: m is in the natural numbers

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: m is in the natural numbers

1 occurrence in this chapter

Occurrence projected-formula-0016522

Equation form expr-9ddfa415125373dc

f(n_1, \dots, n_k)

Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis n sub one comma and so on comma n sub k close parenthesis

1 occurrence in this chapter

Occurrence projected-formula-0016681

Equation form expr-9eae08773384edb6

q \in Q'

Read as: q is in Q prime

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: q is in Q prime

1 occurrence in this chapter

Occurrence projected-formula-0016738

Equation form expr-a1fce4363854ff88

y

Read as: y

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: y

2 occurrences in this chapter

Equation form expr-a20db09b4ab0b0ba

C_0

Read as: C sub zero

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C sub zero

1 occurrence in this chapter

Occurrence projected-formula-0016567

Equation form expr-a2965900c61ab851

q_2

Read as: q sub two

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub two

2 occurrences in this chapter

Equation form expr-a38ee6a67de22a3d

\TMblank

Read as: blank symbol

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: blank symbol

27 occurrences in this chapter

Equation form expr-a4c7fd7f94be16fe

m'

Read as: m prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: m prime

1 occurrence in this chapter

Occurrence projected-formula-0016555

Equation form expr-a5183e47a3207b2d

\TMendtape

Read as: left end marker

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: left end marker

12 occurrences in this chapter

Equation form expr-a83dd0ccbffe39d0

I

Read as: I

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: I

4 occurrences in this chapter

Equation form expr-aa6d6c75d5e9831d

\TMendtape \TMstroke \TMstroke \TMstroke \TMblank_1 \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains blank symbol and is scanned in state q one. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains blank symbol and is scanned in state q one. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016433

Equation form expr-aaa9402664f1a41f

h

Read as: h

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: h

7 occurrences in this chapter

Equation form expr-aaa9ea0d0b12c372

\tuple{C, m, q}

Read as: the tuple C comma m comma q

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: the tuple C comma m comma q

2 occurrences in this chapter

Equation form expr-aadb522a140a620a

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [below right of=B] {$q_2$}; \node[state] (D) [below left of=C] {$q_3$}; \node[state] (H) [left of=D] {$h$}; \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) (B) edge [loop below] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C) (C) edge node {\TMtrans{\TMstroke}{\TMblank}{\TMleft}} (D) (D) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMleft}} (D) edge node {\TMtrans{\TMendtape}{\TMendtape}{\TMright}} (H); \end{tikzpicture}

Read as: State diagram. Purpose: Adds cleanup and a unique halt state to unary addition. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state h. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state h. States with no outgoing transition shown are state h

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Adds cleanup and a unique halt state to unary addition. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two, state q sub three, state h. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, move left, and enter state q sub three. Transition six: from state q sub three, when reading stroke symbol, write stroke symbol, move left, and enter state q sub three. Transition seven: from state q sub three, when reading left end marker, write left end marker, move right, and enter state h. States with no outgoing transition shown are state h

1 occurrence in this chapter

Occurrence projected-formula-0016708

Equation form expr-b398f71af6865ec3

ABBA

Read as: string capital A capital B capital B capital A

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital B capital B capital A

1 occurrence in this chapter

Occurrence projected-formula-0016485

Equation form expr-b6081345cbdbecf7

C \in \Sigma^*

Read as: configuration tape string C is a finite string over tape alphabet capital sigma

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: configuration tape string C is a finite string over tape alphabet capital sigma

1 occurrence in this chapter

Occurrence projected-formula-0016520

Equation form expr-b62f6cbc82b02a3f

\tuple{q', \sigma', D}

Read as: the tuple q prime comma sigma prime comma D

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q prime comma sigma prime comma D

2 occurrences in this chapter

Equation form expr-b85c44ecbea9a6b2

\tuple{q, \sigma}

Read as: the tuple q comma sigma

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q comma sigma

1 occurrence in this chapter

Occurrence projected-formula-0016781

Equation form expr-b8a1bf1bab77ec11

\sigma'

Read as: sigma prime

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: sigma prime

2 occurrences in this chapter

Equation form expr-b8bbb3a7ebd17a45

q_0

Read as: q sub zero

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub zero

11 occurrences in this chapter

Equation form expr-b90a70b28b9c0c0a

\TMstroke^{n_1} \TMblank \TMstroke^{n_2} \TMblank \dots \TMblank \TMstroke^{n_k}

Read as: stroke symbol superscript n sub one blank symbol stroke symbol superscript n sub two blank symbol and so on blank symbol stroke symbol superscript n sub k

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: stroke symbol superscript n sub one blank symbol stroke symbol superscript n sub two blank symbol and so on blank symbol stroke symbol superscript n sub k

1 occurrence in this chapter

Occurrence projected-formula-0016606

Equation form expr-beba1876b0c41616

2(m+n)

Read as: two times the quantity m plus n

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: two times the quantity m plus n

1 occurrence in this chapter

Occurrence projected-formula-0016751

Equation form expr-c2a5776d77147484

m' = \len{C}

Read as: m prime equals the length of C

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: m prime equals the length of C

1 occurrence in this chapter

Occurrence projected-formula-0016553

Equation form expr-c42e9136cb1f4ff7

\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol and is scanned in state q zero. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol and is scanned in state q zero. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016430

Equation form expr-c4694f2e93d5c4e7

O

Read as: O

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: O

6 occurrences in this chapter

Equation form expr-c4c4c2ee23d0a94a

\delta(q,\TMendtape)

Read as: delta open parenthesis q comma left end marker close parenthesis

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q comma left end marker close parenthesis

1 occurrence in this chapter

Occurrence projected-formula-0016513

Equation form expr-c50128cf99c06e86

AAB

Read as: string capital A capital A capital B

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: string capital A capital A capital B

1 occurrence in this chapter

Occurrence projected-formula-0016478

Equation form expr-c6173ad7add4e2cd

\tuple{q,\sigma}

Read as: the tuple q comma sigma

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q comma sigma

1 occurrence in this chapter

Occurrence projected-formula-0016703

Equation form expr-c7c448a182459309

< \len{C}

Read as: is less than the length of C

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: is less than the length of C

1 occurrence in this chapter

Occurrence projected-formula-0016523

Equation form expr-c7cfd0787d1520d0

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [right of=B] {$q_2$}; \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMstay}} (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) (B) edge [loop above] node {\TMtrans{\TMstroke}{\TMstroke}{\TMright}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{\TMleft}} (C) (C) edge [loop above] node {\TMtrans{\TMstroke}{\TMblank}{\TMstay}} (C); \end{tikzpicture}

Read as: State diagram. Purpose: Shared addition state diagram whose exact chapter role is fixed in each occurrence. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, stay put, and enter state q sub two. Every displayed state has at least one outgoing transition

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Shared addition state diagram whose exact chapter role is fixed in each occurrence. Initial state: state q sub zero. States: state q sub zero, state q sub one, state q sub two. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, stay put, and enter state q sub one. Transition two: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition three: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition four: from state q sub one, when reading blank symbol, write blank symbol, move left, and enter state q sub two. Transition five: from state q sub two, when reading stroke symbol, write blank symbol, stay put, and enter state q sub two. Every displayed state has at least one outgoing transition

2 occurrences in this chapter

Equation form expr-cc097011c9aac4f0

q \in Q

Read as: q is in Q

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: q is in Q

3 occurrences in this chapter

Equation form expr-cecd4b28004f5558

\delta''(q,\sigma) = \begin{cases} \delta(q,\sigma) & \text{if $q \in Q$ and $\delta(q,\sigma)$ is defined}\\ \delta'(q,\sigma) & \text{if $q \in Q'$}\\ \tuple{q_0', \sigma, \TMstay} & \text{if $q \in Q$ and $\delta(q,\sigma)$ is undefined} \end{cases}

Read as: delta prime prime open parenthesis q comma sigma close parenthesis equals cases begin; row one: delta open parenthesis q comma sigma close parenthesis, if q is in Q and delta open parenthesis q comma sigma close parenthesis is defined; row two: delta prime open parenthesis q comma sigma close parenthesis, if q is in Q prime ; row three: the tuple q sub zero prime comma sigma comma stay put, if q is in Q and delta open parenthesis q comma sigma close parenthesis is undefined; cases end

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta prime prime open parenthesis q comma sigma close parenthesis equals cases begin; row one: delta open parenthesis q comma sigma close parenthesis, if q is in Q and delta open parenthesis q comma sigma close parenthesis is defined; row two: delta prime open parenthesis q comma sigma close parenthesis, if q is in Q prime ; row three: the tuple q sub zero prime comma sigma comma stay put, if q is in Q and delta open parenthesis q comma sigma close parenthesis is undefined; cases end

1 occurrence in this chapter

Occurrence projected-formula-0016734

Equation form expr-d203ba01eef4198c

\delta

Read as: delta

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta

2 occurrences in this chapter

Equation form expr-d2e515e2e7891e5e

\tuple{q_n,\sigma}

Read as: the tuple q sub n comma sigma

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub n comma sigma

1 occurrence in this chapter

Occurrence projected-formula-0016395

Equation form expr-d4735e3a265e16ee

2

Read as: two

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: two

1 occurrence in this chapter

Occurrence projected-formula-0016794

Equation form expr-d57034110e7c36c7

\langle Q, \Sigma, q_0, \delta\rangle

Read as: left angle bracket Q comma capital sigma comma q sub zero comma delta right angle bracket

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: left angle bracket Q comma capital sigma comma q sub zero comma delta right angle bracket

1 occurrence in this chapter

Occurrence projected-formula-0016502

Equation form expr-d5efec6e7d4e7dbf

\delta(q_1, \TMstroke) = \tuple{q_0, \TMstroke, \TMright}

Read as: delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016423

Equation form expr-d65d75b1e6562713

\Sigma

Read as: capital sigma

Means: Notation for a machine prime s state set, tape alphabet, or defining tuple. Read as: capital sigma

2 occurrences in this chapter

Equation form expr-d6fd93deefa78d7f

q_6

Read as: q sub six

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: q sub six

2 occurrences in this chapter

Equation form expr-d754edda96800b2e

i < \len{C}

Read as: i is less than the length of C

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: i is less than the length of C

1 occurrence in this chapter

Occurrence projected-formula-0016560

Equation form expr-dd917572acf72f4d

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \node[state] (C) [below of=A] {$h$}; \node[state] (D) [below of=B] {$r$}; \path (A) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (B) edge node {\TMtrans{\TMblank}{\TMblank}{N}} (C) (B) edge node {\TMtrans{\TMblank}{\TMblank}{N}} (D) edge [bend left] node {\TMtrans{\TMstroke}{\TMstroke}{R}} (A); \end{tikzpicture}

Read as: State diagram. Purpose: Sends even input to an accept state and odd input to a reject state. Initial state: state q sub zero. States: state q sub zero, state q sub one, state h, state r. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, stay put, and enter state h. Transition three: from state q sub one, when reading blank symbol, write blank symbol, stay put, and enter state r. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. States with no outgoing transition shown are state h, state r

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Sends even input to an accept state and odd input to a reject state. Initial state: state q sub zero. States: state q sub zero, state q sub one, state h, state r. Transition one: from state q sub zero, when reading stroke symbol, write stroke symbol, move right, and enter state q sub one. Transition two: from state q sub zero, when reading blank symbol, write blank symbol, stay put, and enter state h. Transition three: from state q sub one, when reading blank symbol, write blank symbol, stay put, and enter state r. Transition four: from state q sub one, when reading stroke symbol, write stroke symbol, move right, and enter state q sub zero. States with no outgoing transition shown are state h, state r

1 occurrence in this chapter

Occurrence projected-formula-0016688

Equation form expr-de1b5e90a53d43bf

\comp{f}{f'}

Read as: f prime after f

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f prime after f

1 occurrence in this chapter

Occurrence projected-formula-0016765

Equation form expr-de7d1b721a1e0632

i

Read as: i

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: i

1 occurrence in this chapter

Occurrence projected-formula-0016559

Equation form expr-dec716cbf4051e7b

\tuple{q_0, \TMblank}

Read as: the tuple q sub zero comma blank symbol

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: the tuple q sub zero comma blank symbol

1 occurrence in this chapter

Occurrence projected-formula-0016404

Equation form expr-df7e70e5021544f4

B

Read as: capital B symbol

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: capital B symbol

10 occurrences in this chapter

Equation form expr-e4028092e91f57fb

\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMstroke \TMblank \ldots

Read as: Tape configuration: left end marker. cell one contains stroke symbol and is scanned in state q zero. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

Means: A left-to-right tape snapshot; a subscript marks the scanned cell and current state. Read as: Tape configuration: left end marker. cell one contains stroke symbol and is scanned in state q zero. cell two contains stroke symbol. cell three contains stroke symbol. cell four contains stroke symbol. cell five contains blank symbol. then unshown tape squares continue to the right

1 occurrence in this chapter

Occurrence projected-formula-0016415

Equation form expr-e9b629a122ccc66f

\len{C'}=\len{C}

Read as: the length of C prime equals the length of C

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: the length of C prime equals the length of C

1 occurrence in this chapter

Occurrence projected-formula-0016558

Equation form expr-eada767cacb165a5

\TMblank^j

Read as: a block of j blank symbols

Means: Notation for tape symbols, concatenated strings, or unary blocks. Read as: a block of j blank symbols

1 occurrence in this chapter

Occurrence projected-formula-0016587

Equation form expr-ec9edaef8151b883

\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm, semithick] \tikzstyle{every state}=[fill=none,draw=black,text=black] \node[initial,state] (A) {$q_0$}; \node[state] (B) [right of=A] {$q_1$}; \path (A) edge node {\TMtrans{\TMblank}{\TMstroke}{\TMright}} (B); \end{tikzpicture}

Read as: State diagram. Purpose: Introduces how one arrow encodes reading a blank, writing a stroke, moving right, and entering the target state. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, move right, and enter state q sub one. States with no outgoing transition shown are state q sub one

Means: A complete source-order transition linearization of the displayed state diagram. Read as: State diagram. Purpose: Introduces how one arrow encodes reading a blank, writing a stroke, moving right, and entering the target state. Initial state: state q sub zero. States: state q sub zero, state q sub one. Transition one: from state q sub zero, when reading blank symbol, write stroke symbol, move right, and enter state q sub one. States with no outgoing transition shown are state q sub one

1 occurrence in this chapter

Occurrence projected-formula-0016399

Equation form expr-ed27913e8e82a1c7

\delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\ \delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\ \delta(q_1, \TMblank) & = \tuple{q_1, \TMblank, \TMright}

Read as: delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: delta open parenthesis q sub zero comma stroke symbol close parenthesis equals the tuple q sub one comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma stroke symbol close parenthesis equals the tuple q sub zero comma stroke symbol comma move right comma next row delta open parenthesis q sub one comma blank symbol close parenthesis equals the tuple q sub one comma blank symbol comma move right

1 occurrence in this chapter

Occurrence projected-formula-0016410

Equation form expr-edd07dadf1b50c1e

f(n,m) = n + m

Read as: f open parenthesis n comma m close parenthesis equals n plus m

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: f open parenthesis n comma m close parenthesis equals n plus m

1 occurrence in this chapter

Occurrence projected-formula-0016610

Equation form expr-ef016f0715e41073

C = \TMendtape \concat O \concat \TMblank^j

Read as: C equals left end marker concatenated with O concatenated with blank symbol superscript j

Means: Notation for tape content, head position, machine state, or a step in a run. Read as: C equals left end marker concatenated with O concatenated with blank symbol superscript j

1 occurrence in this chapter

Occurrence projected-formula-0016585

Equation form expr-f0cc1fc64ad2dbf3

\min(4,4)=4

Read as: minimum open parenthesis four comma four close parenthesis equals four

Means: A function type, value, or arithmetic relationship in the machine-computation convention. Read as: minimum open parenthesis four comma four close parenthesis equals four

1 occurrence in this chapter

Occurrence projected-formula-0016672

Equation form expr-f26a8655ab7754cb

\tuple{Q, \Sigma, q_0, \delta}

Read as: the tuple Q comma capital sigma comma q sub zero comma delta

Means: Transition notation specifying a current state and symbol or the resulting state, written symbol, and head movement. Read as: the tuple Q comma capital sigma comma q sub zero comma delta

1 occurrence in this chapter

Occurrence projected-formula-0016515

Equation form expr-f2b7ca713580f6e4

D = N

Read as: movement direction D is stay put

Means: An equation, comparison, or membership claim fixed by the surrounding source sentence. Read as: movement direction D is stay put

1 occurrence in this chapter

Occurrence projected-formula-0016551

Equation form expr-f5614b54d69f04e3

\tuple{q_2, 0, \TMstay}

Read as: the tuple q sub two comma zero comma stay put

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub two comma zero comma stay put

1 occurrence in this chapter

Occurrence projected-formula-0016383

Equation form expr-f56502b41b1be050

\tuple{q_2, 0}

Read as: the tuple q sub two comma zero

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: the tuple q sub two comma zero

1 occurrence in this chapter

Occurrence projected-formula-0016388

Equation form expr-f9d5192eee9a80ca

\TMleft

Read as: move left

Means: A Turing-machine variable or term whose role is fixed by its exact source context. Read as: move left

1 occurrence in this chapter

Occurrence projected-formula-0016370

Equation form expr-faae36d220f51fb5

\centering \begin{tabular}{lllll} \cline{2-4} \multicolumn{1}{l|}{} & \multicolumn{1}{c|}{$\TMblank$} & \multicolumn{1}{c|}{$\TMstroke$} & \multicolumn{1}{c|}{$\TMendtape$} & \\ \cline{1-4} \multicolumn{1}{|l|}{$q_0$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{\TMtrans{\TMstroke}{q_1}{\TMright}} & \multicolumn{1}{l|}{\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}}} & \\ \cline{1-4} \multicolumn{1}{|l|}{$q_1$} & \multicolumn{1}{l|}{\TMtrans{\TMblank}{q_1}{\TMright}} & \multicolumn{1}{l|}{\TMtrans{\TMstroke}{q_0}{\TMright}} & \multicolumn{1}{l|}{\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}}} & \\ \cline{1-4} \end{tabular}

Read as: Machine table for the even machine. From state q zero reading blank symbol, the transition is undefined and the machine halts. From state q zero reading stroke symbol, write stroke symbol, move right, and enter state q one. From state q zero reading left end marker, the transition is undefined and the machine halts. From state q one reading blank symbol, write blank symbol, move right, and enter state q one. From state q one reading stroke symbol, write stroke symbol, move right, and enter state q zero. From state q one reading left end marker, the transition is undefined and the machine halts

Means: A row-by-row account of the displayed machine table, including undefined halting cells. Read as: Machine table for the even machine. From state q zero reading blank symbol, the transition is undefined and the machine halts. From state q zero reading stroke symbol, write stroke symbol, move right, and enter state q one. From state q zero reading left end marker, the transition is undefined and the machine halts. From state q one reading blank symbol, write blank symbol, move right, and enter state q one. From state q one reading stroke symbol, write stroke symbol, move right, and enter state q zero. From state q one reading left end marker, the transition is undefined and the machine halts

1 occurrence in this chapter

Occurrence projected-formula-0016445