Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?

  • 2
    $\begingroup$ What do you mean "with transitional functions"? $\endgroup$ – 6005 Apr 8 at 0:41

There is no such problem. All problems that can be solved (i.e., decided) by a non-deterministic Turing machine $T$ can also be solved by a deterministic Turing machine that simulates $T$.

| cite | improve this answer | |
  • $\begingroup$ Can you give an example of a NDTM? (state, stack symbol) --> more than one transitional functions? $\endgroup$ – Shyamalendu Kandar Apr 23 at 12:32
  • $\begingroup$ Just any non deterministic Turing machine? $\langle \{ q_0 \}, \{ \epsilon \}, q_0, \epsilon, \emptyset, \delta \rangle$, where $\delta=\{ (q_0, \epsilon, q_0, \epsilon, \texttt{left}), (q_0, \epsilon, q_0, \epsilon, \texttt{right}) \}$. I'm following this definition. $\endgroup$ – Steven Apr 23 at 17:17
  • $\begingroup$ Which language does it accept? $\endgroup$ – Shyamalendu Kandar Apr 24 at 7:53
  • $\begingroup$ The empty language. It has no accepting states. $\endgroup$ – Steven Apr 24 at 7:55

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.