Decidable properties of computable reals

Question

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?

Answer 1

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}$.

Answer 2

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.