A set $S$ (of natural numbers) is (semi)decidable if its (semi)characteristic function is effectively calculable.

From a set theoretic point of view, the semicharacteristic function of a set is just a particular subset of its characteristic function. Consider the subsets of the characteristic function of a given set which are supersets of its semicharacteristic function. All of them are partial functions, but some might be effectively calculable, and some might not. I don't know how to call these functions, but let me use $f_S$ as a variable that ranges over them for a given set $S$.

Is there any S for which the only effectively calculable $f_S$ is its semicharacteristic function?

  • $\begingroup$ I think "indicator function" is a better term for this than "characteristic function", because of the standard usage according to which "characteristic function" means the Fourier transform of a probability distribution. $\endgroup$ – Michael Hardy Dec 28 '10 at 17:57
  • 4
    $\begingroup$ Michael, the term characteristic function is also completely standard for the function having value $1$ on $S$ and value $0$ on the complement of $S$, and this is the sense that is used here. See en.wikipedia.org/wiki/Characteristic_function. $\endgroup$ – Joel David Hamkins Dec 28 '10 at 21:25
  • $\begingroup$ Standard but potentially ambiguous. $\endgroup$ – Michael Hardy Dec 28 '10 at 21:56

Any finite modification of a computable function is computable, so the only instance of your phenomenon is the set $S=\mathbb{N}$, for which the semi-characteristic function is the same as the characteristic function.

Meanwhile, a modified version of your question is answered by the concept of a simple set, a c.e. set whose complement is infinite but contains no infinite c.e. set. Namely,

Theorem. The following are equivalent for $S\subset\mathbb{N}$ having infinite complement:

  • $S$ is simple. That is, $S$ is c.e. and the complement is infinite, but has no infinite c.e. subset.

  • The semi-characteristic function of $S$ is computable, but every computable function $f_S$ between the semi-characteristic function and the characteristic function differs only finitely from the semi-characteristic function of $S$; that is, the domain of $f_S$ is $S$ plus finitely many elements.

Proof. If $S$ is simple, then any such computable $f_S$ can have only finitely many extra values, since the zeros of $f_S$ would be a c.e. set in the complement of $S$. Conversely, if $S$ is c.e. but not simple, then you can build a suitable $f_S$ by extending the semi-characteristic function to include that extra infinite piece, on which $f_S$ has value $0$. QED

Post had hoped to use such sets to solve Post's problem (the question of whether there are c.e. sets of strictly intermediate Turing degree complexity between the computable sets and the halting problem), and their investigation inspired a huge part of computability theory, even though the ultimate resolution of Post's problem didn't involve that concept.


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.