Theorem 8.11; If M is a nondeterministic Turing machine, then there is a deterministic Thring machine Md such that Ь(Мл) = L(Md).

PROOF; Md will be designed as a multitape TM, sketched in Fig. 8.18. The first tape of Md holds a sequence of IDs of Мдг, including the state of Mjv. One ID of Mfj is marked as the current ID, whose successor IDs are in the process of being discovered. In Fig. 8.18, the third ID is marked by an j: along with the inter-ID separator, which is the *. All IDs to the left of the current one have been explored and can be ignored subsequently.

Queue of IDS

* Ш2

Scratch tape

Figure 8.18: Simulation of an NTM by a DTM

To process the current ID, Md does the following:

1. Md examines the state and scanned symbol of the current ID. Built into the finite control of Md is the knowledge of what choices of move Мл has for each state and symbol. If the state hi the current ID is accepting, then Md accepts and simulates Mj no further.

2. However, if the state is not accepting, and the state-symbol combination has к moves, then Мд uses its second tape to copy the ID and then make к copies of that ID at the end of the sequence of IDs on tape 1.

3. Md modifies each of those fc IDs according to a different one of the к choices of move that Мдг has from its current ID.

4. Md returns to the marked, current ID, erases the mark, and moves the mark to the next ID to the right. The cycle then repeats with step (1).

It should be clear that the simulation is accurate, in the sense that Md will only accept if it finds that Л/дг can enter an accepting ID. However, we need to confirm that if Myv enters an accepting ID after a sequence of n of its own moves, then Mo will eventually make that ID the current ID and will accept.

Show the ids reachable from the initial ID if the input is: * a) 01. b) Oil.

! Exercise 8.4.3: Informally but clearly describe nondeterministic Taring machines - muftitape if you like - that accept the following languages. Try to

Suppose that m is the majdmum number of choices Mjv has in any configuration. Then there is one initial ID of M, at most m IDs that M can reach after one move, at most IDs Mjv can reach after two moves, and so on. Thus, after n moves, M can reach at most l+m + rri + + IDs. This number is at most nm IDs.

The order in which Md explores IDs of Мдг is breadth first ; that is, it explores all IDs reachable by 0 moves (i.e., the initial ID), then all IDs reachable by one move, then those reachable by two moves, and so on. In particular, Md will make current, and consider the successors of, all IDs reachable by up to n moves before considering any IDs that are only reachable by more than n moves.

As a consequence, the accepting ID of Mjv will be considered by Md among the first nm IDs that it considers. We only care that Md considers this ID in some finite time, and this bound is sufficient to assure us that the accepting ID is considered eventually. Thus, if M accepts, then so does Md- Since we already observed that if Md accepts it does so only because M accepts, we conclude that L{Mn) = L{Md)-

Notice that the constructed deterministic TM may take exponentially more time than the nondeterministic TM. It is unknown whether or not this exponential slowdown is necessary. In fact, Chapter 10 is devoted to this question and the consequences of someone discovering a better way to simulate NTMs deterministically.

8.4.5 Exercises for Section 8.4

Exercise 8.4.1: Informally but clearly describe multitape Turing machines that accept each of the languages of Exercise 8.2.2. Tty to make each of your Turing machines run in time proportional to the input length.

Exercise 8.4.2: Here is the transition function of a nondeterministic TM M = ({90,91,92}, {0,1}, {0,\,B}Aqo,B,{q2}y.

take advantage of nondeterminism to avoid iteration and save time in the non-deterministic sense. That is, prefer to have your NTM branch a lot, while each branch is short.

* a) The language of all strings of Os and Is that have some string of length 100 that repeats, not necessarily consecutively. Formally, this language is the set of strings of Os and Is of the form wxyxz, where - 100, and w, y, and 2 are of arbitrary length.

b) The language of all strings of the form Ш1#Ш2# #ш , for any n, such that each Wi is a string of Os and Is, and for some j, Wj is the integer j in binary.

c) The language of all strings of the same form as (b), but for at least two values of j, we have Wj equal to j in binary,

1 Exercise 8.4.4; Consider the nondeterministic Turing machine

M = ({ 0,91,92,{0,1}, {0, l,B},6,go, B, {qf})

Informally but clearly describe the language L(M) if 5 consists of the following sets of rules: 5(go,0) = {( o,l,-R), (quhR)}; rf(9i,l) = {( 2,0,L)}; д{д2,1) = {{qo,l,R)}; S{quB) = {{qf,B,R)}.

* Exercise 8.4.5: Consider a nondeterministic TM whose tape is infinite in both directions. At some time, the tape is completely blank, except for one cell, which holds the symbol $. The head is currently at some blank cell, and the state is q.

a) Write transitions that will enable the NTM to enter state p, scanning the

! b) Suppose the TM were deterministic instead. How would you enable it to find the $ and enter state p?

Exercise 8.4.6: Design the following 2-tape TM to accept the language of all strings of Os and Is with an equal number of each. The first tape contains the input, and is scanned from left to right. The second tape is used to store the excess of Os over Is, or шсе-versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state.

Exercise 8.4.7: In this exercises, we shall implement a stack using a special 3-tape TM.

1. The first tape will be used only to hold and read the input. The input alphabet consists of the symbol t, which we shall inteфret as pop the stack, and the symbols a and b, which are interpreted as push an a (respectively b) onto the stack.