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 φeP, 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 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 φeP 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 kn 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, fPgP.

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 fg and fP, then gP (here, fg 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 fP, gP and fg. 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: φpP. 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 fP.
  • Second case: φpP. 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 fg, we actually have f(x) = g(x). Thus, we see that φp is g. This contradicts the assumption gP.

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 φpP. 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 fP. Thus, we must have φpP, 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 xn, 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   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 nN, 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 φeP.

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 fPhP.

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

  • If xN 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., (φpP) ≠ 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 fPφpP. 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 "fP". 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 φpP, which is fP, 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 fPgP. Assume by contradiction that there exists g total computable which agrees with f until n and such that (gP) ≠ B.

Applying the lemma again, there exists k such that U(k) agrees with g until n and gPU(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 (gP) ≠ B and gPU(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 xn, 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 φpP on p.

We have found a contradiction: one the one hand, the boolean φpP 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

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
  1. ^ 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.
  2. ^ a b Tseitin, Grigori (1959). "Algorithmic operators in constructive complete separable metric spaces". Doklady Akademii Nauk. 128: 49-52.
  3. ^ a b Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1.
  4. ^ Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press.; Theorem 7-2.16.
  5. ^ Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.
  6. ^ Moschovakis, Yiannis N. (June 2010). "Kleene's amazing second recursion theorem" (PDF). The Bulletin of Symbolic Logic. 16 (2).
  7. ^ 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.
  8. ^ Longley, John; Normann, Dag (2015). Higher-Order Computability. Springer. p. 441. doi:10.1007/978-3-662-47992-6.
  9. ^ 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.
  10. ^ 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.