Question on the definition of computable function and non-terminating behaviour

Question

For example on wikipedia a function $f : \mathbb N^k \to \mathbb N$ is defined to be computable, if there exists an algorithm (in form of a Turing machine, as an $\mu$-recursive function or maybe a C++ programm) such that the following holds:

• If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory
• If $f(x)$ is undefined, then the program never terminates on the input x.

My question concerns the second item, the requirement that for elements $x \notin \operatorname{dom}(f)$ we require the program to end up in an endless loop. But more natural to me would be simply to leave the behaviour unspecified in this case (i.e. just require item 1).

Like for example consider the following quite artificial function: $$ f(n) := \left\{ \begin{array}{ll} n^2 & \mbox{ if } n \equiv 0 \pmod{2} \\ \mbox{undefined} & \mbox{ otherwise }. \end{array}\right. $$ Then intuitively I would say some programming squaring its argument would compute $f : \mathbb N \to \mathbb N$, but not to the above definition as this programm would also give a result on all $n \notin \operatorname{dom}(f)$.

From a theoretical point of view this could be fixed if $\mbox{dom}(f)$ is decidable (or semi-decidable, in which case the infinite loop would be given by definition that each query $x \in \operatorname{dom}(f)$ should end up in an infinite loop by the definition of semi-decidable), as we simply query if the argument is in $\operatorname{dom}(f)$, and if yes proceed with our algorithm, and if not just enter some idle endless loop.

From another point of view discarding item two above would be easier in proofs, as the case if $f(x)$ is undefined does not needs to be considered. But I can image that someone wants a relationship that the algorithms terminates exactly if $f$ is defined. But does this makes any difference? What would be lost if we just use item one above as the defintion of computability, i.e. $f : \mathbb N^k \to \mathbb N$ is computable, iff there exists an algorithm that computes the correct result if $f(x)$ is defined.

Answer 1

The short answer is that: this part of Wikipedia's explanation kinda sucks. Hey, it happens. Wikipedia is pretty good, but it's not perfect.

The relevant part of the Wikipedia article says:

Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function $f : \mathbb{N}^k \to \mathbb{N}$ can be calculated if and only if there exists a computer program with the following properties:

1. If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory.
2. If $f(x)$ is undefined, then the program never terminates on the input $x$.

The second sentence is not strictly wrong (that sentence does say that "a partial function can be calculated if...") but it sure seems misleading to include that sentence in an article on computable functions, as computable functions are required to be total functions. Also, the combination of those two sentences leaves the wrong impression as it omits the requirement that $f$ be a total function.

Advice: if you're reading something in Wikipedia that seems confusing or doesn't seem quite right, check another source. Check a good textbook -- they are a more definitive source for the precise definition of mathematical concepts.

Answer 2

A computable function is always a total function. The definition you mention is that of a partial function. A computable function is defined on all inputs, and any algorithm for it has to halt on all inputs.

Partial functions show up in computability theory exactly because Turing machines can never halt. But computable functions are functions which are computed by Turing machines that always halt.