0
$\begingroup$

I've seen questions about how an NTM could simulate a DTM and this seems pretty straightforward to me. However, my text book says you can also simulate an NTM using a DTM.

How would this work? I'm especially curious on how to define the transitions, since in the DTM, each transition would have to be deterministic.

$\endgroup$
2
  • $\begingroup$ Would you be able to program it in a normal programming language? $\endgroup$
    – Pål GD
    Commented Jan 23, 2022 at 20:37
  • $\begingroup$ Ye,s I'd probably use BFS and "step through" the different programs one at a time (or $n$ steps at a time if using iterative deepening). D.W. gave the term I was looking for though. I didn't know this form of programming could be generalized like that (or at least didn't think of it) $\endgroup$ Commented Jan 23, 2022 at 20:40

1 Answer 1

1
$\begingroup$

You use dovetailing to simulate all possible execution paths of the NTM.

$\endgroup$
1
  • $\begingroup$ That's what I was looking for, thanks! $\endgroup$ Commented Jan 23, 2022 at 20:38

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.