Answer the questions numbers 3.1, 3.2, 3.4, 3.5, 3.6, 3.7, 3.8

186 CHAPTER 3 / THE CHURCH-TURING THESIS The following is a high-level description of a TM M that decides A. M = "On input G), the encoding of a graph G. 1. Select the first node of G and mark it. 2. Repeat the following stage until no new nodes are marked: 3. For each node in G, mark it if it is attached by an edge to a node that is already marked. 4. Scan all the nodes of G to determine whether they all are marked. If they are, accept; otherwise, reject." For additional practice, let's examine some implementation-level details of Turing machine M. Usually we won't give this level of detail in the future and you won't need to either, unless specifically requested to do so in an exercise. First, we must understand how encodes the graph G as a string. Consider an encoding that is a list of the nodes of G followed by a list of the edges of G. Each node is a decimal number, and each edge is the pair of decimal numbers that represent the nodes at the two endpoints of the edge. The following figure depicts such a graph and its encoding. (1,2,3,4) ((1,2), (2,3), (3,1),(1,4)) FIGURE 3.24 A graph G and its encoding G) When M receives the input (G), it first checks to determine whether the input is the proper encoding of some graph. To do so, M scans the tape to be sure that there are two lists and that they are in the proper form. The first list should be a list of distinct decimal numbers, and the second should be a list of pairs of decimal numbers. Then M checks several things. First, the node list should contain no repetitions, and second, every node appearing on the edge list should also appear on the node list. For the first, we can use the procedure given in Example 3.12 for TM M. that checks clement distinctness. A similar method works for the second check. If the input passes these checks, it is the encoding of some graph G. This verification completes the input check, and M goes on to stage 1 For stage 1, M marks the first node with a dot on the leftmost digit. For stage 2, M scans the list of nodes to find an undotted node ni and flags it by marking it differently say, by underlining the first symbol. Then M scans the list again to find a dotted node 12 and underlines it, too. EXERCISES 187 Now M scans the list of edges. For each edge, M tests whether the two underlined nodes n, and nu are the ones appearing in that edge. If they are, M dots 1, removes the underlines, and goes on from the beginning of stage 2. If they aren't, M checks the next edge on the list. If there are no more edges, {nna} is not an edge of G. Then M moves the underline on ny to the next dotted node and now calls this node na. It repeats the steps in this paragraph to check, as before, whether the new pair {n, n) is an edge. If there are no more dotted nodes, mi is not attached to any dotted nodes. Then M sets the underlines so that is the next undotted node and ng is the first dotted node and repeats the steps in this paragraph. If there are no more undotted nodes, M has not been able to find any new nodes to dot, so it moves on to stage 4. For stage 4, M scans the list of nodes to determine whether all are dotted. If they are, it enters the accept state, otherwise, it enters the reject state. This completes the description of IM M. EXERCISES 3.1 This exercise concerns TM M2, whose description and state diagram appear in Ex- ample 3.7. In each of the parts, give the sequence of configurations that Mz enters when started on the indicated input string. a. 0. b. 00 c. 000 d. 000000 3.2 This exercise concerns TM M., whose description and state diagram appear in Ex- ample 3.9. In each of the parts , give the sequence of configurations that M, enters when started on the indicated input string. b. 171 c. 1881 d. 10811 e. 10810. *3.3 Modify the proof of Theorem 3.16 to obtain Corollary 3.19, showing that a lan- guage is decidable iff some nondeterministic Turing machine decides it . (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.) 3.4 Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language 188 CHAPTER 3 / THE CHURCH-TURING THESIS A3.5 Examine the formal definition of a Turing machine to answer the following ques- tions, and explain your reasoning. a. Can a Turing machine ever write the blank symbol u on its tape? b. Can the tape alphabet I be the same as the input alphabet ? c. Can a Turing machine's head ever be in the same location in two successive steps? d. Can a Turing machine contain just a single state? 3.6 In Theorem 3.21, we showed that a language is Turing-recognizable iff some enu- merator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, 81, 82,... is a list of all strings in ". E = "Ignore the input 1. Repeat the following for i = 1.2.3..... 2. Run M on si. 3. If it accepts, print out si." 3.7 Explain why the following is not a description of a legitimate Turing machine. Mbad = "On input (p), a polynomial over variables 11, s. Ik 1. Try all possible settings of 81,...,x to integer values. 2. Evaluate p on all of these settings. 3. If any of these settings evaluates to 0, accept; otherwise, reject." 3.8 Give implementation-level descriptions of Turing machines that decide the follow- ing languages over the alphabet (0.1). Aa. {w w contains an equal number of Os and 1s} b. { ww contains twice as many Os as 1s} c. {w} w does not contain twice as many Os as 1s} 186 CHAPTER 3 / THE CHURCH-TURING THESIS The following is a high-level description of a TM M that decides A. M = "On input G), the encoding of a graph G. 1. Select the first node of G and mark it. 2. Repeat the following stage until no new nodes are marked: 3. For each node in G, mark it if it is attached by an edge to a node that is already marked. 4. Scan all the nodes of G to determine whether they all are marked. If they are, accept; otherwise, reject." For additional practice, let's examine some implementation-level details of Turing machine M. Usually we won't give this level of detail in the future and you won't need to either, unless specifically requested to do so in an exercise. First, we must understand how encodes the graph G as a string. Consider an encoding that is a list of the nodes of G followed by a list of the edges of G. Each node is a decimal number, and each edge is the pair of decimal numbers that represent the nodes at the two endpoints of the edge. The following figure depicts such a graph and its encoding. (1,2,3,4) ((1,2), (2,3), (3,1),(1,4)) FIGURE 3.24 A graph G and its encoding G) When M receives the input (G), it first checks to determine whether the input is the proper encoding of some graph. To do so, M scans the tape to be sure that there are two lists and that they are in the proper form. The first list should be a list of distinct decimal numbers, and the second should be a list of pairs of decimal numbers. Then M checks several things. First, the node list should contain no repetitions, and second, every node appearing on the edge list should also appear on the node list. For the first, we can use the procedure given in Example 3.12 for TM M. that checks clement distinctness. A similar method works for the second check. If the input passes these checks, it is the encoding of some graph G. This verification completes the input check, and M goes on to stage 1 For stage 1, M marks the first node with a dot on the leftmost digit. For stage 2, M scans the list of nodes to find an undotted node ni and flags it by marking it differently say, by underlining the first symbol. Then M scans the list again to find a dotted node 12 and underlines it, too. EXERCISES 187 Now M scans the list of edges. For each edge, M tests whether the two underlined nodes n, and nu are the ones appearing in that edge. If they are, M dots 1, removes the underlines, and goes on from the beginning of stage 2. If they aren't, M checks the next edge on the list. If there are no more edges, {nna} is not an edge of G. Then M moves the underline on ny to the next dotted node and now calls this node na. It repeats the steps in this paragraph to check, as before, whether the new pair {n, n) is an edge. If there are no more dotted nodes, mi is not attached to any dotted nodes. Then M sets the underlines so that is the next undotted node and ng is the first dotted node and repeats the steps in this paragraph. If there are no more undotted nodes, M has not been able to find any new nodes to dot, so it moves on to stage 4. For stage 4, M scans the list of nodes to determine whether all are dotted. If they are, it enters the accept state, otherwise, it enters the reject state. This completes the description of IM M. EXERCISES 3.1 This exercise concerns TM M2, whose description and state diagram appear in Ex- ample 3.7. In each of the parts, give the sequence of configurations that Mz enters when started on the indicated input string. a. 0. b. 00 c. 000 d. 000000 3.2 This exercise concerns TM M., whose description and state diagram appear in Ex- ample 3.9. In each of the parts , give the sequence of configurations that M, enters when started on the indicated input string. b. 171 c. 1881 d. 10811 e. 10810. *3.3 Modify the proof of Theorem 3.16 to obtain Corollary 3.19, showing that a lan- guage is decidable iff some nondeterministic Turing machine decides it . (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.) 3.4 Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language 188 CHAPTER 3 / THE CHURCH-TURING THESIS A3.5 Examine the formal definition of a Turing machine to answer the following ques- tions, and explain your reasoning. a. Can a Turing machine ever write the blank symbol u on its tape? b. Can the tape alphabet I be the same as the input alphabet ? c. Can a Turing machine's head ever be in the same location in two successive steps? d. Can a Turing machine contain just a single state? 3.6 In Theorem 3.21, we showed that a language is Turing-recognizable iff some enu- merator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, 81, 82,... is a list of all strings in ". E = "Ignore the input 1. Repeat the following for i = 1.2.3..... 2. Run M on si. 3. If it accepts, print out si." 3.7 Explain why the following is not a description of a legitimate Turing machine. Mbad = "On input (p), a polynomial over variables 11, s. Ik 1. Try all possible settings of 81,...,x to integer values. 2. Evaluate p on all of these settings. 3. If any of these settings evaluates to 0, accept; otherwise, reject." 3.8 Give implementation-level descriptions of Turing machines that decide the follow- ing languages over the alphabet (0.1). Aa. {w w contains an equal number of Os and 1s} b. { ww contains twice as many Os as 1s} c. {w} w does not contain twice as many Os as 1s}