Math Problems Vault

Problem 584

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$

?

Problem 585

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.

?

Problem 586

(a)(b)(c)

Let $\Sigma$ be an arbitrary alphabet not containing $\Lambda$ . We need to construct a Turing machine $\mathfrak {C}$ that swaps two arguments, more precisely, that transforms any input of the form $x \Lambda y$ ( $x$ and $y$ are words in the alphabet $\Sigma )$ into the output $y \Lambda x$ with a standard final configuration.

Determine which of the following programs can be used for the machine $\mathfrak {C}$ . In the program texts, $q_{0}$ is the initial state, $\alpha , \beta$ are arbitrary symbols from $\Sigma$ , and $\gamma , \delta$ are arbitrary symbols from $\Sigma \cup \left\{ u, v\right\}$ , where $u, v$ are new symbols.

?

(a)

$P_{1}=\left\{ q_{0}, \alpha \rightarrow q_{1}^{\alpha }, \Lambda ,+1 ; q_{1}^{\alpha }, \beta \rightarrow q_{1}^{\alpha }, \beta ,+1 ; q_{1}^{\alpha }, \Lambda \rightarrow q_{2}, \alpha ,+1 ; q_{2}, \alpha \rightarrow q_{3}^{\alpha }, \Lambda ,-1 ; q_{2}, \Lambda \rightarrow q_{4}, \Lambda ,-1 ; q_{3}^{\alpha }, \beta \rightarrow q_{3}^{\alpha }, \beta ,-1 ; q_{3}^{\alpha }, \Lambda \rightarrow q_{0}, \alpha ,+1 ; q_{4}, \alpha \rightarrow q_{4}, \alpha ,-1 ; q_{4}, \Lambda \rightarrow q_{5}, \Lambda ,-1 ; q_{5}, \alpha \rightarrow q_{5}, \alpha ,-1 ; q_{5}, \Lambda \rightarrow q_{6}, \Lambda ,+1\right\} ;$

(b)

$P_{2}=\left\{ q_{0}, \alpha \rightarrow q_{0}, \alpha ,+1 ; q_{0}, \Lambda \rightarrow q_{1}, u,+1 ; q_{1}, \alpha \rightarrow q_{1}, \alpha ,+1 ; q_{1}, \Lambda \rightarrow q_{2}, v, 0 ; q_{2}, \gamma \rightarrow q_{3}^{\gamma }, \Lambda ,-1 ; q_{3}^{\gamma }, \delta \rightarrow q_{3}^{\delta }, \gamma ,-1 ; q_{3}^{\alpha }, \Lambda \rightarrow q_{9}^{\alpha }, \Lambda ,+1 ; q_{3}^{u}, \Lambda \rightarrow q_{6}, \Lambda ,+1 ; q_{6}, \alpha \rightarrow q_{6}, \alpha ,+1 ; q_{6}, v \rightarrow q_{7}, \Lambda ,-1 ; q_{7}, \alpha \rightarrow q_{7}, \alpha ,-1 ; q_{7}, \Lambda \rightarrow q_{8}, \Lambda ,+1 ; q_{9}^{\alpha }, \delta \rightarrow q_{9}^{\alpha }, \delta ,+1 ; q_{9}^{\alpha }, \Lambda \rightarrow q_{2}, \alpha , 0\right\} ;$

(c)

$P_{3}=\left\{ q_{0}, \alpha \rightarrow q_{0}, \alpha ,+1 ; q_{0}, \Lambda \rightarrow q_{1}, u,-1 ; q_{1}, \alpha \rightarrow q_{1}, \alpha ,-1 ; q_{1}, \Lambda \rightarrow q_{2}, \Lambda ,+1 ; q_{2}, \alpha \rightarrow q_{3}^{\alpha }, v,+1 ; q_{3}^{\gamma }, \delta \rightarrow q_{3}^{\delta }, \gamma ,+1 ; q_{3}^{\gamma }, \Lambda \rightarrow q_{6}, \gamma , 0 ; q_{6}, \alpha \rightarrow q_{7}^{\alpha }, \Lambda ,-1 ; q_{6}, u \rightarrow q_{8}, \Lambda ,-1 ; q_{7}^{\alpha }, \delta \rightarrow q_{7}^{\alpha }, \delta ,-1 ; q_{7}^{\alpha }, \Lambda \rightarrow q_{9}^{\alpha }, \Lambda ,+1 ; q_{8}, \alpha \rightarrow q_{8}, \alpha ,-1 ; q_{8}, u \rightarrow q_{8}, \Lambda ,-1 ; q_{8}, v \rightarrow q_{8}, \Lambda ,-1 ; q_{8}, \Lambda \rightarrow q_{4}, \Lambda ,+1 ; q_{9}^{\alpha }, \delta \rightarrow q_{3}^{\delta }, \alpha ,+1\right\}$ . $\circledast$

