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 '20 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$.

  • $\begingroup$ Can you give an example of a NDTM? (state, stack symbol) --> more than one transitional functions? $\endgroup$ Apr 23 '20 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 '20 at 17:17
  • $\begingroup$ Which language does it accept? $\endgroup$ Apr 24 '20 at 7:53
  • $\begingroup$ The empty language. It has no accepting states. $\endgroup$
    – Steven
    Apr 24 '20 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.