Tracing a Turing machine's configurations

Given a Turing machine $\mathfrak {M}=(\left\{ q, p, r\right\} ,\left\{ \Lambda , 0,1\right\} , P, q)$ with the following program $P=\left\{ q, 0 \rightarrow q, 0,+1 ; q, 1 \rightarrow q, 1,+1 ; q, \Lambda \rightarrow p, \Lambda ,-1 ; p, 0 \rightarrow p, 1,-1 ; p, 1 \rightarrow r, 0,-1 ; r, 0 \rightarrow r, 0,-1 ; r, 1 \rightarrow r, 1,-1\right\}$. What will the final configuration of this machine be when running on the input 1100? How many steps will be made? $\circledast$

There are three Turing machines $\mathfrak {M}_{i}=\left(Q, \Sigma , P_{i}, q\right), i=1,2,3$, which share the tape alphabet $\Sigma =\left\{ \Lambda , a, b\right\}$, the set of states $Q=\left\{ q, p, r, s, t\right\}$, and the initial state $q$. Their programs $P_{i}$ are given in the tables in Fig. 38 on the next page. Determine which of these machines transform every input word of the form $a^{2 n} b$, $n>0$, into the output $b a^{n}$. $\circledast$

Fig. 38: Programs of the machines from problem 585.

Fig. 38: Programs of the machines from problem 585.

Trace DTM $M_{1}$ of Example 4.1 and show the computation of $M_{1}$ on inputs aabba and bbbab.

Consider the DTM $M_{2}=(Q, \Sigma , \Gamma , \delta , s)$ with $Q=\left\{ s, q_{1}, q_{2}\right\} , \Sigma = \left\{ a, b\right\}$, $\Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, and

Consider the DTM $M_{3}=(Q, \Sigma , \Gamma , \delta , s)$, with $Q=\left\{ s, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\}$, $\Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, and

Consider the DTM $M_{4}=(Q, \Sigma , \Gamma , \delta , s)$, in which $Q, \Sigma$ and $\Gamma$ are the same as those of $M_{3}$, and $\delta$ is the same as $\delta$ of $M_{3}$ except for

.

What is $L\left(M_{4}\right)$?

For each of the following DTM's, trace the machine and show the computation on the given inputs:

Let $M_{1}$ be the one-tape DTM defined by the quintuple ($Q, \Sigma$, $\Gamma , \delta , s)$, where $Q=\left\{ s, q_{1}, q_{2}, q_{3}, p\right\} , \Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$ and $\delta$ is given by the following table:

Draw the transition diagram. What will be the computation on the input $a b b a$? On the input $a^{3} b$?

Which function $f(x)$ is computed by the machine $T$ with the following program of commands:

Let the machine $T$ have the following program:

Which functions $f_{1}(x), f_{2}(x_{1}, x_{2}), \ldots , f_{n}(x_{1}, \ldots , x_{n}), \ldots$ does this machine compute?

This exercise concerns TM $M_{2}$, whose description and state diagram appear in Example 3.7. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string.

This exercise concerns TM $M_{1}$, whose description and state diagram appear in Example 3.9. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string.