# Convert a non-deterministic Turing machine into a deterministic Turing machine

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

• Non-deterministic turing machines are exponentially more powerful than determisistic turing machines. 'nuff said. Nov 7, 2013 at 17:22
• 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.
– D.W.
Nov 7, 2013 at 18:44
• @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. Nov 7, 2013 at 21:11
• @JanDvorak You should be careful stating unproven claims as truth. Also, your comment does not relate to the question at all. Nov 8, 2013 at 13:11
• Jan Dvorak's original comment was posted when my question was more ambiguous about what I was looking for. Nov 8, 2013 at 19:40

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.

• IOW, it's very difficult, but it's possible to do automatically. Nov 7, 2013 at 18:11
• 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.) Nov 8, 2013 at 13:14
• @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". Nov 8, 2013 at 16:50

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.