MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

is there any example of function which is computable on some set and uncomputable on other set? That is for example function f(n) which is computable on some (finite, or for example for even numbers) set A of N and, uncomputable on N\A ?

By nontrivial example I mean function which is not defined as computable function for set A and uncomputable for set N\A that is by use of the "if $x \in A$ then ..." statement, but by one, given procedure or definition. If You have a problem what is mean "one procedure or definition" take an assumption that in definition of such function do not appear sentence "if $x \in A$ then ..."

share|cite|improve this question
Presumably you want to demand that your set $A$ is infinite, rather than finite; since otherwise every function has this property? – Noah Schweber Jun 22 '13 at 17:31
Yes, that is a valid point – kakaz Jun 22 '13 at 17:46
For that matter, you should probably require that $A$ be computable as well. Otherwise, for example, every function $f: \omega\rightarrow F$ has this property whenever $F$ is finite. – Noah Schweber Jun 22 '13 at 17:59
up vote 4 down vote accepted

How about the characteristic function of the Halting Problem? That is, $f(x)=1$ iff $\Phi_x(x)\downarrow$ and $f(x)=0$ otherwise.

This function is clearly incomputable, but is computable on large infinite sets since by the padding lemma we can produce large (computable) sets $X$ of indices for equivalent programs which we already know halt or diverge.

share|cite|improve this answer
it is answer which is clearly correct, but let me wait till someone give at least one additional example... – kakaz Jun 22 '13 at 17:47
Perhaps not what you intended, but: there are plenty of forcing notions which add a function $f: \omega\rightarrow 2$ which is constant on an infinite computable set. One example of this is Mathias forcing: conditions are pairs $(D, E)$ with $D$ finite, $E$ computable and infinite, and $min(E)>max(D)$. They are ordered by setting $(D', E')\le (D, E)$ iff $D\subseteq D'$, $E'\subseteq E$, and $D'-D\subset E$; the function added by this forcing is then just (the characteristic function of) the union of the left components of the conditions in the generic filter. – Noah Schweber Jun 22 '13 at 17:50
The idea is that a condition $(D, E)$ represents a "stage" in the construction in building a set $S$: we've determined that $D\subseteq S$ and that $S\subseteq D\cup E$. Now, we can "thin out" the set $E$ by deleting a computable infinite, coinfinite subset $F$ of $E$ (say, $F$=\lbrace $every other element of E\rbrace$); then the characteristic function of $S$, the set we're building, will be identically zero on $F$. – Noah Schweber Jun 22 '13 at 17:52
What's neat about that example is that there is no infinite computable set on which $\chi_S$ is identically 1. The characteristic function of the halting problem, on the other hand, is identically 1 on infinitely many infinite computable sets, identically 0 on infinitely many computable sets, and these infinite computable sets cover all of $\omega$! Which is pretty cool. – Noah Schweber Jun 22 '13 at 17:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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