How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?
Asked By : Kevin
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16796
0 comments:
Post a Comment
Let us know your responses and feedback