1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ At which points specifically are you not 100% certain about your attempt? It's mathematics; you can check every step yourself until you hit a problem. Also, you seem to missing one step: in order to contradict undecidability of the halting problem, you need to construct a test for whether $f_x(x)$ holds for input $x$, not a fixed one. $\endgroup$ – Raphael Jan 17 '14 at 8:53
  • $\begingroup$ @Vor Please see my question edited above. I described why your proposed solution in a comment may not work. $\endgroup$ – PALEN Jan 17 '14 at 16:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've seen that construction of 'if it halts after at most steps then something else something' many times now. Is it usually useful? Is it a common method? I mean, it may have a proper name. If it does, could you point me to a reading? $\endgroup$ – PALEN Jan 17 '14 at 23:54
  • $\begingroup$ It comes up in different places in theory (also complexity theory) but I don't know of a name. There may be one, though; maybe ask a terminology question? $\endgroup$ – Raphael Jan 18 '14 at 18:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.