[Solved]: Is the set of Gödel numbers of computable constant functions recursively enumerable?

Problem Detail: I’ve been working on the following exercise:

$S = { x | f_x text{ is constant} }$. Is $S$ recursively enumerable?

Here, $fx$ is the function computed by the $text{x-th TM}$. So it is a computable function. Intuitively, I think that to check if $S$ is constant, I would have to check if $f_x$ stops for every input. That procedure would run forever. Important: Same thing about $overline{S}$, if some $f_x$ is undefined for every input $y$ (it would not be constant, as far as I understand, it is constant if it has the same image for all input values) then I would not be able to list $f_x$ in an enumeration of $overline{S}$. In fact, suppose $forall x,fx$ is undefined. This $f_x$ is computable – a TM can be constructed that loops forever. How can you determine that $f_x$ is not constant? There will be no input for which $f_x$ halts. Therefore, we cannot check for equality of $x_1$ and $x_2$ to determine that is not constant. Then, we can’t list this $TM_x$ in the enumeration. A solution in which this $f_x$ was put at the beginning of the enumeration was suggested. But there are infinitely many $TMs$ that are undefined for all inputs. Consequently, I can’t put them at the beginning of the enumeration as other $TMs$ won’t be enumerated. I tried to reduce the Halting Problem to this problem without success. I believe that both $S$ and $overline{S}$ are not r.e. (see my intuitive thoughts above). How would you solve this problem?

Asked By : PALEN

Answered By : Raphael

Your intuition is good: checking whether $x in S$ is stronger than checking $x in K$ ($K$ the halting problem, i.e. $K = { x mid f_x(x) text{ halts}}$). In other words, $qquaddisplaystyle langle operatorname{sgn} circ frangle in S implies f in K$. However, the reverse does not hold and no similar implication works for $overline{K}$, the reduction partner we really want (as it’s not semi-decidable). A small interlude: the title you chose does not actually fit the question! The set of all constant functions is in fact recursively enumerable, e.g. by $qquaddisplaystyle varphi_i(x) = i$ which is clearly a computable function. Many sets of functions are enumerable like this, but not all. What you are really asking is: given a Gödel numbering (e.g. an encoding of all Turing machines), what about the set of all indices (read: programs) that compute this here set of functions? That’s another thing entirely because of the properties such a Gödel numbering has. The distinction is important, see e.g. here. The basic idea for a reduction is always this: build a function that depends on $x$ and whose encoding is in $S$ if and only if $x in overline{K}$ — then we got a deal. So, consider $qquaddisplaystyle g_x(n) = begin{cases} n, &f_x(x) text{ halts after at most $n$ steps } 1, &text{else} end{cases} $ which is clearly computable. Note furthermore that given $x$, we can compute $y$ with $f_y = g_x$; such compilation is possible because we have (or can assume) a Gödel numbering. Now, clearly $qquad langle g_x rangle in S iff x in overline{K}$ holds; thus $S$ can’t be semi-decidable since $overline{K}$ would then be semi-decidable, too, contradicting what we know.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19776 Ask a Question Download Related Notes/Documents