Rice–Shapiro 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 [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 set of P (i.e., the set of indices e such that
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 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
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 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[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 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
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 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
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.,
Suppose for contradiction that one of f and
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 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,
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
In particular,
We have found a contradiction: one the one hand, the boolean
Perspective from effective topology[edit]
For any finite unary function on integers, let denote the 'frustum' of all partial-recursive functions that are defined, and agree with , on 's domain.
Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum , the index set is recursively enumerable. More generally it holds for every set of partial-recursive functions:
is recursively enumerable iff 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]
- ^ a b 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.
- ^ a b Tseitin, Grigori (1959). "Algorithmic operators in constructive complete separable metric spaces". Doklady Akademii Nauk. 128: 49-52.
- ^ a b 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.