Is the set of Gödel numbers of computable constant functions recursively enumerable?

Question

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?

Answer 1

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,

$\qquad\displaystyle \langle \operatorname{sgn} \circ f\rangle \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

$\qquad\displaystyle \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

$\qquad\displaystyle 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.