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!
Best Answer
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.