Contents

Rice–Shapiro theorem

The informal idea of the theorem is that the "only general way" to obtain information on the behavior of a program is to run the program, and because a computation is finite, one can only try the program on a finite number of inputs.

A closely related theorem is the Kreisel-Lacombe-Shoenfield-Tseitin theorem, which was obtained independently by Georg Kreisel, Daniel Lacombe and Joseph R. Shoenfield ^[1], and by Grigori Tseitin^[2].

Formal statement[edit]

Rice-Shapiro theorem.^{[3]: 482 [4][5]} Let P be a set of partial computable functions such that the index setofP (i.e., the set of indices e such that φ_e ∈ P, for some fixed admissible numbering φ) is semi-decidable. Then for any partial computable function f, it holds that P contains f if and only if P contains a finite subfunction of f (i.e., a partial function defined in finitely many points, which takes the same values as f on those points).

Kreisel-Lacombe-Shoenfield-Tseitin theorem.^{[3]: 362 [1][2][6][7][8]} Let P be a set of total computable functions such that the index set of Pisdecidable with a promise that the input is the index of a total computable function (i.e., there is a partial computable function D which, given an index e such that φ_e is total, returns 1 if φ_e ∈ P and 0 otherwise; D(e) need not be defined if φ_e is not total). We say that two total functions f, g "agree until n" if for all k ≤ n it holds that f(k) = g(k). Then for any total computable function f, there exists n such that for all total computable function g which agrees with f until n, f ∈ P ⟺ g ∈ P.

Discussion[edit]

The two theorems are closely related, and also relate to Rice's theorem. Specifically:

• Rice's theorem applies to decidable sets of partial computable functions, concluding that they must be trivial.
• The Rice-Shapiro theorem applies to semi-decidable sets of partial computable functions, concluding that they can only recognize elements based on a finite number of values.
• The Kreisel-Lacombe-Shoenfield-Tseitin theorem applies to decidable sets of total computable functions, with a conclusion similar to the Rice-Shapiro theorem.

Examples[edit]

By the Rice-Shapiro theorem, it is neither semi-decidable nor co-semi-decidable whether a given program:

• Terminates on all inputs (universal halting problem);
• Terminates on finitely many inputs;
• Is equivalent to a fixed other program.

By the Kreisel-Lacombe-Shoenfield-Tseitin theorem, it is undecidable whether a given program which is assumed to always terminate:

• Always returns an even number;
• Is equivalent to a fixed other program that always terminates;
• Always returns the same value.

Proof of the Rice-Shapiro theorem[edit]

Let P be a set of partial computable functions with semi-decidable index set.

Upward closedness[edit]

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 graphoff 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 Ponp 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 gonx (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 fonx. 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 φ_pisg. This contradicts the assumption g ∉ P.

Extracting a finite subfunction[edit]

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 finP. 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 fonx, 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[edit]

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.

Proof of the Kreisel-Lacombe-Shoenfield-Tseitin theorem[edit]

Preliminaries[edit]

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[edit]

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:

• Ifx ≤ N then return f(x);
• Otherwise, run x computation steps of the algorithm that decides Ponp, 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 Bonp 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[edit]

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 Ponp.
• 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 (ifP did not return Bonpinx steps), return f(x).

We first prove that P returns Bonp. 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 Bonp. 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 ∈ Ponp.

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

Perspective from effective topology[edit]

For any finite unary function ${\displaystyle \theta }$ on integers, let ${\displaystyle C(\theta )}$ denote the 'frustum' of all partial-recursive functions that are defined, and agree with ${\displaystyle \theta }$, on ${\displaystyle \theta }$'s domain.

Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum ${\displaystyle C}$, the index set ${\displaystyle Ix($C)} is recursively enumerable. More generally it holds for every set ${\displaystyle A}$ of partial-recursive functions:

${\displaystyle Ix($A)} is recursively enumerable iff ${\displaystyle A}$ is a recursively enumerable union of frusta.

Applications[edit]

The Kreisel-Lacombe-Shoenfield-Tseitin theorem has been applied to foundational problems in computational social choice (more broadly, algorithmic game theory). For instance, Kumabe and Mihara^[9][10] apply this result to an investigation of the Nakamura numbers for simple games in cooperative game theory and social choice theory.

Notes[edit]