Upward closedness

We first prove that P is an upward closed set, i.e., if f ⊆ g and f ∈ P, then g ∈ P (here, f ⊆ g means that f is a subfunction of g, i.e., the graph of f is contained in the graph of g). The proof uses a diagonal argument typical of theorems in computability.

Assume for contradiction that there are two functions f and g such that f ∈ P, g ∉ P and f ⊆ g. We build a program p as follows. This program takes an input x. Using a standard dovetailing technique, p runs two tasks in parallel.

• The first task executes a semi-algorithm that semi-decides P on p itself (p can get access to its own source code by Kleene's recursion theorem). If this eventually returns true, then this first task continues by executing a semi-algorithm that semi-computes g on x (the input to p), and if that terminates, then the task makes p as a whole return g(x).
• The second task runs a semi-algorithm that semi-computes f on x. If this returns true, then the task makes p as a whole return f(x).

We distinguish two cases.

• First case: φ_p ∉ P. The first task can never finish, therefore the result of p is entirely determined by the second task, thus φ_p is simply f, contradicting the assumption f ∈ P.
• Second case: φ_p ∈ P. If f is not defined on x, then the second task can never finish, therefore p returns g(x), or loops if this is undefined. On the other hand, if f is defined on x, it is possible that the second task finishes and is the first to return. In that case, p returns f(x). However, since f ⊆ g, we actually have f(x) = g(x). Thus, we see that φ_p is g. This contradicts the assumption g ∉ P.

Extracting a finite subfunction

Next, we prove that if P contains a partial computable function f, then it contains a finite subfunction of f. Let us fix a partial computable function f in P. We build a program p which takes input x and runs the following steps:

• Run x computation steps of a semi-algorithm that semi-decides P, with p itself as input. If this returns true, then loop indefinitely.
• Otherwise, semi-compute f on x, and if this terminates, return the result f(x).

Suppose that φ_p ∉ P. This implies that the semi-algorithm for semi-deciding P used in the first step never returns true. Then, p computes f, and this contradicts the assumption f ∈ P. Thus, we must have φ_p ∈ P, and the algorithm for semi-deciding P returns true on p after a certain number of steps n. The partial function φ_p can only be defined on inputs x such that x ≤ n, and it returns f(x) on such inputs, thus it is a finite subfunction of f that belongs to P.

Conclusion

It only remains to assemble the two parts of the proof. If P contains a partial computable function f, then it contains a finite subfunction of f by the second part, and conversely, if it contains a finite subfunction of f, then it contains f, because it is upward closed by the first part. Thus, the theorem is proved.

Preliminaries

A total function ${\displaystyle h:\mathbb {N} \rightarrow \mathbb {N} }$ is said to be ultimately zero if it always takes the value zero except for a finite number of points, i.e., there exists N such that for all n ≥ N, h(n) = 0. Note that such a function is always computable (it can be computed by simply checking if the input is in a certain predefined list, and otherwise returning zero).

We fix U a computable enumeration of all total functions which are ultimately zero, that is, U is such that:

• For all k, φ_U(k) is ultimately zero;
• For all total function h which is ultimately zero, there exists k such that φ_U(k) = h;
• The function U is itself total computable.

We can build U by standard techniques (e.g., for increasing N, enumerate ultimately zero functions which are bounded by N and zero on inputs larger than N).

Approximating by ultimately zero functions

Let P be as in the statement of the theorem: a set of total computable functions such that there is an algorithm which, given an index e and a promise that φ_e is computable, decides whether φ_e ∈ P.

We first prove a lemma: For all total computable function f, and for all integer N, there exists an ultimately zero function h such that h agrees with f until N, and f ∈ P ⟺ h ∈ P.

To prove this lemma, fix a total computable function f and an integer N, and let B be the boolean f ∈ P. Build a program p which takes input x and takes these steps:

• If x ≤ N then return f(x);
• Otherwise, run x computation steps of the algorithm that decides P on p, and if this returns B, then return zero;
• Otherwise, return f(x).

Clearly, p always terminates, i.e., φ_p is total. Therefore, the promise to P run on p is fulfilled.

Suppose for contradiction that one of f and φ_p belongs to P and the other does not, i.e., (φ_p ∈ P) ≠ B. Then we see that p computes f, since P does not return B on p no matter the amount of steps. Thus, we have f = φ_p, contradicting the fact that one of f and φ_p belongs to P and the other does not. This argument proves that f ∈ P ⟺ φ_p ∈ P. Then, the second step makes p return zero for sufficiently large x, thus φ_p is ultimately zero; and by construction (due to the first step), φ_p agrees with f until N. Therefore, we can take h = φ_p and the lemma is proved.

Main proof

With the previous lemma, we can now prove the Kreisel-Lacombe-Shoenfield-Tseitin theorem. Again, fix P as in the theorem statement, let f a total computable function and let B be the boolean "f ∈ P". Build the program p which takes input x and runs these steps:

• Run x computation steps of the algorithm that decides P on p.
• If this returns B in a certain number of steps n (which is at most x), then search in parallel for k such that U(k) agrees with f until n and (U(k) ∈ P) ≠ B. As soon as such a k is found, return U(k)(x).
• Otherwise (if P did not return B on p in x steps), return f(x).

We first prove that P returns B on p. Suppose by contradiction that this is not the case (P returns ¬B, or P does not terminate). Then p actually computes f. In particular, φ_p is total, so the promise to P when run on p is fulfilled, and P returns the boolean φ_p ∈ P, which is f ∈ P, i.e., B, contradicting the assumption.

Let n be the number of steps that P takes to return B on p. We claim that n satisfies the conclusion of the theorem: for all total computable function g which agrees with f until n, it holds that f ∈ P ⟺ g ∈ P. Assume by contradiction that there exists g total computable which agrees with f until n and such that (g ∈ P) ≠ B.

Applying the lemma again, there exists k such that U(k) agrees with g until n and g ∈ P ⟺ U(k) ∈ P. For such k, U(k) agrees with g until n and g agrees with f until n, thus U(k) also agrees with f until n, and since (g ∈ P) ≠ B and g ∈ P ⟺ U(k) ∈ P, we have (U(k) ∈ P) ≠ B. Therefore, U(k) satisfies the conditions of the parallel search step in the program p, namely: U(k) agrees with f until n and (U(k) ∈ P) ≠ B. This proves that the search in the second step always terminates. We fix k to be the value that it finds.

We observe that φ_p = U(k). Indeed, either the second step of p returns U(k)(x), or the third step returns f(x), but the latter case only happens for x ≤ n, and we know that U(k) agrees with f until n.

In particular, φ_p = U(k) is total. This makes the promise to P run on p fulfilled, therefore P returns φ_p ∈ P on p.

We have found a contradiction: one the one hand, the boolean φ_p ∈ P is the return value of P on p, which is B, and on the other hand, we have φ_p = U(k), and we know that (U(k) ∈ P) ≠ B.