0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Are you sure that you mean "partially computable function", rather than "computable partial function"? $\endgroup$ – Arno Nov 3 '18 at 14:57
  • $\begingroup$ @Arno aren't both the same? $\endgroup$ – Saravanan Nov 3 '18 at 16:42
  • 1
    $\begingroup$ "Computable partial functions" are a standard notion of computability theory. I don't know of a definition of "partially computable functions", but just based on English grammar, the term should refer to some weakening of computability, ie some different notion. $\endgroup$ – Arno Nov 3 '18 at 17:05
  • 1
    $\begingroup$ @Saravanan It's the difference between "a partial function which is computable" and "a function which is partially computable." The former is definitely what you mean, and that's what's captured by "computable partial function" or "partial computable function" (this latter being read as "computable function which is partial," and hence different from "partially computable function"). In practice I think this won't cause confusion, since I don't think "partially computable" has a technical meaning, but it's not the term used and it's still best to avoid it. $\endgroup$ – Noah Schweber Nov 3 '18 at 17:56
  • $\begingroup$ @NoahSchweber Yeah my mistake, I mean a partial function $f$ which is computable, so then should it always halt "on other undefined inputs from $\mathbb{N}$ and other inputs which does not represent an natural number" $\endgroup$ – Saravanan Nov 3 '18 at 19:04
3
$\begingroup$

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.

$\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.