10
$\begingroup$

Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?

Does this correspond in some direct way to the connectedness of the reals?

$\endgroup$
8
$\begingroup$

Yes, Rice's theorem for reals holds in every reasonable version of computable reals.

I will first prove a certain theorem and a corollary, and explain what it has to do with computability later.

Theorem: Suppose $p : \mathbb{R} \to \{0,1\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence $(x_i)_i$ such that $p(\lim_i x_i) \neq p(x_j)$ for all $j \in \mathbb{N}$.

Proof. We construct a sequence of pairs of reals $(y_i, z_i)_i$ as follows: \begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*} Observe that for all $i \in \mathbb{N}$:

  • $p(y_i) = 0$ and $p(z_i) = 1$
  • $|z_i - y_i| = |b - a| \cdot 2^{-i}$
  • $|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
  • $|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Thus the sequences $(y_i)_i$ and $(z_i)_i$ are Cauchy and they converge to a common point $c = \lim_i y_i = \lim_i z_i$. If $p(c) = 0$ then we take $(x_i)_i = (z_i)_i$, and if $p(c) = 1$ then we take $(x_i)_i = (y_i)_i$. $\square$

Corollary: Suppose $p : \mathbb{R} \to \{0,1\}$ and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then every Turing machine either runs forever or it does not run forever.

Proof. By the theorem, there is a Cauchy sequence $(x_i)_i$ such that $p(x_j) \neq p(\lim_i x_i)$ for all $j \in \mathbb{B}$. Without loss of generality we may assume that $p(x_j) = 1$ and $p(\lim_i x_i) = 0$.

Let $T$ be a Turing machine. Define a sequence $y_i$ by $$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases} $$ The sequence is well-defined because we may simulate $T$ up to $i$ steps and decide whether it has stopped or not within that many steps. Next, observe that $(y_i)_i$ is a Cauchy sequence because $(x_i)_i$ is a Cauchy sequence (we leave this as an exercise). Let $z = \lim_i y_i$. Either $p(z) = 0$ or $p(z) = 1$:

  • if $p(z) = 0$ then $T$ runs forever. Indeed, if it stopped after $j$ steps, then we would have $z = x_j$, and so $p(z) = p(x_j) = 1$ would contradict $p(z) = 0$.

  • if $p(z) = 1$ then $T$ does not run forever. Indeed, if it did, then we would have $z = \lim_i x_i$, and so $p(z) = p(\lim_i x_i) = 0$, contradicting $p(z) = 0$. $\square$

Now we can explain why this gives us Rice's theorem for real numbers. The proofs are constructive, therefore they yield computable procedures. This is true of any model of computability and any compute structure of reals that deserve to be so called. In fact, you can go back and read the proof as instructions for building a program -- all the steps are computable.

Thus, if we had a computable map $p : \mathbb{R} \to \{0,1\}$ and computable $a, b \in \mathbb{R}$ such that $p(a) = 0$ and $p(1) = 1$, then we could apply the computable procedures arising from the constructive proofs of the theorem and the corollary to create the Halting oracle. But the Halting oracle does not exist, therefore, every computable map $p : \mathbb{R} \to \{0,1\}$ is constant.

Supplemental: There was also a question about whether Rice's theorem is related to connectedness of the reals. Yes, it is essentially the statement that the reals are connected.

Let us first observe that a continuous map $p : X \to \{0,1\}$ (we take the discrete topology on $\{0,1\}$) corresponds to a pair of disjoint clopen (closed and open) sets $U, V \subseteq X$ such that $U \cup V = X$. Indeed, take $U = p^{-1}(\{0\})$ and $V = p^{-1}(\{1\})$. Because $p$ is continuous and $\{0\}$ and $\{1\}$ are open, $U$ and $V$ will be open, disjoint, and they obviously cover all of $X$. Conversely, any pair $(U,V)$ of disjoint clopens that cover $X$ determines a continuous map $p : X \to \{0,1\}$ that maps elements of $U$ to $0$ and elements of $V$ to $1$.

