1
$\begingroup$

I have this assignment

  1. Describe in words how a DTM can simulate a NTM
  2. Describe in wordshow a NTM can simulate a DTM

I'm working on this request and I'm crushing with the comparison.

1-I understand that every NTM can be represented by a DTM with a tree structure, that represents every step of the different possibilities of a NTM. Every step should simulate with n tapes the configuration states of the NTM with the DTM etc.

2-For this I'm a little lost, I think you can't have a DTM simulated by an NTM, the multiplicity of states allowed in NTM with guesses makes difficult to create a deterministic process o linear, ¿I'm going in the right path?.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

NDTM may use multiple transitions which are allowed, but these are not required. Think of it in another way, DTM is already NDTM that doesn't use possibility of multiple paths, so it is not much of simulation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks!, you point me in the right direction. $\endgroup$
    – user2668676
    Apr 30, 2019 at 15:12
0
$\begingroup$

A nondeterministic Turing machine has zero or more possible transitions in every configuration; a deterministic one has exactly one. One is "zero or more".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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