Problem 587

Construct a Turing machine that, for each input word of the form $a^{n} b^{k}$ , produces the result $a^{\lfloor (n+k) / 2\rfloor } b^{\lfloor (n+k) / 2\rfloor }$ . How the machine behaves on other inputs is irrelevant. Estimate the running time of the constructed machine. $\circledast$

?

Problem 588

Construct a Turing machine that, for each input word of the form $0^{n} 1^{k}$ , where $n>k>0$ , produces the result 0, and for all other words produces the result 1. Estimate the running time of the constructed machine. $\circledast$

?

Problem 589

Construct a Turing machine that transforms any input word $w \in \left\{ a, b\right\}^{*}$ into the output $a^{n} \Lambda b^{m}$ , where $n$ is the number of letters $a$ and $m$ is the number of letters $b$ in the word $w$ . In other words, the letters of the word are sorted and then separated. Estimate the running time of the constructed machine. $\circledast$

?

Problem 590

Let the alphabet $\Sigma$ not contain the symbols $\Lambda$ and *. Construct a Turing machine program that moves the last word on the tape, in the alphabet $\Sigma$ , from left to right to the place on the tape marked *. More precisely, from the tape $\alpha \Lambda w \Lambda^{n} *$ one should obtain $\alpha \Lambda \Lambda^{n} w$ , where $w \in \Sigma^{*}$ . $\circledast$

?

Problem 591

Construct a Turing machine performing the following task: given an input consisting of one or more words $w_{1} \Lambda \ldots \Lambda w_{n}$ in the alphabet $\Sigma$ (possibly $n=1$ ), construct an output by doubling the last of the words: $w_{1} \Lambda \ldots \Lambda w_{n} \Lambda w_{n}$ . $\circledast$

?

Problem 592

Prove that for any constant $k>1$ one can construct a Turing machine that solves problem 591 in time at most $n^{2} / k+O(n)$ , where $n$ is the total length of the input words. $\circledast$

?

Problem 593

Construct a Turing machine that compares two input words in the alphabet $\left\{ a, b, c\right\}$ lexicographically. This Turing machine must compute the dictionary function: $\circledast$

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

?

Problem 594

Construct Turing machine programs that compute the following dictionary 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 the sequence of words:

f\left(w_{1}, \ldots , w_{n}\right)=\left(w_{n}, \ldots , w_{1}\right)

(d)

doubling of 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 in 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. $\circledast$

Problem 595

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

?

Problem 596

Construct a Turing machine that, given the unary representation of three numbers, that is, an input of the form $\left.\left.\left.\right|^{n+1} \Lambda \right|^{k+1} \Lambda \right|^{m+1}$ , produces the result 0 if $0<n<k+m$ , and 1 otherwise. Estimate the running time of the constructed machine. $\circledast$

?

Problem 597

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

?

(a)

$x+y$ ;

(b)

$x \div y$ ;

(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: $\operatorname {id}_{m}$ , where $m$ is a predetermined constant. $\circledast$

Problem 598

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

Given Turing machines with standard final configuration $\mathfrak {M}_{i}$ , each of which computes a dictionary function $f_{i}(x)$ in time $t_{i}(x)$ , $i=1, \ldots , n$ . Describe 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}(\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3})$ , 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}(\mathfrak {M}_{1}, \mathfrak {M}_{2})$ , 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)$ . $\circledast$

Problem 599

(a)(b)(c)

Given the following Turing machines with standard final configuration: - $\operatorname {copy}(a)$ — copies the input, using the symbol $a$ as a separator between the original and the copy: $w \mapsto w a w$ ; - $\operatorname {replace}(a, b)$ — replaces the leftmost occurrence of the symbol $a$ with $b$ ; if there is no symbol $a$ , the input is unchanged; - $\operatorname {add}$ — adds two numbers written in the unary number system; - $\operatorname {mult}$ — multiplies two numbers written in the unary number system; - $\operatorname {nop}$ — does not change the input.

Determine which arithmetic functions are computed (in the unary number system) by the following Turing machines, constructed by the methods of problem 598 on the previous page:

?

(a)

