2013 May 1,

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

In class we've outlined how, for any nondeterministic Turing machine *N*, there exists a deterministic Turing machine *M* such that L(*M*) = L(*N*). (Our construction is essentially identical to that in the textbook.) It was sufficient to argue that *M* simulates the accepting behavior of *N*, even though it does not simulate the rejecting behavior. To be explicit, for any input *w*,

- if
*N*accepts*w*, then*M*accepts*w*, - if
*N*rejects*w*, then*M*loops on*w*, and - if
*N*loops on*w*, then*M*loops on*w*.

We would like to design *M* better, so that it simulates not just the accepting behavior, but also the rejecting behavior, of *N*. In class we discussed this idea: Add a fourth tape to *M*. When *M* encounters a rejecting branch of *N*, it records that rejecting branch on its fourth tape. If *M* ever discovers that all branches of *N* lead to rejection, then *M* rejects.

A. Does this idea work? Explain in detail how it works, or why it will not work.

B. If the idea works, then how does it affect the running time of *M*? Is the blowup in running time better or worse than with the old *M*? How much better or worse?

C. If the idea does not work, then can you come up with another idea, that does work?