2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How many such functions are there? How many Turing machines are there? $\endgroup$ – Pål GD Feb 28 '16 at 23:03
  • $\begingroup$ Let me answer my latter question. There are countably many Turing machines. $\endgroup$ – Pål GD Feb 28 '16 at 23:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Jed McGowan Feb 28 '16 at 23:13
  • $\begingroup$ I don't know the answer but it would be linguistically elegant if this was prtially true... $\endgroup$ – keshlam Feb 29 '16 at 2:31
3
$\begingroup$

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.

$\endgroup$

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.