Computability 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 fixed 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.

Implement a machine computing the reduction function $f$ from the proof of Theorem 170 on p. 446 in the case of the alphabet $\Sigma =\left\{ a, b\right\}$.

Theorem 170: The problem $\mathrm{TOTAL}$ is undecidable.

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 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 general recursive functions. 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 the construction of a projection, a language can go from decidable to undecidable.

Implement the machine $\mathfrak {M}$ from the proof of Theorem 173 on p. 451 in the case of the alphabet $\Sigma =\left\{ a, b\right\}$.

Theorem 173: The optimal-compression function arc is not computable.

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