What is the definition of computable partial function?

Question

Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input on which $f$ is defined. But then what should $T$ do on inputs from $\mathbb{N}$ for which $f$ is undefined, and what should it do on inputs that do not represent a natural number? Should it halt or not?

Answer 1

A Turing machine $\Phi$ computes a partial function $f:$ $\subseteq\mathbb{N}\rightarrow\mathbb{N}$ iff:

• For each $n\in dom(f)$, $\Phi(n)$ halts and equals $f(n)$.

• For each $n\not\in dom(f)$, $\Phi(n)$ diverges (that is, never halts).

What about when we feed $\Phi$ a "nonsense" input - that is, some string not corresponding to a natural number? Well, we don't actually place any requirements on how $\Phi$ behaves in such a case, so there isn't anything to say there. (One reason this should feel fine is that it is computable to tell whether a given finite string represents a natural number - so we're not missing anything interesting by ignoring the behavior of $\Phi$ on nonsense inputs.)

---

Note that there is a related, weaker notion:

• One partial function $f$ extends another partial function $g$ if $dom(f)\supseteq dom(g)$ and for all $n\in dom(g)$ we have $f(n)=g(n)$.

• We can say that a partial function $g$ is extendible to a partial computable function if there is some computable partial function $f$ which extends $g$.

It turns out that "extendible to a partial computable function" is a strictly weaker condition than being a partial computable function; this is easy to prove by a simple cardinality argument (exercise).

More interestingly, we can cook up partial computable functions which are not extendible to any total computable function - sort of "fundamentally incomplete" functions which are nonetheless computable. A classic example comes from Godel's incompleteness theorem:

Fixing some appropriately-computable bijection $b$ between sentences in the language of arithmetic and natural numbers, let $h(x)$ be the least $n$ such that there is a proof of $b^{-1}(x)$ of length $n$, and be undefined otherwise. Then $h$ is a partial computable function which cannot be extended to a total computable function.

Here "proof" means "proof from PA" (or your favorite axiom system). The reason that $h$ can't be extended to a total computable function is simple: if $f$ were a total computable function extending $h$, we could tell whether a given sentence $\varphi$ was provable from PA by searching for a proof of $\varphi$ of length at most $f(b(\varphi))$ - if we find one it is, and if we don't find one it isn't. But from this data we could built a complete consistent computable extension of PA (exercise), contradicting Godel's incompleteness theorem.

The (non-)extendibility of partial computable functions to total, or otherwise "frequently-defined," computable functions is an important topic in computability theory.