HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Mapping many transition functions into two transition functions

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
functionsintotwotransitionmanymapping

Problem

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$?

Solution

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.

Context

StackExchange Computer Science Q#76171, answer score: 4

Revisions (0)

No revisions yet.