Let $g _c (x)$ be the output of a program that is encoded by $c \in \mathbb{N}$ for the given input $x$. $g_c$ can obviously be undefined, in case the program encoded by $c$ doesn't halt. If we define the sets $T_1=\left\{ c | g_c (c) \mbox{ is defined}\right\} \subseteq \mathbb{N}$, $T_2=\left\{ c | 0 \in\mbox{dom} (g_c)\right\} \subseteq \mathbb{N}$, $T_3= \left\{ (c,x) | x \in \mbox{dom} (g_c) \right\} \subseteq \mathbb{N}^2$ (where "$\mbox{dom} (g_c)$" is the domain of $g_c$) how could I then prove, that the sets $T_1, T_3$ are recursively enumerable and $T_2$ is not recursive?


The details of the answer depend very much on what I can assume that you know.

Presumably by now you have seen a proof of the following fact. Let $H$ consist of all ordered pairs $(c,n)$ such that $c$ is the number of a prorgam $g_c$ such that $g_c$ (ultimately) halts if given input $n$. Then $H$ is not recursive (undecidability of the Halting Problem).

Let $T_{(c,n)}$ be the program which, given any input (in particular, given input $0$), first erases the input, and replaces it by $n$, and then runs the program encoded by $c$ on the result.

This program $T_{(c,n)}$, in the encoding, has code number $f(c,n)$ where $f$ can be chosen to be a pretty simple function.

Note that $(c,n) \in H$ if and only if the program with code number $f(c,n)$ halts when given input $0$, that is,if and only if $f(c,n) \in T_2$. Thus if $T_2$ were recursive, then the set $H$ would be recursive. But $H$ is not recursive (this is the result about the undecidability of the Halting Problem, with which you are undoubtedly more familiar).

About the fact that $T_1$ and $T_3$ are r.e., let's look at $T_3$.

You will need to know a few facts about Turing machines. The state/tape contents that a Turing machine is in at this instant can be encoded in a number. A sequence of such numbers which form a computation can also be encoded by a number. With some work, one can prove the following.

Theorem Let $T(c,n,z)$ be the set of all ordered triples such that $c$ is the number of a program, and $z$ is the encoding of a complete computation when $n$ is fed to program $c$. Then $T$ is a recursive set (predicate).

Very informally, we can in a computable way recognize when the step by step record of a computation is valid.

Now $T_3$ is just the set of all $(c,n)$ for which there exists a $z$ such that $(c,n,z)$ is in $T$. So $T_3$ is the result of projecting a certain recursive set of triples, or alternately it is the result of applying an existential quantifier to a recursive predicate. But that is the definition of r.e.

There will inevitably be differences of details between the notation of your book/notes and what I have used, but I hope that you can translate what I have written into the terminology that is officially used in your course. (There is very wide variation!)

As for $T_1$, the argument is basically the same as the one for $T_3$.

| cite | improve this answer | |

There has been a string of questions lately about this sort of thing. The questions here are all covered in any textbook on computability. Without having any idea what background is assumed, it's hard to know how to phrase the answer.

For proving that a set is recursively enumerable, there is a standard method to follow, using these two facts along with some more basic facts about computable functions:

  • A subset $A$ of $\mathbb{N}^k$, where $k \geq 1$, is recursively enumerable if and only if there is a decidable (by a Turing machine) relation $R(x_1, \ldots, x_k, t)$ such that a tuple $(n_1, \ldots, n_k) \in A$ if and only if there is some $m \in \mathbb{N}$ such that $R(n_1, \ldots, n_k, m)$ holds.

  • The relation $R(c,n,t)$ defined as "the computable function with index $c$ halts on input $n$ after exactly $t$ steps" is decidable.

For proving undecidability, the first thing to note is that the undecidability of $T_3$ is generally called the "undecidability of the halting problem". There are proofs in many textbooks and there is a proof on Wikipedia under "Halting problem". The undecidability of the other two sets can be proved directly in a similar way, or can be proved by showing that if they were decidable then $T_3$ would also be decidable. In fact, all three of the sets are many-one equivalent. The proof of this last fact is not too hard using the $s^m_n$ theorem.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy