Math Problems Vault

Problem 302

Construct a Turing machine that performs the following task: given an input consisting of one or more words $w_{1} \Lambda \ldots \Lambda w_{n}$ over the alphabet $\Sigma$ (possibly $n=1$ ), produce an output that doubles the last of the words: $w_{1} \Lambda \ldots \Lambda w_{n} \Lambda w_{n}$ .

?

Problem 303

Construct a Turing machine that compares two input words over the alphabet $\left\{ a, b, c\right\}$ lexicographically. It must compute the dictionary-order function:

f(x, y)= \begin{cases} a, & \text{ if } x<y \\ b, & \text{ if } x=y \\ c, & \text{ if } y<x \end{cases}

?

Problem 304

Construct programs of Turing machines that compute the following word functions in the alphabet $\Sigma =\left\{ a, b, c\right\}$ :

?

(a)

cyclic permutation of letters: $f(x w)=w x, x \in \Sigma$ ;

(b)

cyclic permutation of words: $f\left(w_{1}, \ldots , w_{n}\right)=\left(w_{2}, \ldots , w_{n}, w_{1}\right)$ ;

(c)

"reversal" of a sequence of words: $f\left(w_{1}, \ldots , w_{n}\right)=\left(w_{n}, \ldots , w_{1}\right)$ ;

(d)

doubling each letter: $f\left(x_{1} \ldots x_{n}\right)=x_{1} x_{1} \ldots x_{n} x_{n}$ ;

(e)

finding the image under the homomorphism $\varphi : \varphi (a)=a, \varphi (b)=c b, \varphi (c)=\varepsilon$ ;

(f)

removal of all single letters $a$ standing at even positions;

(g)

checking whether two words contain the same number of letters $a$ (the result equals 1 if the answer is "yes", 0 if "no");

(h)

checking whether a word is a palindrome (that is, symmetric);

(i)

checking whether the word contains two runs of letters $a$ of the same length;

(j)

checking whether the counts of letters $a, b$ and $c$ in the word form an increasing arithmetic progression.

Problem 305

Construct a Turing machine to convert the representation of a number from binary to unary, input alphabet $\left\{ 0,1\right\}$ .

?

Problem 306

Construct programs of one-way Turing machines that compute the following arithmetic functions in the unary system:

?

(a)

$x+y$ ;

(b)

$\lfloor x-y\rfloor$

(c)

$x y$

(d)

comparison $x<y$ ;

(e)

exponentiation: $x^{y}$ ;

(f)

square root: $\lfloor \sqrt{x}\rfloor$ ;

(g)

logarithm: $\left\lfloor \log_{2} x\right\rfloor ;$

(h)

integer division: $\lfloor x / y\rfloor$ ;

(i)

remainder: $x \bmod y$ ;

(j)

the function selecting the $m$ -th argument: $\mathrm{id}_{m}, m$ — a predetermined constant.

Problem 307

(a)(b)(c)(d)

Given Turing machines with a standard terminal configuration $\mathfrak {M}_{i}$ , each of which computes a word function $f_{i}(x)$ in time $t_{i}(x)$ , $i=1, \ldots , n$ . Indicate how to construct, and estimate the running time of,

?

(a)

the machine $\mathfrak {M}_{1} ; \ldots ; \mathfrak {M}_{n}$ , computing the function $g_{1}(x)=f_{n}\left(\ldots f_{1}(x) \ldots \right)$ ;

(b)

the machine $\operatorname {par}\left(a, \mathfrak {M}_{1}, \ldots , \mathfrak {M}_{n}\right)$ , computing the function

g_{2}\left(x_{1} a x_{2} a \ldots a x_{n}\right)=f_{1}\left(x_{1}\right) a f_{2}\left(x_{2}\right) a \ldots a f_{n}\left(x_{n}\right) ;

(c)

the machine $\operatorname {if}\left(\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3}\right)$ , computing the function

g_{3}(x)= \begin{cases} \mathfrak {M}_{2}(x), & \text{ if } \mathfrak {M}_{1}(x) \text{ is nonempty, } \\ \mathfrak {M}_{3}(x), & \text{ if } \mathfrak {M}_{1}(x) \text{ is empty; } \end{cases}

(d)

