[Solved]: Are all partial functions partial computable?

Problem Detail: 

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.

Asked By : Jed McGowan

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53751

3.2K people like this

 Download Related Notes/Documents