From this we learn that a space $X$ is disconnected if, and only if, there exists a continuous map $p : X \to \{0,1\}$ and $a, b \in X$ such that $p(a) = 0$ and $p(1) = b$ (we need $a$ and $b$ so that we get a non-trivial decomposition of $X$). There is another way to say the same thing: a space $X$ is connected if, and only if, all continuous maps $X \to \{0,1\}$ are constant.

In computable mathematics we have a basic theorem: every computable map is continuous. So, as long as we are within the realm of computable objects, Rice's theorem does in fact state that a certain space is connected. In the case of the classic Rice's theorem the space in question is the space of partial computable functions $\mathbb{N} \to \mathbb{N}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! This is what I was looking for. Any idea about the the other question -- whether this is directly related to connectedness of the reals? $\endgroup$ – Shachaf Sep 4 '17 at 7:45
  • $\begingroup$ I added an explanation about the fact that Rice's theorem is in fact a form of connectedness theorem. $\endgroup$ – Andrej Bauer Sep 4 '17 at 13:06
  • $\begingroup$ Suppose $p(x)=1, p(x')=0$ and define $y_i=x$ if $T$ does not halt within $i$ steps and $y_i=x'$ otherwise. If T does not halt then $y_i$ converges to $x$, otherwise it converges to $x'$. If $x,x'$ are computable, then given $T$, one can generate a machine computing the limit of $y_i$. Why is this not enough to show that $p$ cannot be computable, or even semidecidable (as $T$ does not halt iff $p$ is $1$ on the limit). Obviously I am missing something, since there are nontrivial properties which are semidecidable. $\endgroup$ – Ariel Nov 12 '18 at 12:26
  • 1
    $\begingroup$ Your definition of $T$ is ok, but you also need a computable rate of convergence of the sequence $y_i$ in order to claim that its limit is computable. Since we cannot compute at which index $i$ the sequence $y_i$ might jump from $x$ to $x'$ (or else we could compute at which step $T$ will halt), such a computable rate of convergence cannot be had. $\endgroup$ – Andrej Bauer Nov 12 '18 at 12:29
-1
$\begingroup$

No. Or, at least, the proof isn't trivial, since you can choose among the (generally many) possible ways to compute a real, and may be able to choose one with a structure that is total w.r.t. the chosen property so that you don't reduce testing the property to the halting problem.

Also, I think I need a better understanding of what "nontrivial" means w.r.t. the properties of numbers. For Rice's theorem, "nontrivial" is basically non-syntactic and not implied by syntax. However each computable real number isn't a single program, but rather an equivalence class full of programs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you mean, here. Are you trying to distinguish between computable real numbers (e.g., $2$, $22/7$, $\pi$, etc.) and the programs that compute them? Sure, there are infinitely many programs that compute each computable real but there are also infinitely many Turing machines that decide any decidable language, and the ordinary Rice's theorem doesn't have any problem with that. $\endgroup$ – David Richerby Jul 5 '17 at 0:36
  • $\begingroup$ Do different representations of computable reals actually have significantly different computability properties? Let's say I'm using one of the definitions at en.wikipedia.org/wiki/Computable_number, e.g. a computable real is represented by a program that takes a rational error bound and produces an approximation within that bound. I mean "trivial" in the same sense sense as Rice's theorem: A property that applies to all computable reals or to none of them. It's true that each number can be represented by multiple programs, but that's true of partial functions as well. $\endgroup$ – Shachaf Jul 5 '17 at 0:41
  • $\begingroup$ @Shachaf That's more "trivial" than Rice's Theorem requires. "Syntactic" properties are also trivial -- e.g. "has at least 4 states reachable from the initial state", "has a connected state graph", "has no transition that writes X to the tape", etc. -- and they need no apply to every machine. $\endgroup$ – Boyd Stephen Smith Jr. Jul 6 '17 at 19:07
  • $\begingroup$ @DavidRicherby Yes, I think the distinction is necessary. If you are able to work exclusively with total or productive representations, you have more power. $\endgroup$ – Boyd Stephen Smith Jr. Jul 6 '17 at 19:10
  • $\begingroup$ Rice's theorem is about properties of partial functions, not algorithms that compute them. Similarly I'm asking about properties of computable reals, not programs that compute them. $\endgroup$ – Shachaf Jul 6 '17 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.