Rice–Shapiro theorem - Misplaced Pages

(Redirected from Rice-Shapiro theorem) Generalization of Rice's theorem

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, named after Henry Gordon Rice and Norman Shapiro. It states that when a semi-decidable property of partial computable functions is true on a certain partial function, one can extract a finite subfunction such that the property is still true.

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 , and by Grigori Tseitin.

Formal statement

Rice-Shapiro theorem. Let P be a set of partial computable functions such that the index set of P (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. Let P be a set of total computable functions such that the index set of P is decidable 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

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

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

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

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.

Proof of the Kreisel-Lacombe-Shoenfield-Tseitin theorem

Preliminaries

A total function $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.

Perspective from effective topology

For any finite unary function $\theta$ on integers, let $C(\theta )$ denote the 'frustum' of all partial-recursive functions that are defined, and agree with $\theta$ , on $\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 $C$ , the index set $Ix(C)$ is recursively enumerable. More generally it holds for every set $A$ of partial-recursive functions:

$Ix(A)$ is recursively enumerable iff $A$ is a recursively enumerable union of frusta.

Applications

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 apply this result to an investigation of the Nakamura numbers for simple games in cooperative game theory and social choice theory.

Notes

^ Kreisel, Georg; Lacombe, Daniel; Shoenfield, Joseph R. (1959). "Partial recursive functionals and effective operations". In Heyting, Arend (ed.). Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 290–297.
^ Tseitin, Grigori (1959). "Algorithmic operators in constructive complete separable metric spaces". Doklady Akademii Nauk. 128: 49-52.
^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1.
Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press.; Theorem 7-2.16.
Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.
Moschovakis, Yiannis N. (June 2010). "Kleene's amazing second recursion theorem" (PDF). The Bulletin of Symbolic Logic. 16 (2).
Royer, James S. (June 1997). "Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals". Journal of Computer and System Sciences. 54 (3): 424–436. doi:10.1006/jcss.1997.1487.
Longley, John; Normann, Dag (2015). Higher-Order Computability. Springer. p. 441. doi:10.1007/978-3-662-47992-6.
Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439. doi:10.1007/s00355-008-0300-5. S2CID 8106333.
Kumabe, M.; Mihara, H. R. (2008). "Computability of simple games: A characterization and application to the core". Journal of Mathematical Economics. 44 (3–4): 348–366. arXiv:0705.3227. doi:10.1016/j.jmateco.2007.05.012. S2CID 8618118.

Categories: