The Turing-Church Thesis and Undecidable Problems

Find the exact number of Turing machines of the form $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}\right)$ with a predetermined set of states $Q$ and tape alphabet $\Sigma$.

Let the following alphabet of Turing machines be fixed: $\left\{ \Lambda , \mid \right\}$. For the "busy beaver" function bb

Prove that the algorithmic reducibility relation $\leqslant_{m}$ is reflexive and transitive.

Prove the algorithmic undecidability of the test-data completeness problem $\mathrm{TEST}$. The problem consists of triples $(\pi (\mathfrak {M}), x, q)$ such that the state $q$ occurs in the computation of the Turing machine $\mathfrak {M}$ on input $x$.

Prove the algorithmic undecidability of the zero problem $\mathrm{ZERO}$. The problem $\mathrm{ZERO}$ consists of codes $\pi (\mathfrak {M})$ of Turing machines $\mathfrak {M}$ such that $\mathfrak {M}(x)=\varepsilon$ for all $x$. Hint. Reduce $\mathrm{TOTAL}$ to $\mathrm{ZERO}$.

Prove the algorithmic undecidability of the following equivalence problem $\mathrm{EQU}$. The problem $\mathrm{EQU}$ consists of pairs $(\pi (\mathfrak {M}), \pi (\mathfrak {N}))$ such that the machines $\mathfrak {M}$ and $\mathfrak {N}$ are equivalent. Hint. Reduce $\mathrm{ZERO}$ to $\mathrm{EQU}$.

Prove the algorithmic undecidability of the constant problem $\mathrm{CONST}$. The problem $\mathrm{CONST}$ consists of those $\pi (\mathfrak {M})$ such that the Turing machine $\mathfrak {M}$ returns the same result on any input, whenever it halts at all. Hint. Reduce the complement of $\mathrm{SELF}$ to $\mathrm{CONST}$.

Prove the algorithmic undecidability of the growth problem $\mathrm{GROW}$. The problem $\mathrm{GROW}$ consists of those $\pi (\mathfrak {M})$ such that the Turing machine $\mathfrak {M}$ computes an arithmetic function and $\mathfrak {M}(x)<\mathfrak {M}(y)$ holds for all $x<y$, whenever both values are defined. Hint. Reduce the complement of $\mathrm{SELF}$ to $\mathrm{GROW}$.

Prove that

Prove that for two decidable sets $A$ and $B$ of natural numbers, their "sum" $A+B=\left\{ x+y: x \in A, y \in B\right\}$ and "product" (not Cartesian!) $A \cdot B=\left\{ x \cdot y: x \in A, y \in B\right\}$ are also decidable sets.

Prove that for two decidable languages $L$ and $K$ over the alphabet $\Sigma$, their concatenation $L K$ and iteration $L^{*}$ are also decidable languages.

Let $A$ be a decidable set, and let $g(x)$ and $h(x)$ be g.r.f.'s. Prove that the function

is also general recursive.

Prove that the bounded halting problem is decidable. The problem consists of triples of the form $(\pi (\mathfrak {M}), x, t)$ such that the computation of the Turing machine $\mathfrak {M}$ on input $x$ halts in at most $t$ steps.

Show that under projection, a decidable language can become undecidable.

Show that the function arc grows unboundedly but is not monotonic: it is possible that $\operatorname {arc}(u)<\operatorname {arc}(v)$, even though the word $v$ is shorter than the word $u$.

Show that the function arc grows more slowly than every computable function: if a g.r.f. $f$ satisfies $f(x) \leqslant \operatorname {arc}(x)$ for all $x$, then $f$ is bounded.

Let $T(n)$ be the longest running time of a Turing machine with $n$ states on a blank tape. Prove that the function $T(n)$ is not computable.

Call the working region of a Turing machine $\mathfrak {M}$ on input $x$ the set of cells visited by the machine's head before it halts. Denote by $S(\mathfrak {M}, x)$ the size of the working region of the machine $\mathfrak {M}$ on input $x$. If the machine $\mathfrak {M}$ does not halt on $x$, then the value $S(\mathfrak {M}, x)$ may be arbitrary. Suppose that for the machine $\mathfrak {M}$ the function $S(\mathfrak {M}, x)$ is majorized by a general recursive function $S^{*}(x)$: $S(\mathfrak {M}, x) \leqslant S^{*}(x)$ for all $x$. Prove that the halting problem $\mathrm{HALT}_{\mathfrak {M}}$ for the machine $\mathfrak {M}$ is algorithmically decidable.

Prove that the function $S(\pi (\mathfrak {M}), x)$ from the previous problem is not computable.

For any pair of sets $A$ and $B$ define

Prove that for any set $C$ the condition $A \vee B \leqslant_{m} C$ holds if and only if $A \leqslant_{m} C$ and $B \leqslant_{m} C$.

A nonempty set $A$ is called recursively enumerable if it is the range of some g.r.f. $f$: $A=\left\{ f(0), f(1), f(2), \ldots \right\}$. Prove that

Prove that the set $\mathrm{TOTAL}$ is not recursively enumerable. Hint. For the universal Turing machine $\mathfrak {U}$, consider the function $\mathfrak {U}(f(x), x) \& a$ (concatenation with a nonempty symbol).

Prove that there exists a p.r.f. $f$ that cannot be extended to any g.r.f. $g$, that is, such that $f(x)=g(x)$ for all $x \in \operatorname {dom} f$. Hint. For the universal Turing machine $\mathfrak {U}$, consider the arithmetic function $f(x)=\mathfrak {U}(x, x)+1$.