Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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