22
$\begingroup$

Is it possible to algorithmically test if a computable number is rational or integer? In other words, would it be possible for a library that implements computable numbers to provide the functions isInteger or isRational?

I am guessing that it is not possible, and that this is somehow related to the fact that it is not possible to test if two numbers are equal, but I don't see how to prove it.

Edit: A computable number $x$ is given by a function $f_x(\epsilon)$ that can return a rational approximation of $x$ with precision $\epsilon$: $|x - f_x(\epsilon)| \leq \epsilon$, for any $\epsilon > 0$. Given such function, is it possible to test if $x \in \mathrm{Q}$ or $x \in \mathrm{Z}$?

$\endgroup$
14
  • 3
    $\begingroup$ How is the computable number given? $\endgroup$ Feb 17, 2013 at 5:32
  • 10
    $\begingroup$ How the number is given is of course relevant. As a silly example, if the input contains a flag whether the number is an integer or not, deciding if the input is an integer or not is trivial. $\endgroup$ Feb 17, 2013 at 12:00
  • 3
    $\begingroup$ Similar question: cstheory.stackexchange.com/questions/10495/… $\endgroup$ Feb 17, 2013 at 13:41
  • 3
    $\begingroup$ (1) “How do you know that this is an integer?” Why should I care? You did not say anything about requirements about operations. (2) “If you see the two answers so far, they don't mention anything about the implementation.” I do not know what you mean by “implementation” here, or why this sentence is relevant to my comments. $\endgroup$ Feb 18, 2013 at 23:55
  • 17
    $\begingroup$ I hope my answer burries this discussion. Tsuyoshi, you are mistaken, it is relevant what operations are computable. We do not implement real numbers in a vacuum, but in order to do manipulate them. According to you, we could just use the unit type to implement everything. Yes, we could, but then some operations would not be computable, and that is precisely the criterion by which we judge representations. $\endgroup$ Feb 19, 2013 at 7:22

5 Answers 5

42
$\begingroup$

It is easy to get confused about what it means to "represent" or "implement" a real number. In fact, we are witnessing a discussion in the comments where the representation is contentious. So let me address this first.

How do we know that an implementation is correct?

The theory which explains how to represent things in a computer is realizability. The basic idea is that, given a set $X$, we pick a datatype $\tau$ and to every $x \in X$ a set of values of type $\tau$ which realize it. We write $v \vdash x \in X$ when $v$ is a value that realizes $x$. For example (I shall use Haskell for no good reason), a sensible implementation of $\mathbb{N}$ might be the datatype Integer where $v \vdash k \in \mathbb{N}$ when $v$ evaluates to the numeral $\overline{k}$ (thus in particular -42 does not represent a natural number, and neither does a diverging program). But some joker could walk by and suggest that we use Bool to represent natural numbers with $\mathtt{True} \vdash 42 \in \mathbb{N}$ and $\mathtt{False} \vdash n \in \mathbb{N}$ for $n \neq 42$. Why is this incorrect? We need a criterion.

In the case of "joker numbers" the easy observation is that addition cannot be implemented. Suppose I tell you I have two numbers, both represented by $\mathtt{False}$. Can you give a realizer for their sum? Well, that depends on whether the sum is 42, but you cannot tell. Since addition is an "essential part of what natural numbers are", this is unacceptable. In other words, implementation is not about sets, but about structures, i.e., we have to represent sets in such a way that it is possible to also implement the relevant structure. Let me stress this:

We implement structures, not bare sets. Therefore, we have to be able to implement the entire structure, together with operations and all the axioms, in order for the implementation to be correct.

If you do not abide by this principle, then you have to suggest an alternative mathematical criterion of correctness. I do not know of one.

Example: representation of natural numbers

For natural numbers the relevant structure is described by Peano axioms, and the crucial axiom that has to be implemented is induction (but also $0$, successor, $+$ and $\times$). We can compute, using realizability, what the implementation of induction does. It turns out to be a map (where nat is the yet unknown datatype which represents natural numbers)

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

satisfying induction x f zero = x and induction x f (succ n) = f n (induction x f n). All this comes out of realizability. We have a criterion: an implementation of natural numbers is correct when it allows an implementation of Peano axioms. A similar result would be obtained if we used the characterization of numbers as the initial algebra for the functor $X \mapsto 1 + X$.

Correct implementation of real numbers

Let us turn attention to the real numbers and the question at hand. The first question to ask is "what is the relevant structure of the real numbers?" The answer is: Archimedean Cauchy complete ordered field. This is the established meaning of "real numbers". You do not get to change it, it has been fixed by others for you (in our case the alternative Dedekind reals turn out to be isomorphic to the Cauchy reals, which we are considering here.) You cannot take away any part of it, you are not allowed to say "I do not care about implementing addition", or "I do not care about the order". If you do that, you must not call it "real numbers", but something like "real numbers where we forget the linear order".

