0
$\begingroup$

If I have two Turing machines A and B, and I want to use an output of A as an input to B, how is it going to work? Can I just run A, keep the input tape, and then run B (without affecting the number of states A and B? Or do I have to combine an halting state of machine and an initial state of the other machine?

$\endgroup$
1
$\begingroup$

Given two Turing machines $M_1$ and $M_2$, assume that their state sets are disjoint, i.e, $Q_1 \cap Q_2 = \emptyset$. Define $\Sigma_3 = \Sigma_1 \cup \Sigma_2, Q_3=Q_1\cup Q_2, F_3=F_2$.

Modify $M_1$ so that it prints its output starting from the first (leftmost) tape cell, then move the tape head to the leftmost cell and enter the $M_2$'s start state. This makes sure that $M_2$'s input is the $M_1$'s output. You may also need to add new states to $Q_3$ .

$\endgroup$

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.