# Are all partial functions partial computable?

If we have some function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ that is not total, i.e. for some values $x \in \mathbb{N}$, $f(x) = {\perp}$, is $f$ always partial computable? By partial computable I mean there exists a program that $f(a)$ is defined for $a \in \mathrm{dom}(f)$ and $f(a)$ is not defined for $a \notin \mathrm{dom}(f)$.

I expect that this isn't the case but cannot come up with a counter example.

• How many such functions are there? How many Turing machines are there? – Pål GD Feb 28 '16 at 23:03
• Let me answer my latter question. There are countably many Turing machines. – Pål GD Feb 28 '16 at 23:04
• There are an uncountable number of partial functions meaning there must exist such a function that cannot be computed as, like you said, there are countably many Turing machines. – Jed McGowan Feb 28 '16 at 23:13
• I don't know the answer but it would be linguistically elegant if this was prtially true... – keshlam Feb 29 '16 at 2:31

The fact that we can encode Turing machines as strings means that there are only countably many Turing machines, so only countably many computable or partial-computable anythings. Since there are uncountably many partial functions $\mathbb{N}\to\mathbb{N}$ (or even partial functions $\mathbb{N}\to\{0\})$, it follows that, in a very strong sense, "most" partial functions are not partial computable.
For a concrete example, use the fact that, if a set and its complement are both semi-decidable, they are both decidable (exercise: prove this), and the analogous result for partial functions. This means that, if you take any set $S$ that is semi-decidable but not decidable, then $\overline{S}$ is not semi-decidable. So, for example, the function $$f(x) = \begin{cases} 0 &\text{ if }x=\langle M\rangle \text{ for some TM M that loops on every input}\\ {\perp} &\text{ otherwise} \end{cases}$$ is not partial computable.