Rice–Shapiro theorem

Template:Short description 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 Template:R, and by Grigori TseitinTemplate:R.

Formal statement

Rice-Shapiro theorem.Template:RTemplate:RTemplate:R 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 ${\varphi }_e\in P$, for some fixed admissible numbering $\varphi$) 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.Template:RTemplate:RTemplate:RTemplate:RTemplate:RTemplate:R 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 ${\varphi }_e$ is total, returns 1 if ${\varphi }_e\in P$ and 0 otherwise; $D(e)$ need not be defined if ${\varphi }_e$ is not total). We say that two total functions $f$, $g$ "agree until $n$" if $f(k)=g(k)$ holds for all $k\le n$. Then for any total computable function $f$, there exists $n$ such that for all total computable function $g$ which agrees with $f$ until $n$, we have $f\in P⟺g\in P$.

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.

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.

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.Template:RTemplate:R

Let $Q$ be the set of total computable functions $f:\mathbb{N}\to \mathbb{N}$ such that $f$ is not the constant zero function and, defining $n$ to be the maximum index such that $f(n)$ is zero, there exists a program of code $e\le n$ such that ${\varphi }_e(i)$ is defined and equal to $f(i)$ for each $i\le n+1$. Let $P$ be the set $Q$ with the constant zero function added.

On the one hand, $P$ contains the constant zero function by definition, yet there is no $n$ such that if a total computable $g$ agrees with the constant zero function until $n$ then $g\in P$. Indeed, given $n$, we can define a total function $g$ by setting $g(n+1)$ to some value larger than every ${\varphi }_e(n+1)$ for $e\le n+1$ such that ${\varphi }_e(n+1)$ is defined, and $g(n^{\prime })=0$ for $n^{\prime }\ne n+1$. The function $g$ is zero except on the value $n+1$, thus computable, it agrees with the zero function up to $n$, but it does not belong to $P$ by construction.

On the other hand, given a program $e$ and a promise that ${\varphi }_e$ is total, it is possible to semi-decide whether ${\varphi }_e\in P$ by dovetailing, running one task to semi-decide ${\varphi }_e\in Q$, which can clearly be done, and another task to semi-decide whether ${\varphi }_e(k)=0$ for all $k\le e$. This is correct because the zero function is detected by the second task, and conversely, if the second task returns true, then either ${\varphi }_e$ is zero, or ${\varphi }_e$ is only zero up to an index $n$, which must satisfy $e\le n$, which by definition of $Q$ implies that ${\varphi }_e\in Q$.

Proof of the Rice-Shapiro theorem

Let $P$ be a set of partial computable functions with semi-decidable index set. We prove the two implications separately.

Upward closedness

We first prove that if $f$ is a finite subfunction of $g$ and $f\in P$ then $g\in P$. The hypothesis that $f$ is finite is in fact of no use.

The proof uses a diagonal argument typical of theorems in computability. 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)$.

If ${\varphi }_p\notin P$, the first task can never finish, therefore the result of $p$ is entirely determined by the second task, thus ${\varphi }_p$ is simply $f$, a contradiction. This shows that ${\varphi }_p\in P$.

Thus, both tasks are relevant; however, because $f$ is a subfunction of $g$ and the second task returns $f(x)=g(x)$ when $f(x)$ is defined, while the first task returns $g(x)$ when defined, the program in fact computes $g$, i.e., ${\varphi }_p=g$, and therefore $g\in P$.

Extracting a finite subfunction

Conversely, we prove that if $P$ contains a partial computable function $f$, then it contains a finite subfunction of $f$. Let us fix $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 semi-algorithm terminates and returns true, then loop indefinitely.
• Otherwise, semi-compute $f$ on $x$, and if this terminates, return the result $f(x)$.

Suppose that ${\varphi }_p\notin 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\in P$. Thus, we must have ${\varphi }_p\in P$, and the algorithm for semi-deciding $P$ returns true on $p$ after a certain number of steps $n$. The partial function ${\varphi }_p$ can only be defined on inputs $x$ such that $x\le n$, and it returns $f(x)$ on such inputs, so it is a finite subfunction of $f$ that belongs to $P$.

