Computable Functions

Let $\texttt{x}$ be a variable of the while language.

We write $[\texttt{x} \mapsto n]$ for the state that maps the variable $\texttt{x}$ to the number $n \in \mathbb{N}$, and every other variable to $0$.

A while program $\texttt{S}$ computes a partial function
$f : \mathbb{N} ⇀ \mathbb{N}$ (with respect to $\texttt{x}$) just if $f(m) \simeq n$ exactly when $\langle S, [\texttt{x} \mapsto m] \rangle \Downarrow [\texttt{x} \mapsto n]$.

The function computed by a while program $\texttt{S}$ must be partial, because $\texttt{S}$ might decide to loop on certain inputs.

A function $f : \mathbb{N} ⇀ \mathbb{N}$ is computable just if there is a program $S$ that computes $f$ with respect to the variable $\texttt{x}$. We often abbreviate the phrase “with respect to” to “wrt.”

Given a while program $S$ we write $⟦ S ⟧_{\texttt{x}} : \mathbb{N} ⇀ \mathbb{N}$ for the function computed by $S$ with respect to variable $\texttt{x}$.

Examples

The function
\[\begin{aligned} & f : \mathbb{N} \to \mathbb{N} \\ & f(x) = x+1 \end{aligned}\]
is computable. We have that $f = ⟦ S ⟧_{\texttt{x}}$, where $S$ is the program
```
1
  x <- x + 1
```

The factorial function $(\cdot)! : \mathbb{N} \to \mathbb{N}$ is computable. We have that $(\cdot)! = ⟦ Q ⟧_{\texttt{n}}$, where $Q$ is the program

r <- 1;
while (n >= 1) {
  r <- r * n;
  n <- n - 1
}
// Put the desired result in n.
n <- r
// Zero out the auxiliary variable.
r <- 0;

The integer-division-by-2 function $\textbf{div2} : \mathbb{N} ⇀ \mathbb{N}$, which performs Euclidean division by 2 and returns the quotient, is computable. It is computed wrt n by the program

q <- 0; r <- n;
while (r >= 2) {
  q <- q + 1; r <- r - 2    // Loop invariant: n = q * 2 + r & r >= 0
}
// Put the result in n.
n <- q
// Zero out all auxiliary variables.
q <- 0; r <- 0;

The partial function
\[\begin{aligned} & g : \mathbb{N} ⇀ \mathbb{N} \\ & g(x) \begin{cases} \simeq x + 1 & \text{ if $x < 2$} \\ \uparrow & \text{ otherwise} \end{cases} \end{aligned}\]
is computable. It is computed wrt x by the following program.
```
1
2
3
4
if (x <= 1) then
  x <- x + 1
else
  while (true) do { skip }
```

Characteristic Functions

Let $U \subseteq \mathbb{N}$ be a predicate on the natural numbers.

The characteristic function of $U$ is the function

\[\begin{aligned} &\chi_U : \mathbb{N} \to \mathbb{N} \\ &\chi_U(n) = \begin{cases} 1 & \text{ if $n \in U$} \\ 0 & \text{ if $n \not\in U$} \end{cases} \end{aligned}\]

A number either is or isn’t a member of the predicate. Thus, its characteristic function is always total: it is defined for all natural numbers.

Decidable predicates

A predicate $U \subseteq \mathbb{N}$ is decidable just if its characteristic function $\chi_U : \mathbb{N} \to \mathbb{N}$ is computable.

The while program that computes the characteristic function $\chi_U$ of a predicate $U \subseteq \mathbb{N}$ is called a decision procedure.

Any predicate for which there is no decision procedure is called undecidable.

Examples

The predicate $E = \{ n \in \mathbb{N} \mid n \text{ is even} \}$ is decidable. It is decided with respect to the variable $\texttt{x}$ by the program
```
1
2
3
4
 while (x >= 2) do {
   x <- x - 2
 }
 x <- 1 - x
```
The invariant maintained by this loop is that the parity of $x$ (i.e. whether it is even or odd) is the same as it was before the loop started. At the end of the loop the variable $\texttt{x}$ is $< 2$, which is to say either $0$ or $1$. If it is $0$, the initial value had an even parity, and if it is $1$, the initial value had an odd parity. We have to remember to flip this value in order to return the correct result (i.e. $1$ if it is even, and $0$ if it is odd).

Semi-decidable predicates

Let $U \subseteq \mathbb{N}$ be a predicate on the natural numbers.

The semi-characteristic function of $U$ is the partial function

\[\begin{aligned} &\xi_U : \mathbb{N} ⇀ \mathbb{N} \\ &\xi_U(n) \begin{cases} \simeq 1 & \text{ if $n \in U$} \\ \uparrow & \text{ otherwise} \end{cases} \end{aligned}\]

The characteristic function $\chi_U$ of $U$ is always total: it always returns either $0$ or $1$.

In contrast, the semi-characteristic function $\xi_U$ is partial. If $n \in U$ the semi-characteristic function returns $1$. Otherwise, it is undefined.

The idea is that semi-characteritic functions are somewhat easier to compute than characteristic functions. A program that computes a characteristic function must halt with a specific answer (yes or no) on all valid inputs. However, a program that computes the semi-characteristic function must only halt for ‘yes’ inputs. Otherwise, it is allowed to continue computing forever.

A predicate $U \subseteq \mathbb{N}$ is semi-decidable just if its semi-characteristic function $\xi_U$ is computable.

Examples

The predicate $U = \{ k \in \mathbb{N}^+ \mid \text{ the Collatz sequence starting at $k$ eventually reaches 1 } \}$ is semi-decidable.

The Collatz sequence starting at $k \in \mathbb{N}^+$ is the sequence of numbers $(a_n)_{n \in \mathbb{N}}$ defined by

\[\begin{aligned} a_0 &= k \\ a_{n+1} &= \begin{cases} a_n/2 & \text{ if $a_n$ is even} \\ (3a_n+1)/2 & \text{ if $a_n$ is odd} \end{cases} \end{aligned}\]

The Collatz conjecture is a famously unsolved problem of mathematics. It states that the Collatz sequence $a_0, a_1, \dots$ starting at any $a_0 \in \mathbb{N}^+$ will eventually reach the number $1$.

If the Collatz conjecture is true, then every number is in the predicate $U$, i.e. $U = \mathbb{N}$. Thus, if $U$ were proven to be decidable, then that would reveal a lot of interesting things for this unresolved conjecture!

However, we can show that $U$ is semi-decidable. Its semi-characteristic function $\xi_U$ is computed by the following program (wrt n), which calculates every number in the sequence until it reaches $1$.

while (! (n = 1)) {

  // Divide n by 2, putting the quotient in q and the remainder in r.
  q <- 0; r <- n;
  while (r >= 2) {
    q <- q + 1; r <- r - 2      // Loop invariant: n = q * 2 + r & r > 0
  }

  // Depending on the parity compute the next element in the sequence.
  if (r = 0) then {
    // The next element is a_n / 2.
    n <- q
  }
  else {
    // The next element is (3 * a_n + 1) / 2.
    // Compute 3 * a_n + 1, and then divide it by 2.
    q <- 0; r <- 3 * n + 1;
    while (r >= 2) do {
      q <- q + 1; r <- r - 2
    }
    n <- q
  }
}
// If we get here it must be that n = 1. Zero out all other variables.
q <- 0; r <- 0

Suppose we run this program starting with $n > 0$. If the Collatz sequence eventually reaches $1$, the while loop will terminate (with the value $1$ in n). Otherwise, the loop will run forever.

What will happen if we start with $n = 0$?