Ch.10: Turing Machines I
Week 10 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 10.1. Definition and Diagrams 10.2. Algorithmic Description of TMs
41 flashcards · Computer Science · by lakesare
Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses
[Definition and Diagrams] What is a Turing machine (TM), informally?
A finite automaton with unlimited memory on a tape, whose head can move left or right and can read and write on any cell. A control unit with finitely many states, a head, and a tape that is infinite to the right.
[Definition and Diagrams] Why is the tape of a Turing machine more powerful than the stack of a PDA (pushdown automaton)?
The head can read and write any cell of the tape, while a PDA can only read, push and pop at the top of the stack. Example: {wcw∣w∈{a,b}∗}\{wcw \mid w \in \{a, b\}^*\}{wcw∣w∈{a,b}∗} is recognized by a TM, but by no PDA.
[Definition and Diagrams] How does a Turing machine start its computation?
The input is on the leftmost cells of the tape, all other cells are blank, the head is on the leftmost cell, and the machine is in the start state q0q_0q0 . The head can never move to the left of the start cell.Example: input 100111001110011 gives the tape 1 0 0 1 1 □ □ □…1\,0\,0\,1\,1\,\square\,\square\,\square \dots10011□□□…
[Definition and Diagrams] What does a Turing machine do in one step?
It reads the symbol under the head, writes a symbol in that cell, moves the head one cell left or right, and may change state. Like a DFA, it is deterministic: the transition function determines each step.
[Definition and Diagrams] A Turing machine is an 8-tuple (Q,Σ,Γ,δ,□,q0,qaccept,qreject)(Q, \Sigma, \Gamma, \delta, \square, q_0, q_{\text{accept}}, q_{\text{reject}})(Q,Σ,Γ,δ,□,q0,qaccept,qreject) . What is each component?
QQQ the finite set of states Example: {q0,q1,q2,qaccept,qreject}\{q_0, q_1, q_2, q_{\text{accept}}, q_{\text{reject}}\}{q0,q1,q2,qaccept,qreject} Σ\SigmaΣ the input alphabet, a finite set with □∉Σ\square \notin \Sigma□∈/Σ Example: {0,1}\{0, 1\}{0,1} Γ\GammaΓ the tape alphabet, a finite set with Σ⊆Γ\Sigma \subseteq \GammaΣ⊆Γ and □∈Γ\square \in \Gamma□∈Γ Example: {0,1,0‾,1‾,□}\{0, 1, \overline{0}, \overline{1}, \square\}{0,1,0,1,□} δ\deltaδ the transition function δ:Q×Γ→Q×Γ×{L,R}\delta: Q \t…
[Definition and Diagrams] For a Turing machine with transition function δ\deltaδ , what does δ(q,a)=(r,b,L)\delta(q, a) = (r, b, L)δ(q,a)=(r,b,L) mean?
In state qqq , reading aaa : write bbb in the cell, move the head one cell left, go to state rrr . δ:Q×Γ→Q×Γ×{L,R}\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}δ:Q×Γ→Q×Γ×{L,R} , where Γ\GammaΓ is the tape alphabet.Example: δ(q1,1)=(q2,1‾,L)\delta(q_1, 1) = (q_2, \overline{1}, L)δ(q1,1)=(q2,1,L) replaces 111 by 1‾\overline{1}1 and moves left into q2q_2q2 .
[Definition and Diagrams] How are the input alphabet Σ\SigmaΣ , the tape alphabet Γ\GammaΓ and the blank □\square□ of a Turing machine related?
Σ⊆Γ\boldsymbol{\Sigma \subseteq \Gamma}Σ⊆Γ , □∈Γ\boldsymbol{\square \in \Gamma}□∈Γ , □∉Σ\boldsymbol{\square \notin \Sigma}□∈/Σ Since the input contains no □\square□ , the first □\square□ the machine reads to the right of the input marks the end of the input.Example: Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} , Γ={0,1,0‾,1‾,□}\Gamma = \{0, 1, \overline{0}, \overline{1}, \square\}Γ={0,1,0,1,□}
[Definition and Diagrams] What happens when a Turing machine enters qacceptq_{\text{accept}}qaccept or qrejectq_{\text{reject}}qreject ?
The computation halts immediately, accepting or rejecting the input.
[Definition and Diagrams] Besides accepting and rejecting, what else can happen when a Turing machine runs on an input?
It can loop: the computation never halts. A DFA always stops at the end of the input; a Turing machine has no such end, since it can move left and right forever.
[Definition and Diagrams] In a Turing machine state diagram, what does the label a→b,Ra \to b, Ra→b,R on an arrow from qqq to rrr mean?
In state qqq , reading aaa : write bbb , move the head right, go to state rrr . a→a,Ra \to a, Ra→a,R reads aaa and leaves the cell unchanged.
[Definition and Diagrams] In a Turing machine state diagram, what happens when the machine reads a symbol for which the current state has no arrow?
The machine goes to the reject state (it crashes). So the reject state and the arrows into it are usually not drawn, as with missing transitions in an NFA.Example: in a machine for 0n1n0^n1^n0n1n , reading □\square□ while still searching for a 111 rejects.
[Definition and Diagrams] Which language over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} does this Turing machine recognize?
{w∣the number of 1’s in w is a multiple of 3}\boldsymbol{\{w \mid \text{the number of 1's in } w \text{ is a multiple of } 3\}}{w∣the number of 1’s in w is a multiple of 3} q0,q1,q2q_0, q_1, q_2q0,q1,q2 count the 1's modulo 3; 000 's change nothing; □\square□ marks the end of the input. The machine only reads and never changes the tape, like a DFA.Example: 101110111011 goes q0→q1→q1→q2→q0→qacceptq_0 \to q_1 \to q_1 \to q_2 \to q_0 \to q_{\text{accept}}q0→q1→q1→q2→q0→qaccept : acce…
[Definition and Diagrams] Which language over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} does this Turing machine recognize? (Missing transitions go to the reject state.)
{0n1n∣n≥1}\boldsymbol{\{0^n1^n \mid n \ge 1\}}{0n1n∣n≥1} Example: 0011→0‾011→0‾01‾1→0‾ 0‾ 1‾1→0‾ 0‾ 1‾ 1‾0011 \to \overline{0}011 \to \overline{0}0\overline{1}1 \to \overline{0}\,\overline{0}\,\overline{1}1 \to \overline{0}\,\overline{0}\,\overline{1}\,\overline{1}0011→0011→0011→0011→0011 , then q3q_3q3 passes the 1‾\overline{1}1 's, reads □\square□ and accepts.
[Definition and Diagrams] How does a Turing machine recognize {0n1n∣n≥1}\{0^n1^n \mid n \ge 1\}{0n1n∣n≥1} ?
Mark a 000 (as 0‾\overline{0}0 ), move right to the first unmarked 111 and mark it (as 1‾\overline{1}1 ), move left to the last marked 000 ; repeat. When no unmarked 000 is left, it checks that only 1‾\overline{1}1 's follow up to □\square□ . The tape alphabet {0,1,0‾,1‾,□}\{0, 1, \overline{0}, \overline{1}, \square\}{0,1,0,1,□} is larger than the input alphabet {0,1}\{0, 1\}{0,1} .
[Definition and Diagrams] Which language over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} does this Turing machine recognize? (Missing transitions go to the reject state.)
The palindromes of even length. Example: abbaabbaabba is accepted; abaabaaba (odd length) and ababab are rejected.
[Definition and Diagrams] How does a Turing machine recognize the even-length palindromes over {a,b}\{a, b\}{a,b} ?
Delete the first symbol, then delete the last symbol if it is the same (else reject); repeat until the tape is blank, then accept. After each deletion at the end, the head returns to the new start. q1q_1q1 remembers that the deleted first symbol was aaa , q3q_3q3 that it was bbb .
[Definition and Diagrams] A Turing machine for the even-length palindromes over {a,b}\{a, b\}{a,b} repeatedly deletes the first symbol, goes to the end and deletes the last symbol if it is the same.Why does this machine reject odd-length palindromes such as abaabaaba ?
After deleting the first symbol of the last round, it finds no symbol at the end (only □\square□ ), and then it rejects. Example: aba→□b□aba \to \square b \squareaba→□b□ ; then bbb is deleted as a first symbol, and at the end the machine reads □\square□ instead of bbb .
[Algorithmic Description of TMs] A Turing machine that produces a desired output on the tape for a given input, rather than only accepting or rejecting, is called a transducer.
Example: a TM that turns 1n1^n1n into 12n1^{2n}12n .
[Algorithmic Description of TMs] Why were Turing machines developed?
As a model of computation that can do whatever a computer can do. So a Turing machine is a tool for theoretical questions about what computers can compute.
[Algorithmic Description of TMs] Why are Turing machines usually described by pseudo-code instead of state diagrams?
TM state diagrams are much more complicated than DFA or PDA diagrams, so a higher-level description, a TM as an algorithm, is easier to write and read.
[Algorithmic Description of TMs] Write this fragment of a Turing machine (starting in q2q_2q2 ) as pseudo-code.
Move right over 0's. If you read 1: replace 1 by 0, move head one unit left. If you read □\square□ : ACCEPT.
[Algorithmic Description of TMs] Which basic operations do the pseudo-code descriptions of Turing machines use?
Sweep Move from start to end to check the input, e.g. the order of the symbols. Example: if there is any aaa after the first bbb , REJECT. Cross Replace a symbol by ×\times× , so that it is counted and never read again as that symbol. Example: cross an aaa , then cross a bbb , to pair them. Mark and unmark Replace a symbol by a marked version and later back, so that it can be counted again. Example: a→a‾a \to \overline{a}a→a , later a‾→a\overline{a} \to aa→a . Write at the end Move head to end…
[Algorithmic Description of TMs] Describe a Turing machine (a transducer) that turns an input 1n1^n1n into 12n1^{2n}12n .
Replace the first 1 by $\char36 $ , mark the other 1's; then for each 1, write one more 1 at the end. Steps: write a 1 at the end (the copy of the first 1); move left to a 1‾\overline{1}1 , unmark it, write a 1 at the end, repeat; at $\char36 $ , write 1 and ACCEPT. If the first symbol is □\square□ (input ε\varepsilonε ), ACCEPT at once.Example: 11→$1‾1→$111→111111 \to \char36 \overline{1}1 \to \char36 111 \to 111111→$11→$111→1111
[Algorithmic Description of TMs] A transducer turns 1n1^n1n into 12n1^{2n}12n : it replaces the first 1 by $\char36 $ , marks the other 1's ( 1→1‾1 \to \overline{1}1→1 ), writes a 1 at the end, then repeatedly moves left to a 1‾\overline{1}1 , unmarks it and writes a 1 at the end.What is the $\char36 $ for?
It marks the left end of the input, so the machine knows when all marked 1's are done; then it writes a 1 in place of $\char36 $ and accepts. The 1 written at the end right after marking is the copy of the first 1.
[Algorithmic Description of TMs] Describe a Turing machine recognizing {a2nbn∣n≥0}\{a^{2n}b^n \mid n \ge 0\}{a2nbn∣n≥0} .
Check that no aaa comes after a bbb ; then repeatedly cross two aaa 's and one bbb ; accept if the aaa 's and bbb 's run out together. 1. Sweep: if there is any aaa after the first bbb , REJECT.2. Search for aaa . If found, cross it and cross a second aaa (if there is none, REJECT). If not found, Go To 4.3. Search for bbb . If found, cross it, Go To 2. Else REJECT.4. Search for bbb . If found, REJECT. Else ACCEPT.
[Algorithmic Description of TMs] Describe a Turing machine recognizing {anbn2∣n≥1}\{a^n b^{n^2} \mid n \ge 1\}{anbn2∣n≥1} .
Write one ccc at the end for each aaa ; then for each ccc , delete it and mark one bbb for each aaa ; accept if exactly all bbb 's get marked. So nnn rounds mark nnn bbb 's each, n2n^2n2 in total.1. Sweep: if there is no aaa , no bbb , or they are out of order, REJECT.2. For each aaa : mark it ( a→a‾a \to \overline{a}a→a ), move head to end, write ccc .3. Search for ccc . If found, delete it, Go To 4. Else: if an unmarked bbb is left, REJECT; else ACCEPT.4. Unmark all aaa 's.5. For each aaa : m…
[Algorithmic Description of TMs] Describe a Turing machine recognizing {wcw∣w∈{a,b}∗}\{wcw \mid w \in \{a, b\}^*\}{wcw∣w∈{a,b}∗} .
Repeatedly cross the first uncrossed symbol before ccc and the first uncrossed symbol after ccc , rejecting if they differ. Before that, check that there is exactly one ccc . At the end, accept if after ccc only ×\times× 's and then □\square□ remain.1. Sweep: if there is no ccc or more than one ccc , REJECT.2. Read the symbol; if it is aaa : cross it, move right to ccc , move right over ×\times× 's, read the next symbol; if it is aaa , cross it, move left to ccc , then left to the first ×\times…
[Algorithmic Description of TMs] Is {wcw∣w∈{a,b}∗}\{wcw \mid w \in \{a, b\}^*\}{wcw∣w∈{a,b}∗} regular? Context-free? Turing-recognizable?
Not regular, not context-free, but Turing-recognizable. The pumping lemma for context-free languages shows it is not context-free; a TM recognizes it by crossing matching symbols on both sides of ccc .
[Algorithmic Description of TMs] How are the regular, the context-free and the Turing-recognizable languages related?
Regular ⊊\subsetneq⊊ context-free ⊊\subsetneq⊊ Turing-recognizable A language is Turing-recognizable if some Turing machine recognizes it. Every context-free language is Turing-recognizable (proved later in the book).Example: {anbn}\{a^nb^n\}{anbn} is context-free but not regular; {wcw}\{wcw\}{wcw} is Turing-recognizable but not context-free.
[Algorithmic Description of TMs] Describe a Turing machine (a transducer) that turns nnn symbols aaa into n2n^2n2 symbols aaa .
Write nnn bbb 's at the end as a counter; for each bbb , delete it and write nnn ccc 's at the end. Finally delete the aaa 's and turn the ccc 's into aaa 's. aaa 's are marked ( a→a‾a \to \overline{a}a→a ) to count them and unmarked before each round.Example: aa→aa bb→aa \to aa\,bb \toaa→aabb→ two rounds of cccccc →cccc→aaaa\to cccc \to aaaa→cccc→aaaa
[Exercises] Describe a Turing machine recognizing {anbncn∣n≥0}\{a^nb^nc^n \mid n \ge 0\}{anbncn∣n≥0} .
Check the order; then repeatedly cross one aaa , one bbb and one ccc ; when no aaa is left, accept if no bbb or ccc is left. 1. Sweep: if the symbols are out of order (e.g. an aaa after a bbb ), REJECT.2. Search for aaa . If found, cross it. Else Go To 5.3. Search for bbb . If found, cross it. Else REJECT.4. Search for ccc . If found, cross it, Go To 2. Else REJECT.5. Search for bbb or ccc . If found, REJECT. Else ACCEPT.
[Exercises] A Turing machine for {anbncn∣n≥0}\{a^nb^nc^n \mid n \ge 0\}{anbncn∣n≥0} : check the order of the symbols; repeatedly cross one aaa , one bbb and one ccc ; when no aaa is left, accept if no bbb or ccc is left.How do you change this machine to recognize {w∣w has equally many a’s,b’s and c’s}\{w \mid w \text{ has equally many } a\text{'s}, b\text{'s and } c\text{'s}\}{w∣w has equally many a’s,b’s and c’s} ?
Delete the first step, the check of the order. Searching for the next aaa , bbb or ccc works in any order. For NFAs and PDAs the order of the symbols matters much more.
[Exercises] Describe a Turing machine recognizing {anbmcn+m∣n,m≥0}\{a^nb^mc^{n+m} \mid n, m \ge 0\}{anbmcn+m∣n,m≥0} .
Check the order; then repeatedly cross one aaa or bbb and one ccc ; when no aaa or bbb is left, accept if no ccc is left. If an aaa or bbb is crossed but no ccc is found, REJECT.
[Exercises] Describe a Turing machine recognizing {anbn+1c4n∣n≥0}\{a^nb^{n+1}c^{4n} \mid n \ge 0\}{anbn+1c4n∣n≥0} .
Check the order; then repeatedly cross one aaa , one bbb and four ccc 's; when no aaa is left, accept if exactly one bbb and no ccc are left. Example: abbccccabbccccabbcccc : one round crosses aaa , bbb , cccccccccccc ; one bbb is left, so accept.
[Exercises] Describe a Turing machine recognizing {w∈{a,b,c}∗∣the number of a’s is twice the number of c’s}\{w \in \{a, b, c\}^* \mid \text{the number of } a\text{'s is twice the number of } c\text{'s}\}{w∈{a,b,c}∗∣the number of a’s is twice the number of c’s} .
Repeatedly cross two aaa 's and one ccc (reject if only one aaa , or no ccc , is found); when no aaa is left, accept if no ccc is left. No order check: the bbb 's and the order of the symbols do not matter.Example: cbaacbaacbaa is accepted, accaccacc is rejected.
[Exercises] Describe a Turing machine recognizing {akbmcn∣k<m or k<n}\{a^kb^mc^n \mid k < m \text{ or } k < n\}{akbmcn∣k<m or k<n} .
For each aaa , cross it and one bbb and one ccc where present; at the end, accept if some bbb or ccc is left. First check the order. If an aaa finds neither a bbb nor a ccc , REJECT.After kkk rounds, a bbb is left exactly when m>km > km>k , and a ccc exactly when n>kn > kn>k .Example: aabcccaabcccaabccc ( k=2<n=3k = 2 < n = 3k=2<n=3 ): accepted. aabcaabcaabc : the second aaa finds neither bbb nor ccc , so rejected.
[Exercises] Describe a Turing machine recognizing {anbm∣m=5n−3, n≥1}\{a^nb^m \mid m = 5n - 3, \ n \ge 1\}{anbm∣m=5n−3, n≥1} .
Write three extra bbb 's at the end; then repeatedly cross one aaa and five bbb 's; accept if no bbb is left. First reject unless the input starts with aaa and has no aaa after a bbb . m=5n−3m = 5n - 3m=5n−3 means m+3=5nm + 3 = 5nm+3=5n .Example: abbabbabb ( n=1n = 1n=1 , m=2m = 2m=2 ) becomes abbbbbabbbbbabbbbb , one round crosses everything: accepted.
[Exercises] Describe a Turing machine recognizing {anba2nba3n∣n≥0}\{a^nba^{2n}ba^{3n} \mid n \ge 0\}{anba2nba3n∣n≥0} .
Repeatedly cross one aaa before the first bbb , two between the bbb 's, and three after the second bbb ; at the end, accept if no aaa is left. First reject unless there are exactly two bbb 's. The loop ends when no aaa is left before the first bbb .Example: abaabaaaabaabaaaabaabaaa ( n=1n = 1n=1 ): one round crosses all six aaa 's, accepted.
[Exercises] A={w∈{0,1}∗∣#0=#1}A = \{w \in \{0, 1\}^* \mid \#0 = \#1\}A={w∈{0,1}∗∣#0=#1} and B={w∈{0,1}∗∣#0=2⋅#1}B = \{w \in \{0, 1\}^* \mid \#0 = 2 \cdot \#1\}B={w∈{0,1}∗∣#0=2⋅#1} , where #0\#0#0 , #1\#1#1 count the 0's and 1's in www . Describe a Turing machine recognizing A∪BA \cup BA∪B .
Pair each 1 with one 0 (ACCEPT if no 0 is left); otherwise unmark all and pair each 1 with two 0's (ACCEPT if no 0 is left). The first pass tests w∈Aw \in Aw∈A , the second w∈Bw \in Bw∈B ; pairing is done by marking.If a 1 finds no 0 in the first pass, #0<#1\#0 < \#1#0<#1 , so www is in neither AAA nor BBB : REJECT.Example: 000100010001 fails the first pass ( #0>#1\#0 > \#1#0>#1 ), but is not in BBB either ( 3≠23 \neq 23=2 ): rejected. 001001001 is accepted in the second pass.
[Exercises] What language does this Turing machine recognize? 1. Sweep: if there is any aaa after the first bbb , REJECT.2. Move head to start, search for aaa . If found, cross it. Else Go To 5.3. Two times: search for bbb ; if found cross it, else REJECT.4. Go To 2.5. Move head to start, search for bbb . If found, ACCEPT. Else REJECT.
{anbm∣m≥2n+1}\boldsymbol{\{a^nb^m \mid m \ge 2n + 1\}}{anbm∣m≥2n+1} Each aaa crosses two bbb 's, and at least one bbb must remain.Example: bbb ( n=0n = 0n=0 ) and abbbabbbabbb are accepted; abbabbabb is rejected.
[Exercises] What language does this Turing machine recognize? 1. If there is no ccc , two or more ccc 's, an aaa after ccc or a bbb before ccc : REJECT.2. Move head to end, write bbb .3. Move head to start, search for aaa . If found, cross it. Else Go To 6.4. Two times: search for bbb ; if found cross it, else REJECT.5. Go To 3.6. Move head to start, search for bbb . If found, REJECT. Else ACCEPT.
{ancb2n−1∣n≥1}\boldsymbol{\{a^ncb^{2n-1} \mid n \ge 1\}}{ancb2n−1∣n≥1} The input is ancbka^ncb^kancbk ; with the extra bbb there are k+1k + 1k+1 bbb 's, and each aaa crosses two, so k+1=2nk + 1 = 2nk+1=2n .Example: acbacbacb ( n=1n = 1n=1 ) and aacbbbaacbbbaacbbb are accepted; ccc is rejected.