MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Uncomputability of the identity relation on computable real numbers

Let $f_{=}$ be a function from $\mathbb{R}^{2}$ be defined as follows: (1) if $x = y$ then $f_{=}(x,y) = 1$; (2) $f_{x,y} = 0$ otherwise.

I would like to have a proof for / a reference to a textbook proof of the following theorem (if it indeed is a theorem):

$f_{=}$ is uncomputable even if one restricts the domain of $f_{=}$ to a proper subset of $\mathbb{R}^{2}$, viz. the set of the computable real numbers

Thanks!

-
You should specify which model of computation over the reals you have in mind. – wood Sep 30 2010 at 14:18
Rice's theorem: en.wikipedia.org/wiki/Rice%27s_theorem – Mark Sapir Sep 30 2010 at 14:20
@Wood: The question is specific enough. There is no ambiguity in the term "computable real number". – Mark Sapir Sep 30 2010 at 14:21
@Mark: I agree for the term "computable real number". But he is referring to a computable function over the reals. Does he mean the Blum-shub-Smale model or something else. I think there maybe different models. When I first read the question, I thought trivially yes under der BSS model. – wood Sep 30 2010 at 14:27
@Wood: He restricts the function to computable reals. The function takes Turing machines computing $x,y$ and produces 1 or 0. By Rice theorem the function is not computable: you cannot check if two Turing machines recognize the same language. – Mark Sapir Sep 30 2010 at 15:26
show 2 more comments

Suppose that $f_=$ is computable when restricted to computable real numbers, which means that there exists a Turing machine that, given as input the encoding of two Turing machines $M_1$ and $M_2$ that compute the fractional digits of two computable real numbers $r_1$ and $r_2$ in $[0,1]$, produces $1$ if $r_1 = r_2$ and $0$ otherwise. I will use this assumption to show that the Halting problem is also computable, which is impossible.

Given a Turing machine $M$ and an input $x$ for which we want to know if $M$ on input $x$ halts or not, let $M_x$ be the Turing machine that acts as follows: given an integer $i$ as input, $M_x$ starts a simulation of $M$ on input $x$ for up to $i$ steps, and if the simulation does not halt within that number of steps, it outputs $0$ and otherwise it outputs $1$. By definition, $M_x$ computes the digits of a computable real number (more precisely, it computes the $i$-th digit for every given $i$). Moreover, that real number is $0$ if $M$ on input $x$ does not halt, and the real number $0.0\cdots 011 \cdots = 2^{-k}$ otherwise for some $k \geq 1$. In other words, $M_x$ computes the real number $0$ if and only if $M$ on input $x$ does not halt. To complete the argument, note that $0$ is a computable real number, so if you could tell whether two computable real numbers are equal you would also be able to tell if $M$ on input $x$ halts or not.

-

Aren't computable functions of reals automatically continuous? And isn't your function discontinuous? Of course you need a definition of computable in this setting to make sense of this...

-
 If you take away some neighbourhood of the diagonal the continuity obstruction vanishes (the OP allowed proper subsets of R^2). – Peter Arndt Sep 30 2010 at 15:37 I thought the question only allowed one proper subset, namely the one consisting only of pairs of computable reals. – Carl Mummert Sep 30 2010 at 19:03 I guess you are right, Carl. – Peter Arndt Sep 30 2010 at 20:40

The main difficulty in finding a reference for this is that it's so well known :). The fact that equality of reals is only (negatively) semidecidable is a basic and important result in both computable analysis and constructive analysis.

The underlying phenomenon here is about continuity. As Gerald Edgar says, the equality function is not continuous (in particular, it's not sequentially continuous). The proof that slimton presents shows not only that it's discontinuous, but that it's effectively discontinuous: we can make an effective sequence of effective reals that witnesses the discontinuity.

This is closely related to the type-2 functional $E\colon \{0,1\}^\omega \to \{0,1\}$ defined such that $E(f) = 1 \leftrightarrow (\exists k)(f(k) = 1)$. This functional is not computable.

If you look more deeply at slimton's proof, you see that he actually proves that if you had a uniform way to test equality of reals, then you would have a uniform way to compute $E$. In particular the problem of computing equality of computable reals is no easier than that of computing $E$ on computable reals. It can be shown with only a little more work that these are equivalent problems.

This phenomenon is a particular instance of a general phenomenon first studied by Grilliot [1] and now called Grilliot's trick: a functional $\Phi$ is effectively discontinuous if and only if $E$ is computable from $\Phi$. In particular, no effectively discontinuous functional is computable.

1: Thomas J. Grilliot, "On Effectively Discontinuous Type-2 Objects", Journal of Symbolic Logic v. 36, n. 2 (Jun., 1971), pp. 245-248. http://www.jstor.org/stable/2270259

-

Dan Richardson in Bath has extensively studied the problem of recognizing zero under various hypotheses. I would be hard-pressed to give you an account of the details, because there is a lot of subtle and surprising results, but his page has all his papers and I'm sure you can find something of interest there.

-