the machine $\operatorname {while}\left(\mathfrak {M}_{1}, \mathfrak {M}_{2}\right)$ , computing the function $g_{4}(x)=x_{q}$ , where $q$ is the smallest natural number for which $\mathfrak {M}_{1}\left(x_{q}\right)$ is empty, with $x_{0}=x$ and $x_{j+1}=\mathfrak {M}_{2}\left(x_{j}\right)$ . Assume that $\left|x_{j}\right| \leqslant L(x)$ and $t_{i}\left(x_{j}\right) \leqslant T_{i}(x)$ .

Problem 308

(a)(b)(c)(d)

Using the Turing machines from the previous problems, construct programs of Turing machines that compute the following functions:

?

(a)

$f_{1}(x, y)= \begin{cases} x^{2} y^{3}, & \text{ if } x<y, \\ \lfloor (x+y) / 2\rfloor , & \text{ otherwise; } \end{cases}$

(b)

$f_{2}(x, y)= \begin{cases} \lfloor \sqrt{x}\rfloor , & \text{ if } x+1 \geqslant y, \\ 2(x+y), & \text{ otherwise; } \end{cases}$

(c)

$f_{3}(x, y)= \begin{cases} \left\lfloor \log_{2}(1+\lfloor x / y\rfloor )\right\rfloor , & \text{ if } x>2 y, \\ x y, & \text{ otherwise; } \end{cases}$

(d)

$f_{4}(x, y)= \begin{cases} \lfloor \sqrt{x}\rfloor , & \text{ if } 2 x \geqslant y, \\ x \bmod y, & \text{ otherwise. } \end{cases}$

Problem 309

Show how the execution of the following commands can be organized on an ordinary Turing machine:

?

(a)

$q, a \rightarrow p, b$ , return — return the head to whichever of the neighboring cells it came from into the current one;

(b)

$q, a \rightarrow p, b$ , zero — return the head to cell zero;

(c)

$q, a \rightarrow p, b$ , mirror — move the head to cell $-i$ , if it was in the cell numbered $i$ ;

(d)

$q, a \rightarrow p, b$ , double — move the head to cell $2 i$ , if it was in the cell numbered $i$ ;

(e)

$q, a \rightarrow p, b$ , next — move the head to the nearest cell to the right of the current one that contains $a$ (if one exists, otherwise the head stays in place);

(f)

$q, a \rightarrow p, \operatorname {insert} b$ — shift the current cell and all cells to the right of it one position to the right and write the symbol $b$ into the freed cell; the head ends up in the new cell;

(g)

$q, a \rightarrow p$ , restore, $s$ — replace the symbol $a$ with the one that was in the cell in the initial configuration.

Problem 310

Implement the Turing machine from Examples 111 on p. 409 and 112 on p. 410 without extending the alphabet.

Example 111: a Turing machine over the alphabet $\Sigma =\left\{ a,b,c\right\}$ computing the function $f\left(w_{1}w_{2}\right)=w_{1}$ for words with $\left|w_{1}\right|-\left|w_{2}\right| \in \left\{ 0,1\right\}$ (i.e. erase the second half of the word, keeping the middle symbol if the length is odd), implemented by extending the alphabet with primed symbols $a^{\prime }, b^{\prime }, c^{\prime }$ .

Example 112: a Turing machine over the alphabet $\Sigma =\left\{ 0,1\right\}$ that adds two nonempty binary numbers given on the tape, implemented by extending the alphabet with primed symbols $0^{\prime }, 1^{\prime }$ .

?

Problem 311

Complete the construction of the Turing machine from Theorem 156 on p. 413.

Theorem 156: For every Turing machine $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ one can construct a $\Sigma$ -equivalent Turing machine $\mathfrak {N}$ having a standard terminal configuration (i.e. one in which, at the moment of halting, the head is in cell zero and the tape holds only the result, with no leftover marker symbols).

?

Problem 312

A different approach, compared to the construction of Theorem 157 on p. 417, to simulating a two-way tape on a one-way tape consists in storing the contents of the nonnegative half of the tape of $\mathfrak {M}$ in cells with odd numbers, and the contents of the left half — in cells with even numbers. That is, the new tape will have the form $\beta (0)=\# , \beta (2 x+1)=\alpha (x)$ and $\beta (2 x)=\alpha (-x)$ for $x>0$ . Construct a program for a one-way machine $\mathfrak {N}$ that implements this approach.

