Is this modified characteristic function computable

computabilitycomputer sciencedecidabilitylogic

Let $P(n,k)$ be decidable and define

$$f(n)=\begin{cases}1&\text{if there are exactly two }k\text{ with }P(n,k),\\
\text{undefined}&\text{otherwise}.\end{cases}$$

I wonder if this function is computable, not matter what the defining $P$ is. It does not really make sense conceptually for me if it would be as no program could ever decide when to stop searching after having found two solutions to verify that there is no third.

I tried to reduce this to the existence of a decidable $P(n,k)$ such that $\exists k P(n,k)$ is undecidable. It is easy to construct a decidable $P'(n,k)$ such that $P'(n,k)$ has exactly two solutions $k$ if and only if $P(n,k)$ has at least one solution $k$ but computability of $f$ does not immediately yield decidability of $P'$ and hence a contradiction as we have this undefined clause.

Best Answer

In general no. For example, consider the relation $P(n,k)$ defined by "$k=0$ or $k=1$ or $n$ has entered the halting problem by stage $k$." Then $f^{-1}(1)$ defines the complement of the halting problem; since that isn't computably enumerable, $f$ can't be (partial) computable as the partial computable preimage of a c.e. set is always c.e.

Related Question