Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ What do you mean "with transitional functions"? $\endgroup$– Caleb StanfordCommented Apr 8, 2020 at 0:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$ Commented Apr 23, 2020 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$– StevenCommented Apr 23, 2020 at 17:17
-
$\begingroup$ Which language does it accept? $\endgroup$ Commented Apr 24, 2020 at 7:53
-
$\begingroup$ The empty language. It has no accepting states. $\endgroup$– StevenCommented Apr 24, 2020 at 7:55