Is the set of numbers of computable functions f(x) = c recursively enumerable?

68 Views Asked by At

Consider the set of numbers of computable functions such that is $f(x)$ defined, $f(x) = c$ for any $x$. Is this set enumerable or co-enumerable? (Or neither).

A bit of my thoughts on it. We can take every function and begin the computing. If $f(x) \ne c$ for some $x$, the computing will stop and we will go to the next one. So the function seems to be co-enumerable. But what to do if $f(x) = c$ for any $x$? It takes infinite time to know it!

By the way, the function is non-recursive (Rice theorem).

1

There are 1 best solutions below

0
On BEST ANSWER

It's not even co-enumerable - what if $f(x)$ doesn't halt?

In fact, the set of indices of partial computable functions which are defined and equal to $c$ on all inputs (for $c$ some fixed constant) is $\Pi^0_2$ complete - in particular, strictly more complex than any c.e. or co-c.e. set! (In fact it has Turing degree $0''$, the "Halting Problem's Halting Problem".)