Exercise 1 Consider the following 2-tape Turing Machine, which we call P. 12+ o/oo o+ o/oo 42 43 where n E 10, 1). At the correct initial configuration, i is assumed that the first tape contains a bitstring w, and the head is positioned on the leftmost bit; e the second tape is empty, i.e. filled with blanks. a) Write out the runs of P for each of the following bitstings w: 00, 000, 0101, 0110, 1110 b) Determine at which state will P terminate when w is the alternating bitstring of 0s and 1 (i.e. w = 010101 . . .) such that i. the length of w is 99 ii. the length of w is 100 [Hint: What if w = 01010?] c) Explain the general behavior of the machine: which bitstrings w lead to which states? d) Does every run starting from a correct initial configuration terminate? If not, provide an example of a correct initial configuration that leads to a nonterminating run. If yes, add one or two transitions so that the new machine does not terminate for correct initial configurations. For extra points, i. describe a 1-tape Turing machine R, which performs the same computation as the 2-tape machine P ii. determine how many steps wll it take to each of the machines P and R to terminate on input w of length n 40 points ] Exercise 1 Consider the following 2-tape Turing Machine, which we call P. 12+ o/oo o+ o/oo 42 43 where n E 10, 1). At the correct initial configuration, i is assumed that the first tape contains a bitstring w, and the head is positioned on the leftmost bit; e the second tape is empty, i.e. filled with blanks. a) Write out the runs of P for each of the following bitstings w: 00, 000, 0101, 0110, 1110 b) Determine at which state will P terminate when w is the alternating bitstring of 0s and 1 (i.e. w = 010101 . . .) such that i. the length of w is 99 ii. the length of w is 100 [Hint: What if w = 01010?] c) Explain the general behavior of the machine: which bitstrings w lead to which states? d) Does every run starting from a correct initial configuration terminate? If not, provide an example of a correct initial configuration that leads to a nonterminating run. If yes, add one or two transitions so that the new machine does not terminate for correct initial configurations. For extra points, i. describe a 1-tape Turing machine R, which performs the same computation as the 2-tape machine P ii. determine how many steps wll it take to each of the machines P and R to terminate on input w of length n 40 points ]