I am not going to go into all the details, but let me just explain how the various parts of the structure give various operations on reals:

  • the Archimedean axiom is about computing rational approximations of reals
  • the field structure gives the usual arithmetical operations
  • the linear order gives us a semidecidable procedure for testing $x < y$
  • the Cauchy completeness gives us a function lim : (nat -> real) -> real which takes a (representation of) rapid Cauchy sequence and returns its limit. (A sequence $(x_n)_n$ is rapid if $|x_n - x_m| \leq 2^{-\min(n,m)}$ for all $m, n$.)

What we do not get is a test function for equality. There is nothing in the axioms for reals which asks that $=$ be decidable. (In contrast, the Peano axioms imply that the natural numbers are decidable, and you can prove that by implementing eq : nat -> nat -> Bool using only induction as a fun exercise).

It is a fact that the usual decimal representation of reals that humanity uses is bad because with it we cannot even implement addition. Floating point with infinite mantissa fails as well (exercise: why?). What works, however is signed digit representation, i.e., one in which we allow negative digits as well as positive ones. Or we could use sequences of rationals which satisfy the rapid Cauchy test, as stated above.

The Tsuyoshi representation also implements something, but not $\mathbb{R}$

Let us consider the following representation of reals: a real $x$ is represented by a pair $(q,b)$ where $(q_n)_n$ is a rapid Cauchy sequence converging to $x$ and $b$ is a Boolean indicating whether $x$ is an integer. For this to be a representation of the reals, we would have to implement addition, but as it turns out we cannot compute the Boolean flags. So this is not a representation of the reals. But it still does represent something, namely the subset of the reals $\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$. Indeed, according to the realizability interpretation a union is implemented with a flag indicating which part of the union we are in. By the way, $\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$ is a not equal to $\mathbb{R}$, unless you believe in excluded middle, which cannot be implemented and is therefore quite irrelevant for this discussion. We are of forced by computers to do things intuitionistically.

We cannot test whether a real is an integer

Finally, let me answer the question that was asked. We now know that an acceptable representation of the reals is one by rapid Cauchy sequences of rationals. (An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.)

Theorem: Testing whether a real is an integer is not decidable.

Proof. Suppose we could test whether a real is an integer (of course, the real is realized by a rapid Cauchy sequence). The idea, which will allow you to prove a much more general theorem if you want, is to construct a rapid Cauchy sequence $(x_n)_n$ of non-integers which converges to an integer. This is easy, just take $x_n = 2^{-n}$. Next, solve the Halting problem as follows. Given a Turing machine $T$, define a new sequence $(y_n)_n$ by $$y_n = \begin{cases} x_n & \text{if $T$ has not stopped within $n$ steps}\\ x_m & \text{if $T$ stopped in step $m$ and $m \leq n$} \end{cases}$$ That is, the new sequence looks like the sequence $(x_n)_n$ as long as $T$ runs, but then it gets "stuck" at $x_m$ if $T$ halts in step $m$. Very importantly, the new sequence is also a rapid Cauchy sequence (and we can prove this without knowing whether $T$ halts). Therefore, we can compute its limit $z = \lim_n y_n$, because our representation of reals is correct. Test whether $z$ is an integer. If it is, then it must be $0$ and this only happens if $T$ runs forever. Otherwise, $z$ is not an integer, so $T$ must have stopped. QED.

Exercise: adapt the above proof to show that we cannot test for rational numbers. Then adapt it to show we cannot test for anything non-trivial (this is a bit harder).

Sometimes people get confused about all this testing business. They think we have proved that we can never test whether a real is an integer. But surely, 42 is a real and we can tell whether it is an integer. In fact, any particular real we come up with, $\sin 11$, $88 \ln 89$, $e^{\pi \sqrt{163}}$, etc., we can perfectly well tell whether they are integers. Precisely, we can tell because we have extra information: these reals are not given to us as sequences, but rather as symbolic expressions from which we can compute the Tsuyoshi bit. As soon as the only information we have about the real is a sequence of rational approximations converging to it (and I do not mean a symbolic expression describing the sequence, but a black box which outputs the $n$-th term on input $n$) then we will be just as helpless as machines.

The moral of the story

It makes no sense to talk about implementation of a set unless we know what sort of operations we want to perform on it.

$\endgroup$
25
  • 16
    $\begingroup$ If my answers were wives, I could only answer once. Or at least I would have to delete the previous answer before I wrote the next one. $\endgroup$ Feb 19, 2013 at 7:40
  • 5
    $\begingroup$ @Max: the first theorems of this kind were given by Kreisel, Lacombe and Shoenfield (look up KLS theorem). Independently Tsteitin gave a theorem which generalized KLS and was explicitly of the form "every computable map is computably continuous". $\endgroup$ Feb 19, 2013 at 17:10
  • 6
    $\begingroup$ I need to write a textbook — (Google google google). Okay, good, you have tenure. Go for it! $\endgroup$
    – Jeffε
    Feb 19, 2013 at 18:22
  • 10
    $\begingroup$ @Tsuyoshi: The question used the established phrase "real number" without a qualification. The structure of real numbers is standard. You are free to consider other structures, but you are not free to misinterpret standard terminology. $\endgroup$ Feb 19, 2013 at 22:03
  • 21
    $\begingroup$ Technically speaking, you are correct, the word "real" was not used. But you are mistaken about the definition of real numbers. Or I would put it this way: it is bad mathematics to think that the reals are a particular set which comes first, only to be followed by some structure. Just like we define groups, rings, topological spaces, etc., in terms of their structure, so we should define special objects in terms of their universal properties (natural numbers are the initial semiring, integers the initial ring, rationals initial field, reals the .....). $\endgroup$ Feb 19, 2013 at 23:17