Theorem 157: For every Turing machine $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ there exists a $\Sigma$ -equivalent one-way Turing machine $\mathfrak {N}$ having a standard terminal configuration. (The construction given in the proof of Theorem 157 folds the two-way tape in half using two-tier symbols, so that cell $i$ of $\mathfrak {N}$ 's tape stores a pair consisting of the symbol from cell $i+1 \geqslant 0$ of $\mathfrak {M}$ 's tape on top and the symbol from cell $-i \leqslant 0$ on the bottom; this problem asks for an alternative, non-two-tier encoding achieving the same goal.)

?

Problem 313

Prove that the one-way Turing machine $\mathfrak {N}$ , constructed in Theorem 157 on p. 417, correctly simulates the original machine $\mathfrak {M}$ .

Theorem 157: For every Turing machine $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ there exists a $\Sigma$ -equivalent one-way Turing machine $\mathfrak {N}$ having a standard terminal configuration. (The construction in the proof uses two-tier symbols to fold the two-way tape of $\mathfrak {M}$ in half: cell $i$ of $\mathfrak {N}$ 's tape holds a pair whose top is $\mathfrak {M}$ 's cell $i+1$ and whose bottom is $\mathfrak {M}$ 's cell $-i$ , so nonnegative and negative cells of $\mathfrak {M}$ 's tape are interleaved onto $\mathfrak {N}$ 's single-direction tape.)

?

Problem 314

Show how to extract the output words from the tape code $\rho (\alpha )$ (Theorem 159 on p. 426).

For a one-way tape $\alpha$ over alphabet $\Sigma =\left\{ a_{0}, a_{1}, \ldots , a_{k}\right\}$ (with $a_{0}=\Lambda$ ), holding at each moment a sequence $\# a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}} \Lambda \Lambda \ldots$ , the tape code is $\rho (\alpha )=\sum_{j=1}^{\infty } \alpha (j) \cdot k^{j-1}$ , i.e. reading the sequence of symbol indices as the digits of a number in base $k$ (only finitely many terms are nonzero). Theorem 159: every Turing-computable word function is program-computable — the proof simulates a Turing machine $\mathfrak {M}$ by a labeled program $\Pi$ that stores $\mathfrak {M}$ 's configuration $(q, i, \alpha )$ using a variable $r$ holding the tape code $\rho (\alpha )$ ; at the end, the resulting tape code must be decoded back into the sequence of output words, which is exactly what this problem asks for.

?

Problem 315

Show how, on a Turing machine, to construct the unary representation of the input, and to recover the output from the unary representation (Theorem 160 on p. 429), without extending the alphabet.

Theorem 160: If a word function $f:\Omega^{*} \rightarrow \Omega^{*}$ is computable on a Turing machine $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ with $\Omega \subseteq \Sigma$ , then it is computable on a one-way Turing machine $\mathfrak {N}=(Q^{\prime }, \Sigma^{\prime }, P^{\prime }, q_{0}^{\prime })$ with no alphabet extension, i.e. $\Sigma^{\prime }=\Omega \cup \left\{ \Lambda , \# \right\}$ . (The proof builds $\mathfrak {N}$ by first converting the input into the unary representation of its tape code $\rho (\alpha_{0})$ , then running a machine $\mathfrak {N}_{1}$ computing the same function on that unary representation — as given by Theorem 158 — and finally recovering the output word from the unary representation of the resulting tape code; this problem asks for these two conversion steps.)

?

Problem 316

Show how to simulate on a Turing machine the operation of a labeled program in the binary system (Theorem 158 on p. 422).

Theorem 158: Every program-computable function $f$ is Turing-computable without extending the alphabet. (The proof simulates a labeled program $\Pi$ with variables $x_{1}, \ldots , x_{k}$ by a one-way Turing machine whose configuration $(q_{\alpha }, 0, \kappa )$ mirrors $\Pi$ 's configuration $(\alpha , \sigma )$ , storing the unary representations of $\sigma (x_{1}), \ldots , \sigma (x_{k})$ on the tape, separated by blanks; the number system chosen there is unary, and this problem asks to show that the binary system also works.)

?

Problem 317

Construct a universal Turing machine, implementing items 1)-21) from Theorem 161 on p. 430.

Theorem 161: For every alphabet $\Sigma$ there exists a $\Sigma$ -universal Turing machine $\mathfrak {U}$ , i.e. a machine such that for every Turing machine $\mathfrak {M}=(Q,\Sigma ,P,q_{0})$ there is an input $c_{\mathfrak {M}}$ (encoding $\mathfrak {M}$ 's program) for which $\mathfrak {U}(c_{\mathfrak {M}}, x) = \mathfrak {M}(x)$ for every input $x$ .

?