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?.

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ Thanks!, you point me in the right direction. $\endgroup$ – user2668676 Apr 30 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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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