10
$\begingroup$

I tend to think this is undecidable:

Let $x$ be a computable irrational number. Consider a TM $M$. You can construct a function that runs $M$ on $\epsilon$, and in parallel computes $x$ with growing precision. If $M$ halts, it stops computing $x$, otherwise it continues.

Deciding if this function computes a rational number is equivalent to the halting problem.

$\endgroup$
3
  • $\begingroup$ I don't understand your answer, could you please elaborate more? I don't understand how do you relate it with the halting problem, and more importantly, I think there is no reason for $M$ to ever halt (even if $x$ is an integer). $\endgroup$
    – dbarbosa
    Feb 19, 2013 at 0:31
  • $\begingroup$ As Tsuyoshi has pointed out the answer depends on the representation and the model of computation. Your answer correctly says that if take the inputs to be computable real numbers given by a TM computing them then equality is not decidable. This is correct, however it is not close to any model that is used in practice. $\endgroup$
    – Kaveh
    Feb 19, 2013 at 6:09
  • 2
    $\begingroup$ Indeed, my answer refers to representations as posted in the question, be them practical or not. @dbarbosa - I'll explain: given a TM $M$, follow the construction in the answer. Then, assume by way of contradiction that you can decide whether the outputted machine represents a rational or not. If it is a rational, it means that at some point, $M$ halted and we cease to compute the number. On the other hand, if it is irrational, then $M$ doesn't halt. Thus, we know whether $M$ halts, solving the halting problem, which is known to be undecidable. $\endgroup$
    – Shaull
    Feb 19, 2013 at 6:49
10
$\begingroup$

Assuming a real is given as a sequence of rational approximations with the error bounded by some known computable function which tends to zero (all such approximations are equivalent, and correspond to the usual topology on the reals).

Computable functions are continuous. IsRational and IsInteger are not continuous and therefore not computable.

IsInteger is semi-computable: there is a procedure that will eventually output "false" if the input is not an integer, but will run forever if the input is an integer. This procedure simply looks at each approximation and checks whether there is an integer within the error bound. This function is continuous when we use the Sierpiński topology on {true, false} (i.e. {false} is an open set but {true} is not).

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I don't understand the not continuous => not computable, I am guessing that you used a (probably widely known) theorem that I am not aware of or that I am not remembering. Could you please provide more detail about this step? $\endgroup$
    – dbarbosa
    Feb 18, 2013 at 23:41
  • 1
    $\begingroup$ "computable => continuous" seems to be a folk theorem -- I can't find an original citation. The theory of computation on infinite objects and the connections to topology are described quite well (IMO) in these course slides by Brattka (math.uni.wroc.pl/~pkowa/slides/brattka.pdf). Proposition 2 in the slides states that all computable functions on sequences of naturals are continuous; combined with Theorem 12 one gets the result for functions of other types. $\endgroup$
    – Max
    Feb 19, 2013 at 7:36
6
$\begingroup$

It is undecidable whether a given computable number is equal to zero.

(So your rational approximation oracle returns 0 for every ε you've tried? Maybe you just haven't given it a small enough ε.)

Thus, it's undecidable whether a given computable number between -½ and +½ is an integer.

$\endgroup$
2
$\begingroup$

A function being computable is a stronger than the function being continuous, i.e. any computable function needs to be continuous in the information topology.

You want to see if the function $F:\mathbb{R} \to \{Yes,No\}$ defined by

$$ F(r) = \begin{cases} YES & r\in \mathbb{Q}\\ NO & o.w. \end{cases} $$

is computable.

Let's assume that similar to what you wrote, real numbers are given by black-boxes and a real number black-box $r$ can be used to obtain a rational number of the form $\frac{k}{2^{n}}$ such that $r \in [\frac{k}{2^n},\frac{k+1}{2^n}]$ for any natural number $n$.

Then your function is not continuous and is therefore not computable.

Here is a more direct and intuitive adversary argument: Let $M$ be a machine. Assume that the number is $0$. Assume that for $n$ the black-box returns $[-\frac{1}{2^n},\frac{1}{2^n}]$. If $M$ doesn't halt we are done. If it halts, let the largest number that $M$ has asked an approximation for to be $m$. Then information that $M$ has seen up to this point is consistent with the real number being any real number in the interval $[-\frac{1}{2^m},\frac{1}{2^m}]$, i.e. $M$ doesn't have enough information to correctly solve the problem. If $M$ answers $NO$ then the answer is incorrect. If it answers $YES$ then we can consider running $M$ on any irrational number in the interval $[-\frac{1}{2^m},\frac{1}{2^m}]$ and $M$ will incorrectly answer $YES$ since it will get exactly the same information from the black-box. Therefore $M$ cannot solve the problem correctly.

The proof that any computable function needs to be continuous is similar.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.