2013 May 1,

CS 254: Day 14

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?