4
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Non-deterministic turing machines are exponentially more powerful than determisistic turing machines. 'nuff said. $\endgroup$ Nov 7, 2013 at 17:22
  • 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, 2013 at 18:44
  • 1
    $\begingroup$ @D.W. I had difficulty finding resources on-line about this question, so I figured that having an easy-to-find SE question about the topic would be helpful to others. I will, of course, reference my textbook for more help myself. $\endgroup$
    – Kevin
    Nov 7, 2013 at 21:11
  • 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, 2013 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, 2013 at 19:40

2 Answers 2

7
$\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$
3
  • $\begingroup$ IOW, it's very difficult, but it's possible to do automatically. $\endgroup$ Nov 7, 2013 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, 2013 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, 2013 at 16:50
4
$\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 and acknowledge you have read our privacy policy.

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