7
$\begingroup$

Can the equality of two real numbers always be determined?

Let us say that we have derived an expression for a real number X. We also have obtained an (entirely different) expression for a real number Y.

Now one mathematician claims that X and Y must necessarily be exactly equal. Another mathematician claims that X and Y can not be equal, however their difference is extremely small; say 0.5^N with N some unknown but very large number.

To settle the dispute the mathematicians decide to use a Turing machine.
As input the machine takes the binary expansions x(n) for X [n=1,2,3,4...] and y(n) for Y. If the machine finds that for some n the pair of digits x(n) and y(n) are unequal, then it concludes that X and Y are unequal and the program halts. However if X and Y are equal, the machine will continue to check digits "ad infinitum" without ever reaching a conclusion. So in the case of equality (X = Y) there appears to be no halting criterium.

In the example that I described, the Turing machine is of no great help. The machine just continues to run "forever". Thus it remains unresolved whether this is because X and Y are exactly equal, or whether they are unequal but the first difference in their digits occurs at some unattainable high index N (required CPU time > age of the universe).

  • 0
    Most real numbers are transcendental which means they have an infinite expansion, if the two numbers are very close it may take "forever" to compare them. If however you already have an expression for one simply verify that the expression holds for the second. Note, however that most real numbers won't have such nice expression.2012-05-11
  • 0
    I wonder whether your second mathematician can know that. It might help to examine how he could reach that conclusion. For example, I can demonstrate X and Y are distinct by exhibiting a rational number Z between them. How else can I know they're distinct?2012-05-11
  • 3
    Case in point: $X = 0$, $Y = \sum_{n=1}^\infty 2^{-n} d_n$ where $d_n = 1$ if $n$ is an odd perfect number and $0$ otherwise. So if we could tell whether or not $X=Y$ we would know whether or not an odd perfect number exists. Similarly for many other unsolved questions of number theory.2012-05-13

2 Answers 2