$\operatorname {copy}(*) ; \operatorname {par}(*, \operatorname {copy}(\Lambda ), \operatorname {copy}(\Lambda )) ; \operatorname {par}(*, \operatorname {mult}, \operatorname {add}) ; \operatorname {replace}(*$ , $\Lambda$ ); $\operatorname {add}$ ;

(b)

$\operatorname {copy}(*) ; \operatorname {par}(*, \operatorname {copy}(\Lambda ), \operatorname {copy}(\Lambda )) ; \operatorname {par}(*, \operatorname {mult}, \operatorname {add}) ; \operatorname {par}(*$ , ( $\operatorname {copy}(\Lambda ) ; \operatorname {add}), \operatorname {nop}) ; \operatorname {replace}(*, \Lambda ) ; \operatorname {add} ;$

(c)

$\operatorname {copy}(*) ; \operatorname {par}(*,(\operatorname {copy}(\Lambda ) ; \operatorname {mult}), \operatorname {nop}) ; \operatorname {par}(*,(\operatorname {copy}(\Lambda ) ; \operatorname {add})$ , $\operatorname {nop}$ ); $\operatorname {replace}$$(*, \Lambda )$ ; $\operatorname {add}$ .

Problem 600

Given the Turing machines with standard final configuration from problem 599 on the preceding page, as well as the following: - $\operatorname {id}_{i}$ — returns the $i$ -th argument, or the empty word if the number of arguments is less than $i$ ; - $\operatorname {pos}_{i}$ — checks whether the $i$ -th argument is positive (numbers are written in unary), returning the empty word if it equals zero, or | if it is positive; - $\operatorname {dec}$ — decreases the argument by one if it is positive, otherwise leaves the input unchanged (numbers are written in unary). Determine which arithmetic functions (in the unary system) are computed by each of the Turing machines whose programs are shown schematically in Fig. 39 on the next page (see problem 598 on the preceding page). $\circledast$

?

Problem 601

(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}$ $\circledast$

Problem 602

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

?

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

$q, a \rightarrow p, \operatorname {insert} b$ — the current cell and all cells to its right are shifted one position to the right, and the symbol $b$ is written into the freed cell; the head ends up in the new cell;

(g)

$q, a \rightarrow p$ , restore, $s$ — the symbol $a$ is replaced by the symbol that was in the cell in the initial configuration. $\circledast$

Problem 603

Construct a Turing machine for problem 591 on p. 185, without enlarging the original alphabet $\Sigma$ . $\circledast$

?

Problem 604

(a)(b)

Implement the following Turing machines without extending the alphabet:

?

(a)

erase the second half of the word, leaving the central symbol if the length was odd;

(b)

add two numbers written in binary. $\circledast$

Problem 605

One of the approaches to simulating a two-way tape on a one-way tape consists in storing the contents of the non-negative half of the tape $\mathfrak {M}$ in the cells with odd numbers, and the contents of the left half in the 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}$ implementing this approach. $\circledast$

?

Problem 606

Prove that every arithmetic function $f(x)$ computable on some Turing machine $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}\right)$ in the unary number system can also be computed on a Turing machine $\mathfrak {N}$ whose tape alphabet contains only two symbols: $\Lambda$ and $\mid$ . Hint. To simulate one symbol $a_{i}$ of the alphabet $\Sigma$ , use a block of several consecutive cells containing the word $\left.\right|^{i} \Lambda^{k-i}$ , where $\Sigma =\left\{ a_{0}, \ldots , a_{k}\right\}$ . Replace each command of $\mathfrak {M}$ with a group of commands processing the corresponding block of cells. $\circledast$

?

Problem 607

A $k$ -tape Turing machine has $k$ tapes, each with its own head moving along it. A command of a $k$ -tape Turing machine has the form

q, a_{1}, a_{2}, \ldots , a_{k} \rightarrow p, b_{1}, b_{2}, \ldots , b_{k}, s_{1}, s_{2}, \ldots , s_{k},

where $q, p \in Q$ are states, $a_{1}, \ldots , a_{k}$ are the symbols observed by the heads on the corresponding tapes, $b_{1}, \ldots , b_{k}$ are the symbols written by the heads on the corresponding tapes, $s_{1}, \ldots , s_{k}$ are the directions of the head shifts on the corresponding tapes. The input data is written on the first tape, and the rest are empty in the initial configuration. The result is also placed on the first tape.

Prove that any function computable on a $k$ -tape Turing machine can also be computed on an ordinary Turing machine. By how much does the computation time increase in this case? $\circledast$

?

Problem 608

Show that palindromes (symmetric words) can be recognized on a two-tape Turing machine in time proportional to their length. $\circledast$

?