3
$\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$
3
$\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$
  • $\begingroup$ So instead of choosing randomly between different transition functions, you choose randomly between intermediary states? $\endgroup$ – shinzou Jun 1 '17 at 16:14
  • 1
    $\begingroup$ It's not random choice, but rather non-deterministic choice. $\endgroup$ – Yuval Filmus Jun 1 '17 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 Jun 1 '17 at 17:33
  • 1
    $\begingroup$ It is still an NDTM, but now at each step there are only two choices. $\endgroup$ – Yuval Filmus Jun 1 '17 at 17:35

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.