Proof of the Kreisel–Lacombe–Shoenfield–Tseitin theorem

Preliminaries

A total function $h:\mathbb{N}\to \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 $h(n)=0$ for all $n\ge N$. 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$, the function ${\varphi }_{U(k)}$ is ultimately zero;
• For all total function $h$ which is ultimately zero, there exists $k$ such that ${\varphi }_{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 ${\varphi }_e$ is total, decides whether ${\varphi }_e\in 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\in P⟺h\in P$.

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

• If $x\le 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., ${\varphi }_p$ is total. Therefore, the promise to $P$ run on $p$ is fulfilled.

Suppose for contradiction that one of $f$ and ${\varphi }_p$ belongs to $P$ and the other does not, i.e., $({\varphi }_p\in P)\ne 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={\varphi }_p$, contradicting the fact that one of $f$ and ${\varphi }_p$ belongs to $P$ and the other does not. This argument proves that $f\in P⟺{\varphi }_p\in P$. Then, the second step makes $p$ return zero for sufficiently large $x$, thus ${\varphi }_p$ is ultimately zero; and by construction (due to the first step), ${\varphi }_p$ agrees with $f$ until $N$. Therefore, we can take $h={\varphi }_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$ be a total computable function and let $B$ be the boolean "$f\in 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)\in P)\ne 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 $\mathrm{\neg }B$, or $P$ does not terminate). Then $p$ actually computes $f$. In particular, ${\varphi }_p$ is total, so the promise to $P$ when run on $p$ is fulfilled, and $P$ returns the boolean ${\varphi }_p\in P$, which is $f\in 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\in P⟺g\in P$. Assume for contradiction that there exists $g$ total computable which agrees with $f$ until $n$ and such that $(g\in P)\ne B$.

Applying the lemma again, there exists $k$ such that $U(k)$ agrees with $g$ until $n$ and $g\in P⟺U(k)\in P$. Since both $U(k)$ and $f$ agree with $g$ until $n$, $U(k)$ also agrees with $f$ until $n$, and since $(g\in P)\ne B$ and $g\in P⟺U(k)\in P$, we have $(U(k)\in P)\ne 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)\in P)\ne 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 ${\varphi }_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\le n$, and we know that $U(k)$ agrees with $f$ until $n$.

In particular, ${\varphi }_p=U(k)$ is total. This makes the promise to $P$ run on $p$ fulfilled, therefore $P$ returns ${\varphi }_p\in P$ on $p$.

We have found a contradiction: one the one hand, the boolean ${\varphi }_p\in P$ is the return value of $P$ on $p$, which is $B$, and on the other hand, we have ${\varphi }_p=U(k)$, and we know that $(U(k)\in P)\ne B$.

Topological view

The set of total computable functions can be viewed as a subspace of the Baire space $𝒯\subseteq {\mathbb{N}}^{\mathbb{N}}$. The Kreisel–Lacombe–Shoenfield–Tseitin theorem states that if a function $F:𝒯\to 2$ (where the set of booleans $2$ has the discrete topology) is computable (from a program computing $f\in 𝒯$, we can compute $F(f)$), then $F$ must be continuous.

The above proof of the Kreisel–Lacombe–Shoenfield–Tseitin gives a strengthening of the theorem: from programs computing $F$ and $f$, one can compute $n$ such that $F$ is constant on functions agreeing with $f$ until $n$. This strengthened version has a natural interpretation from the point of view of realizability: inside the internal logic of the effective topos, it holds that every function ${\mathbb{N}}^{\mathbb{N}}\to 2$ is continuous.Template:R

For the Rice–Shapiro theorem, one views the set of partial computable functions as a subspace of the space $𝒫$ of all partial functions from $\mathbb{N}$ to $\mathbb{N}$ topologized in the following way: for each finite partial function $f$, the set of partial functions extending $f$ is declared to be a basic open set. The theorem states that if a subset $P\subseteq 𝒫$ is semi-decidable (from a program computing $f\in 𝒫$, we can semi-decide whether $f\in P$), then it must be open.