Diagonalization (Cantor/Turing argument)

Write out the details of the proof, using diagonalization, that $\mathcal{B}$ is uncountable.

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$.

Let $A$ be any set (not necessarily countable). Show that there does not exist a one-to-one correspondence between set $A$ and the set $2^{A}$ of all subsets of $A$.

Show that the set $F_{1}$ of all one-to-one, increasing functions from $\mathbf{N}$ to N is uncountable.

What are wrong with the following diagonalization proofs?

Assume that $A \subseteq \mathbf{N}$ is a set with the following properties: (i) $\phi_{n}$ is recursive for all $n \in A$, and (ii) for all recursive functions $f, f=\phi_{n}$ for some $n \in A$. Show that $A$ is not an r.e. set.

Show that set $A=\left\{ n \mid \phi_{n}\text{ halts on }n\text{ and its output is greater than }n\right\}$ is not a recursive set.

We say two sets $A$ and $B$ are recursively separable if there exists a recursive set $C$ such that $A \subseteq C$ and $B \subseteq \bar{C}$. Show that for any $n \neq m \in \mathbf{N}$, sets $K_{n}$ and $K_{m}$ are not recursively separable, where $K_{n}=\left\{ x \mid \phi_{x}(x)\text{ is defined and is equal to }n\right\}$.

Show that there exists a set $A$ such that both $A$ and $\bar{A}$ are infinite but neither has an infinite r.e. subset.

Show that there exist two r.e. sets $A$ and $B$ such that $A \leq_{m} B$ and $B \leq_{m} A$.

Describe the detail of the 3-worktape DTM $M^{*}$ of Theorem 6.16. In particular, describe how $M^{*}$ works using input $w$ as both the machine code for $M_{w}$ and as the input to $M_{w}$, while it is stored in the read-only input tape.

Find a recursive language $L$ that is not context-sensitive.

Show that the set $F$ of functions from $\mathbf{N}$ to $\left\{ 0,1\right\}$ is uncountable.

Show that there exists a co-r.e. set that is not r.e.

We say a partial recursive function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is extendable if there exists a recursive function $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ such that $g(x)=f(x)$ whenever $f(x) \downarrow$. Show that there exists a partial recursive function that is not extendable.

Show that TOT $=\left\{ n \mid W_{n}= \left\{ 0,1\right\}^{*}\right\} =\left\{ n \mid \phi_{n}\text{ is recursive }\right\}$ is not r.e.

Show that there exists a simple set.

Prove that the set of points of the segment $[0, 1]$ is uncountable.

Prove that the set of real-valued functions defined on the segment $[0, 1]$ has cardinality greater than $c$.

Prove that the set $P(A)$ of all subsets of a set $A$ has cardinality greater than $\left|A\right|$.

We say that a sequence of natural numbers $b_{1}, b_{2}, \ldots$ grows faster than a sequence $a_{1}, a_{2}, \ldots$ if $\lim_{n \to \infty } \frac{a_{n}}{b_{n}} = 0$. Prove that:

Prove that there is no primitive recursive function universal for the family of all $n$-ary primitive recursive functions.

Prove that there is no partial recursive function universal for the family of all $n$-ary general recursive functions.

Prove that the following functions are not partial recursive:

Find a partial recursive function $f(x)$ that has no general recursive extension.

Find a partial recursive function $f(x)$ not representable in the form

for any general recursive function $g$.

Prove that if $V(n,x)$ is a partial recursive function universal for the class of all one-place partial recursive functions, then the set

is not recursively enumerable.

Let $\mathcal{B}$ be the set of all infinite sequences over $\left\{ 0,1\right\}$. Show that $\mathcal{B}$ is uncountable using a proof by diagonalization.

Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\left\{ \left\langle M_{1}\right\rangle ,\left\langle M_{2}\right\rangle , \ldots \right\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)

Let $A_{\text{TM }}{ }^{\prime }=\left\{ \langle M, w\rangle \mid M \text{ is an oracle TM and } M^{A T \mathrm{M}} \text{ accepts } w\right\}$. Show that $A_{\text{TM }}{ }^{\prime }$ is undecidable relative to $A_{\text{TM }}$.

Show that for any language $A$, a language $B$ exists, where $A \leq_{\mathrm{T}} B$ and $B \nleq_{\mathrm{T}} A$.

• Prove that there exist two languages $A$ and $B$ that are Turing-incomparable-that is, where $A \nleq_{\mathrm{T}} B$ and $B \nleq_{\mathrm{T}} A$.

• Read the definition of a 2DFA (two-headed finite automaton) given in Problem 5.26. Prove that P contains a language that is not recognizable by a 2DFA.

Problem 5.26: A two-headed finite automaton (2DFA) is a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a 2DFA is finite and is just large enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A 2DFA accepts its input by entering a special accept state.

Prove that an oracle $C$ exists for which $\mathrm{NP}^{C} \neq \operatorname {coNP}^{C}$.