# Existence of algorithm for determining if a given number is rational or not

As far as I understand, it is not necessarily a easy thing to prove that a real number is rational or not. For example, according to http://mathworld.wolfram.com/e.html "$e+\pi \in \mathbb{Q}$?" is still an open problem.

This might be completely nonsense but I'm wondering there is something preventing the existence of a general algorithm which can "decide" whether any real number is rational or not in a finite number of steps?

I'm very much still a beginner in math and I thus for obvious reasons have a hard time reasoning about this question in a meaningful way. If we for the sake of argument assume that such a algorithm exists, would this lead to some contradiction?

-
For one thing, there are too many real numbers. –  André Nicolas Feb 26 '14 at 20:05
–  Bill Dubuque Feb 26 '14 at 20:35

The details of this depend a bit on how you imagine that input number to the algorithm is to be given -- there's no way to represent every real number as a finite combination of symbols that the algorithm can even inspect in a finite time.

However, it seems to be reasonable that if an algorithm such as the one you imagine exists at all, it ought to be able to formulate it such that it accepts input numbers given in the most explicit way imaginable:

Input: A computer program (or description of a Turing machine) that given $n$ produces the $n$th decimal digit of the real number we think about.

Output: "Yes" if the number we think about is rational, "No" otherwise.

One can prove that no algorithm with this input and output can exist. Namely, if it existed we could use it to decide the halting problem, which is known to be undecidable algorithmically.

Suppose we want to know whether Turing machine $T$ halts. We can then consider the real number $x$ whose digit number $n$ is

• $0$ is $T$ runs for at least $n$ steps,
• $1$ if $T$ halts in less than $n$ steps and $n$ is a perfect square, or
• $2$ if $T$ halts in less than $n$ steps and $n$ is not a perfect square

It is clear that this is a computable specification of the digits of $x$ -- for each digit we simply simulate $T$ for $n$ steps and see what happens.

Now if $T$ doesn't halt, $x$ will be $0$ -- in particular $x$ is rational. On the other hand, if $T$ does halt, $x$ will consist of a number of $0$s followed by an infinite sequence of $1$s and $2$s which never repeats (because the number of non-squares between successive squares increase monotonically). This, if $T$ halts, $x$ will be irrational.

If your algorithm existed, running it on this $x$ would tell us whether $T$ halts or not. But that is known to be impossible, so the algorithm cannot exist.

We might try to salvage this by requiring that the digits of $x$ must be given in some nicer way than by an unrestricted program that computes its digits. However, that doesn't lead us anywhere nice, because the digits of the number above are defined by a primitive recursive function, which is just about the simplest class of functions that one can argue are expressive enough to compute digits of most "interesting" real numbers, at least unless we cheat and introduce particular notations for "the digits of $e$", "the digits of $\pi$" and so forth for some hand-selected set of interesting constants.

-

Yes, there is an algorithm, the continued fraction expansion only terminates after a finite number of steps if the number is rational. In the case of irrational numbers, this expansion would not terminate, making the algorithm impractical.

Another question is, an algorithm needs an input. How would you encode the number $e+\pi$ for the computer? Any finite approximation already is a rational number.

-
That's not an algorithm, since it may never terminate. –  Bill Dubuque Feb 26 '14 at 20:16
@BillDubuque: Indeed. Here's a similarly easy "algorithm" to test if a number $x$ is rational or not: choose an enumeration $\{a_n\}$ of the rationals. The first step (n=1) is to test whether $x=a_1$. If so, $x$ is rational and you are done; if not, proceed to the next step. The nth step is to test whether $x=a_n$, etc. If the "algorithm" terminates, $x$ is rational. But you have the same problem -- you will only get an answer if $x$ is rational. –  MPW Feb 26 '14 at 23:20