Examples of Turing Machines

Show that $A=\left\{ w w^{R} \mid w \in \left\{ 0,1\right\}^{*}\right\}$ is Turing-acceptable.

Show that the following function is Turing-computable:

Show that $\left\{ w w^{R} \mid w \in \left\{ 0,1\right\}^{*}\right\}$ is Turing-decidable.

Show that the function $\pi_{2}^{2}\left(n_{1}, n_{2}\right)=n_{2}$, for $n_{1}, n_{2} \in \mathbf{N}$, is Turing-computable.

Find a Turing machine that computes the function

For $1 \leq i \leq k$, show that function $\pi_{i}^{k}\left(x_{1}, x_{2}, \cdots , x_{k}\right)=x_{i}$ on natural numbers is Turing-computable.

Show that, for any $1 \leq i \leq k+1$, the function

on strings over $\left\{ a, b\right\}$ is Turing-computable.

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

Construct DTM's for procedures $R$ and $T$ of Example 4.9.

Construct DTM's to decide the following languages:

Construct DTM's to compute the following functions:

For any given DTM $M$, construct a new DTM $M^{\prime }$ such that $M^{\prime }$ accepts exactly the same set of strings as that of $M$ (i.e., $L(M)=L\left(M^{\prime }\right)$) but when $M^{\prime }$ halts its tape is always empty (i.e., the final configuration is always $(h, \mathrm{BB})$).

Consider the regular language $L=\left\{ 0^{n_{1}} 10^{n_{2}} 1 \cdots 10^{n_{k}} \mid k \geq 5\text{, }n_{1}, \ldots , n_{k} \geq 0, n_{j} \equiv n_{j+1}(\bmod 5)\text{, where }j=(k \bmod 5)+1\right\}$.

In the proof of Theorem 4.10, we observe that if the DTM $M$ visits, during its computation on input $x$, some blank cells to the right of the input, then the NFA $M^{\prime }$ needs to move, after reading all input symbols, to other states by $\varepsilon$-moves to decide whether it accepts the input. Show that this is not necessary. That is, we can eliminate all $\varepsilon$-moves in $\delta^{\prime }$ and change the set $F$ of the final states to include all crossing sequences $S$ which contain $\langle h, R\rangle$ as the last pair such that $S \stackrel{\mathrm{~ B}}{\rightleftharpoons } S_{1} \stackrel{\mathrm{~ B}}{\rightleftharpoons } S_{2} \stackrel{\mathrm{~ B}}{\rightleftharpoons } \ldots \stackrel{\mathrm{~ B}}{\rightleftharpoons }(\langle h, R\rangle )$. Explain how to determine the final set $F$.

We consider an extension of read-only DTM's. A one-pebble, read-only DTM (or, simply, one-pebble DTM) is a read-only DTM $M$ with the additional capability that it can mark a specific cell of the input tape by putting a pebble on it. The machine $M$ has only one pebble, and so at any time the tape can have at most one marked symbol. More precisely, a one-pebble DTM $M$ is a DTM $M=\left(Q, \Sigma , \Gamma , \delta , s^{*}\right)$, where $Q=Q_{1} \cup \left\{ q^{*} \mid q \in Q_{1}\right\}$ for some finite set $Q_{1}, \Gamma =\Sigma \cup \left\{ \mathrm{B}\right\} \cup \left\{ a^{*} \mid a \in \Sigma \text{ or }a=\mathrm{B}\right\} , s \in Q_{1}$, and $\delta$ satisfies the following properties: For any $q \in Q_{1}$ and $a \in \Sigma \cup \left\{ \mathrm{~ B}\right\}$,

1. $\delta (q, a)=(p, a, D)$ for some $p \in Q_{1}$ and $D \in \left\{ L, R\right\}$.

2. $\delta \left(q, a^{*}\right)$ is either $\left(p, a^{*}, D\right)$ or $\left(p^{*}, a, D\right)$ for some $p \in Q_{1}$ and $D \in \left\{ L, R\right\}$.

3. $\delta \left(q^{*}, a\right)$ is either $\left(p^{*}, a, D\right)$ or $\left(p, a^{*}, D\right)$ for some $p \in Q_{1}$ and $D \in \left\{ L, R\right\}$.

4. $\delta \left(q^{*}, a^{*}\right)$ is undefined. (In the above, the superscript * denotes the pebble. So, a state $q^{*}$ indicates that $M$ is holding the pebble at its finite control, and all tape symbols are unmarked; and a state $q \in Q_{1}$ indicates that the pebble is in an input cell. Note that property (i) indicates that $M$ cannot mark a cell if it does not hold the pebble in its finite control now.)

5. Construct a one-pebble DTM $M$ such that on each input $x$ of length $n \geq 2, M$ halts in exactly $n^{2}$ moves.

6. Show that for each read-only DTM $M$, there exist two constants $c$ and $d$ such that if $M$ halts on an input $x$ of length $n \geq 1$, then it must halt within $c n+d$ moves.

7. Show that for each one-pebble DTM $M$, there exist two constants $c$ and $d$ such that if $M$ halts on an input $x$ of length $n \geq 1$, then it must halt within $c n^{2}+d$ moves.

8. Show that if $L$ is a regular language, then there is a one-pebble DTM $M$ that accepts the language $\operatorname {SQRT}(L)$. (Recall that $\mathrm{SQRT}(L)$ is defined in Example 2.44 as $\left\{ x\left|(\exists y)\right| y\left|=|x|^{2}, x y \in \right. L\right\}$.)

In this exercise, we prove that the language accepted by a one-pebble DTM must be regular. Assume that $M=\left(Q, \Sigma , \Gamma , \delta , s^{*}\right)$ is a one-pebble DTM with $Q=Q_{1} \cup \left\{ q^{*} \mid q \in Q_{1}\right\}$. Also assume that $M$ operates on an input $x$ and visits cells $C_{0}, C_{1}, \ldots , C_{n}$, with symbol $s_{i}$ in cell $C_{i}$, for $i=0,1, \ldots , n$ (i.e., $s_{0} s_{1} \cdots s_{n}=\mathrm{B} x \mathrm{~ B} \cdots \mathrm{~ B}$). For each $i, 0 \leq i \leq n$, define a partial function $f_{i}: Q_{1} \rightarrow Q_{1}$ as follows: If $\delta \left(q, s_{i}^{*}\right)=\left(p, s_{i}^{*}, D\right)$ for some $p \in Q_{1}$ and $D \in \left\{ L, R\right\}$, then $f_{i}(q)$ is the next state $r \in Q_{1} (r \neq h)$ at which $M$ returns to cell $C_{i}$. Otherwise, $f_{i}(q)$ is undefined. That is, the function $f_{i}$ encodes the states of $M$ when it visits cell $C_{i}$ with the pebble in cell $C_{i}$ (similar to a crossing sequence of a read-only DTM). Note that $f_{i}$ depends on both machine $M$ and input $x$.

We consider another extension of read-only DTM's. A DTM $M$ is called a read/erase-only DTM if it can, at each move, only read an input symbol and/or erase it (i.e., replace the original symbol by $B$). That is, a DTM $M=(Q, \Sigma , \Gamma , \delta , s)$ is a read/erase-only DTM if $\Gamma =\Sigma \cup \left\{ \mathrm{B}\right\}$, and the transition function $\delta$ satisfies the following property: For any $q \in Q$ and $a \in \Sigma \cup \left\{ \mathrm{~ B}\right\} , \delta (q, a)$ is either $(p, a, D)$ or $(p, \mathrm{~ B}, D)$ for some $p \in Q$ and $D \in \left\{ L, R\right\}$.