4
$\begingroup$

Continuing from this answer: https://cs.stackexchange.com/a/56072/43035

I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two transition functions $\delta_0',\delta_1'$. How will conflicts be handled?

For example: $\delta_1(q_1, a) = (q_2, b, R)\\ \delta_2(q_1, a) = (q_3, c, L)\\ \delta_3(q_1, a) = (q_4, d, R)$

How can you map $\delta_3$?

$\endgroup$

1 Answer 1

4
$\begingroup$

Suppose that you have three options $o_1,o_2,o_3$.

You first guess whether to apply $o_1$ or not; if not, you stay in place.

If you didn't apply $o_1$, you guess whether to apply $o_2$ or $o_3$.

Here is how to implement it using transitions, using your example: $$ \begin{align*} &\delta_1(q_1,a) = (q_2,b,R) \\ &\delta_2(q_1,a) = (q_s,a,R) \\ &\delta_1(q_s,\sigma) = (q_t,\sigma,L) \\ &\delta_2(q_s,\sigma) = (q_t,\sigma,L) \\ &\delta_1(q_t,a) = (q_3,c,L) \\ &\delta_2(q_t,a) = (q_4,d,R) \end{align*} $$ Here $q_s,q_t$ are new states, and $\sigma$ is any tape symbol.

$\endgroup$
4
  • $\begingroup$ So instead of choosing randomly between different transition functions, you choose randomly between intermediary states? $\endgroup$
    – shinzou
    Commented Jun 1, 2017 at 16:14
  • 1
    $\begingroup$ It's not random choice, but rather non-deterministic choice. $\endgroup$ Commented Jun 1, 2017 at 16:36
  • $\begingroup$ Wait a second, in the answer I linked he said this is a way to turn an NDTM to DTM, but if there are still ND choices then how is it a DTM? $\endgroup$
    – shinzou
    Commented Jun 1, 2017 at 17:33
  • 1
    $\begingroup$ It is still an NDTM, but now at each step there are only two choices. $\endgroup$ Commented Jun 1, 2017 at 17:35

Your Answer

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

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