2
$\begingroup$

How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?

$\endgroup$
  • $\begingroup$ Non-deterministic turing machines are exponentially more powerful than determisistic turing machines. 'nuff said. $\endgroup$ – John Dvorak Nov 7 '13 at 17:22
  • $\begingroup$ @JanDvorak: Good point. What I meant to ask for was a machine that recognized the same language, not one that performed with the same complexity. $\endgroup$ – Kevin Nov 7 '13 at 17:36
  • 1
    $\begingroup$ What research have you done? Have you looked in a standard textbook on automata theory? This is likely to be covered in most such textbooks. We expect you to do some research before asking here. $\endgroup$ – D.W. Nov 7 '13 at 18:44
  • 1
    $\begingroup$ @JanDvorak You should be careful stating unproven claims as truth. Also, your comment does not relate to the question at all. $\endgroup$ – Raphael Nov 8 '13 at 13:11
  • 1
    $\begingroup$ Jan Dvorak's original comment was posted when my question was more ambiguous about what I was looking for. $\endgroup$ – Kevin Nov 8 '13 at 19:40
5
$\begingroup$

The deterministic machine simulates all possible computations of a nondeterministic machine, basically in parallel. Whenever there are two choices, the deterministic machine spawns two computations. This proces is sometimes called dovetailing. The tape of the deterministic simulator contains a list of configurations of the nondeterministic one, and performs a step on each of these in turn. This requires quite some administration, and the capability to move aroud data when one of the simulated configurations extends its allotted space.

$\endgroup$
  • $\begingroup$ IOW, it's very difficult, but it's possible to do automatically. $\endgroup$ – John Dvorak Nov 7 '13 at 18:11
  • 1
    $\begingroup$ It can be useful to visualize the space of possible computations of a non-deterministic machine on some input as (binary) tree. The deterministic machine just traverses the whole tree in a breadth-first fashion. (Constructing this machine explicitly is sure to be messy.) $\endgroup$ – Raphael Nov 8 '13 at 13:14
  • 3
    $\begingroup$ @JanDvorak Conceptually, it's a quite simple idea. I think the simulation is easy enough to code in an higher programming language. It's just the compilation to TMs that yields "ugly" "code". $\endgroup$ – Raphael Nov 8 '13 at 16:50
2
$\begingroup$

a worthwhile question because the algorithm is not really so trivial to a neophyte and worth studying for its key/basic theoretical implications, and your question is not specifically limited to recursive languages! a key is to recognize the algorithm as a breadth first search of a (possibly infinite) graph of all possible transitions, ie exploration of all edges of a graph in parallel so to speak. (exercise: explain why the similar graph-traversal algorithm, depth first search cannot work.)

the construction is relevant to, and shows up in, the famous/fundamental Cook proof for the NP completeness of SAT. basically solutions of the SAT construction are 1-1 correspondence with NTM acceptance paths in P-time.

moreover there is significant theory (somewhat similar/analogous) of converting other nondeterministic machines to deterministic ones eg NFAs to DFAs. in general the complexity of the corresponding classes (deterministic vs nondeterministic ones) is open for many related questions.

see also

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.