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 (or KLST 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 be a set of partial computable functions such that the index set of (i.e., the set of indices such that , for some fixed admissible numbering ) is semi-decidable. Then for any partial computable function , it holds that contains if and only if contains a finite subfunction of (i.e., a partial function defined in finitely many points, which takes the same values as on those points).
Kreisel-Lacombe-Shoenfield-Tseitin theorem.[3]: 362 [1][2][6][7][8]: 440 Let be a set of total computable functions such that the index set of is decidable with a promise that the input is the index of a total computable function (i.e., there is a partial computable function which, given an index such that is total, returns 1 if and 0 otherwise; need not be defined if is not total). We say that two total functions , "agree until " if holds for all . Then for any total computable function , there exists such that for all total computable function which agrees with until , we have .
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.
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.
It is natural to wonder what can be said about semi-decidable sets of total computable functions. Perhaps surprisingly, these need not verify the conclusion of the Rice-Shapiro and Kreisel-Lacombe-Shoenfield-Tseitin theorems. The following counterexample is due to Richard M. Friedberg.[9][8]: 444
Let be the set of total computable functions such that is not the constant zero function and, defining to be the maximum index such that is zero, there exists a program of code such that is defined and equal to for each . Let be the set with the constant zero function added.
On the one hand, contains the constant zero function by definition, yet there is no such that if a total computable agrees with the constant zero function until then . Indeed, given , we can define a total function by setting to some value larger than every for such that is defined, and for . The function is zero except on the value , thus computable, it agrees with the zero function up to , but it does not belong to by construction.
On the other hand, given a program and a promise that is total, it is possible to semi-decide whether by dovetailing, running one task to semi-decide , which can clearly be done, and another task to semi-decide whether for all . This is correct because the zero function is detected by the second task, and conversely, if the second task returns true, then either is zero, or is only zero up to an index , which must satisfy , which by definition of implies that .
Proof of the Rice-Shapiro theorem
[edit]Let be a set of partial computable functions with semi-decidable index set. We prove the two implications separately.
Upward closedness
[edit]We first prove that if is a finite subfunction of and then . The hypothesis that is finite is in fact of no use.
The proof uses a diagonal argument typical of theorems in computability. We build a program as follows. This program takes an input . Using a standard dovetailing technique, runs two tasks in parallel.
- The first task executes a semi-algorithm that semi-decides on itself ( 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 on (the input to ), and if that terminates, then the task makes as a whole return .
- The second task runs a semi-algorithm that semi-computes on . If this returns true, then the task makes as a whole return .
If , the first task can never finish, therefore the result of is entirely determined by the second task, thus is simply , a contradiction. This shows that .
Thus, both tasks are relevant; however, because is a subfunction of and the second task returns when is defined, while the first task returns when defined, the program in fact computes , i.e., , and therefore .
Extracting a finite subfunction
[edit]Conversely, we prove that if contains a partial computable function , then it contains a finite subfunction of . Let us fix . We build a program which takes input and runs the following steps:
- Run computation steps of a semi-algorithm that semi-decides , with itself as input. If this semi-algorithm terminates and returns true, then loop indefinitely.
- Otherwise, semi-compute on , and if this terminates, return the result .
Suppose that . This implies that the semi-algorithm for semi-deciding used in the first step never returns true. Then, computes , and this contradicts the assumption . Thus, we must have , and the algorithm for semi-deciding returns true on after a certain number of steps . The partial function can only be defined on inputs such that , and it returns on such inputs, so it is a finite subfunction of that belongs to .
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 such that for all . 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 a computable enumeration of all total functions which are ultimately zero, that is, is such that:
- For all , the function is ultimately zero;
- For all total function which is ultimately zero, there exists such that ;
- The function is itself total computable.
We can build by standard techniques (e.g., for increasing , enumerate ultimately zero functions which are bounded by and zero on inputs larger than ).
Approximating by ultimately zero functions
[edit]Let be as in the statement of the theorem: a set of total computable functions such that there is an algorithm which, given an index and a promise that is total, decides whether .
We first prove a lemma: For all total computable function , and for all integer , there exists an ultimately zero function such that agrees with until , and .
To prove this lemma, fix a total computable function and an integer , and let be the boolean . Build a program which takes input and takes these steps:
- If then return ;
- Otherwise, run computation steps of the algorithm that decides on , and if this returns , then return zero;
- Otherwise, return .
Clearly, always terminates, i.e., is total. Therefore, the promise to run on is fulfilled.
Suppose for contradiction that one of and belongs to and the other does not, i.e., . Then we see that computes , since does not return on no matter the amount of steps. Thus, we have , contradicting the fact that one of and belongs to and the other does not. This argument proves that . Then, the second step makes return zero for sufficiently large , thus is ultimately zero; and by construction (due to the first step), agrees with until . Therefore, we can take and the lemma is proved.
Main proof
[edit]With the previous lemma, we can now prove the Kreisel-Lacombe-Shoenfield-Tseitin theorem. Again, fix as in the theorem statement, let be a total computable function and let be the boolean "". Build the program which takes input and runs these steps:
- Run computation steps of the algorithm that decides on .
- If this returns in a certain number of steps (which is at most ), then search in parallel for such that agrees with until and . As soon as such a is found, return .
- Otherwise (if did not return on in steps), return .
We first prove that returns on . Suppose by contradiction that this is not the case ( returns , or does not terminate). Then actually computes . In particular, is total, so the promise to when run on is fulfilled, and returns the boolean , which is , i.e., , contradicting the assumption.
Let be the number of steps that takes to return on . We claim that satisfies the conclusion of the theorem: for all total computable function which agrees with until , it holds that . Assume for contradiction that there exists total computable which agrees with until and such that .
Applying the lemma again, there exists such that agrees with until and . Since both and agree with until , also agrees with until , and since and , we have . Therefore, satisfies the conditions of the parallel search step in the program , namely: agrees with until and . This proves that the search in the second step always terminates. We fix to be the value that it finds.
We observe that . Indeed, either the second step of returns , or the third step returns , but the latter case only happens for , and we know that agrees with until .
In particular, is total. This makes the promise to run on fulfilled, therefore returns on .
We have found a contradiction: one the one hand, the boolean is the return value of on , which is , and on the other hand, we have , and we know that .
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[10][11] 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): 189–239. doi:10.2178/bsl/1286889124.
- ^ 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.
- ^ a b Longley, John; Normann, Dag (2015). Higher-Order Computability. Theory and Applications of Computability. Springer. doi:10.1007/978-3-662-47992-6. ISBN 978-3-662-47991-9.
- ^ Friedberg, Richard M. (1958). "Un contre-exemple relatif aux fonctionnelles récursives". Comptes rendus de l'Académie des Sciences. 247: 852–854.
- ^ 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.