23
$\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
  • 4
    $\begingroup$ How is the computable number given? $\endgroup$ Commented 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$ Commented Feb 17, 2013 at 12:00
  • 3
    $\begingroup$ Similar question: cstheory.stackexchange.com/questions/10495/… $\endgroup$ Commented Feb 17, 2013 at 13:41
  • 4
    $\begingroup$ I will repeat what you and I said in my own words. I said that a computable number (in whatever encoding) with a flag whether the number is an integer or not is a valid encoding of a computable number (although it is a silly encoding), and therefore you should have specified encoding. You objected by saying that that flag cannot be computed when operations on computable numbers are performed. I said that whether the flag can be computed is irrelevant to whether something is a valid encoding or not. I am not sure how to state this more clearly, so this is my last comment in this thread. $\endgroup$ Commented Feb 19, 2013 at 0:31
  • 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$ Commented Feb 19, 2013 at 7:22

6 Answers 6

44
$\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$ Commented 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$ Commented Feb 19, 2013 at 17:10
  • 8
    $\begingroup$ I need to write a textbook — (Google google google). Okay, good, you have tenure. Go for it! $\endgroup$
    – Jeffε
    Commented 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$ Commented 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$ Commented Feb 19, 2013 at 23:17
12
$\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$
6
  • $\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
    Commented 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
    Commented 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
    Commented Feb 19, 2013 at 6:49
  • $\begingroup$ This answer seems to be reducing the problem in question to the halting problem, and then claiming that the problem in question is therefore undecidable. But to reach that conclusion, the reduction should go in the other direction: that is, one should reduce the halting problem to the problem in question. That is, however, also easy to do. $\endgroup$
    – Neal Young
    Commented Feb 2 at 14:09
  • $\begingroup$ @NealYoung - I don't think there's a mistake in my answer. I reduce from the halting problem to the "rationality" problem, not the other way around. I initially fix some computable irrational number x, and then the input for the reduction is a TM M, and the output is a TM that computes a number, which is exactly x if M doesn't halt, and is rational if M halts. $\endgroup$
    – Shaull
    Commented Feb 2 at 18:57
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
    Commented 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
    Commented Feb 19, 2013 at 7:36
7
$\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$
1
$\begingroup$

As a (hopefully fun) exercise, we pin down the complexities of the two problems more precisely. Let $x$ be a given computable number (encoded as defined in the post).

Lemma 1. The problem of determining whether $x$ is an integer is complete for $\Pi_1$.

Lemma 2. The problem of determining whether $x$ is rational is complete for $\Sigma_2$.

In other words, the first problem is equivalent (under many-one reductions) to determining whether a given TM runs forever on empty input. The second problem is equivalent to determining whether a given TM has any input that makes it run forever. (This is strictly harder than the first problem.)

[EDIT: An answer to a related post shows that determining whether $x$ is transcendental is complete for $\Pi$.]

This answer can be viewed as a detailed elaboration of Saul's previous answer.

Here is how a number $x$ is encoded, according to the post:

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 \mathbb{Q}$ or $x \in \mathbb{Z}$?

Specifically, we assume that the function $f_x$ is encoded by (the encoding of) a TM $M_x$ that computes $f_x(\epsilon)$ given any $\epsilon$.

Let $Z$ denote the problem of determining whether a given computable number $x$ is an integer (that is, in $\mathbb Z$). Let $Q$ denote the problem of determining whether a given $x$ is rational (that is, in $\mathbb Q$). Let $\mathbb Q_+$ denote the positive rationals.

First upper bound: $Q$ is in $\Sigma_2$

To see that $Q$ is in $\Sigma_2$, note that, given an $x$ via a TM $M_x$ computing $x$ as described above, $x$ is rational if and only if $$(\exists q\in \mathbb Q) ~ (\forall \epsilon \in \mathbb Q_+) ~|M_x(\epsilon) - q| \le \epsilon.$$ Further, given $\epsilon$, $M_x$, and $q$, the condition $|M_x(\epsilon) - q| \le \epsilon$ is computable. By definition of $\Sigma_2$, this shows $Q\in \Sigma_2$.

Second upper bound: $Z$ is in $\Pi_1$

By similar reasoning, $Z$ is in $\Sigma_2$. But in fact something stronger holds: $Z$ is in $\Pi_1$. To see this note that $x$ must be at distance at most $1/10$ from $M_x(1/10)$, so, if $x$ is an integer, it has to equal $\lfloor M_x(1/10) + 1/2 \rfloor$. Hence, $x$ is an integer if and only ifn $$(\forall \epsilon \in \mathbb Q_+) ~|M_x(\epsilon) - \lfloor M_x(1/10) + 1/2 \rfloor| \le \epsilon.$$ The condition $|M_x(\epsilon) - \lfloor M_x(1/10) + 1/2 \rfloor| \le \epsilon$ is computable. So $Z\in \Pi_1$.

Hardness results

Next we sketch proofs that the two "upper bounds" above are tight. That is, each problem is hard (under many-one reductions) for its respective class.

First hardness result: $Q$ is $\Sigma_2$-hard

We give a reduction via the following intermediate problem:

Problem $F$ (for "finite"). Given (the encoding of) a TM $M$ that enumerates a sequence of bits, is $\sum_i M_i$ (where $M_i$ is the $i$th bit enumerated by $M$) finite?

Claim 1. $F$ is $\Sigma_2$-hard


We prove the claim by reduction from the following problem which is well known (and easily shown) to be $\Sigma_2$-complete:

Given a TM $M$, is there an input on which $M$ runs forever?

Given such an $M$, the reduction outputs the following TM $M'$:

TM $M'$:

  1. for each input $y_1, y_2, \ldots$ to $M$ (in any order) do:
  2. $~~~$ output 1
  3. $~~~$ simulate $M(y_i)$, outputting a 0 at each step of the simulation
  4. $~~~~~$ (if $M(y_i)$ halts, stop and move on to the next input $y_{i+1}$)

If $M$ halts on all inputs, then $\sum_i M'_i$ is infinite. On the other hand, if $M$ runs forever on some input, then, when the outer loop runs for the first such input, say $y_f$, the inner loop never terminates, so $\sum_i M'_i = f < \infty$. Hence, the reduction is correct, proving the claim.


To prove that $Q$ is $\Sigma_2$-hard, we will reduce $F$ to $Q$.

Let $M$ be any TM that enumerates a bit sequence $M_1, M_2, \ldots$. Define $$x(M) = \displaystyle\sum_{i=1}^\infty \frac{M_i}{i!}.$$

Claim 2. $x(M)$ is rational iff $\langle M \rangle \in F$ (i.e., $\sum_i M_i < \infty$).

Indeed, if $\sum_i M_i < \infty$, then $x(M)$ is the sum of finitely many rationals, so is rational. Conversely, if $\sum_i M_i = \infty$, then for any integer $m$ we have $$m! x(M) = \sum_{i=1}^\infty M_i m!/i!,$$ and the first $m$ terms in the sum are integers, while the sum of the remaining terms is strictly positive but at most $\sum_{i>m} 1/m^{i-m} < 1$. So $m! x(M)$ is not an integer for any integer $m$. So $x(M)$ is not rational. This proves Claim 2.

Given $M$ as described above, the reduction (from $F$ to $Q$) outputs the following TM $M'$:

TM $M'$ on input $\epsilon>0$:

  1. return $\sum_{i=1}^{m(\epsilon)} M_i / i!$, where $m(\epsilon) = \lceil 2/\epsilon\rceil$

Note that $M'$ computes (by OP's definition) $x(M)$. (Indeed, $\sum_{n=m(\epsilon)}^{\infty} 1/n! < \epsilon$, so the sum returned by $M'(\epsilon)$ is within $\epsilon$ of $x(M)$.)

By Claim 2, then, $\langle M' \rangle \in Q$ iff $\langle M \rangle \in F$. That is, the reduction is correct. This shows that $Q$ is also $\Sigma_2$-hard. This completes the proof of Lemma 2.

Second hardness result: $Z$ is $\Pi_1$-hard

The proof is by reduction from the complement of the halting problem. Given a TM $M$, the reduction outputs a computable $x$ such that $x$ is an integer iff $M$ runs forever on empty input.

The machine $M_x$ that computes $x$ does the following:

TM $M_x$ on input $\epsilon$:

  1. simulate $M()$ for $1/\epsilon$ steps
  2. if $M()$ does not halt within $1/\epsilon$ steps: output $0$
  3. else: output $1/(h+1)$, where $M()$ halts in $h \le 1/\epsilon$ steps

If $M()$ never halts, then $M_x$ always outputs 0, and $x=0$ (which is an integer). If $M()$ halts in some $h$ steps, then $M_x$ outputs $0$ for $\epsilon \ge 1/h$, and outputs $1/(h+1)$ for all smaller $\epsilon$. In this case $x=1/(h+1)$ (which is not an integer).

We leave it as an exercise to verify that $|M_x(\epsilon) - x| \le \epsilon$ for all $\epsilon\ge 0$, as required.

This completes the reduction and the proof of Lemma 1.


Note on a technical subtlety. A-priori, the problems $Q$ and $Z$ are promise problems. The input is encoded as a TM $M_x$ that is promised to encode some $x$ via a function $f_x$. To be complete, we should specify what decision should be reached in the event that the given TM does not properly encode such an $x$.

Given that $M$ computes a function (with rational input and output), $M$ will properly encode some $x$ if and only if

  1. $M$ halts on all inputs, and
  2. $|M_x(\epsilon_1) - M_x(\epsilon_2)| \le \epsilon_1 + \epsilon_2$ for all inputs $\epsilon_1$ and $\epsilon_2$.

Deciding Condition 1 (whether $M$ halts on all inputs) is $\Pi_2$-complete, so requiring the decider of $Q$ or $Z$ to verify the first condition for an arbitrary TM would increase the complexity of both problems. On the other hand, with some reasonable (and detectable) restriction on $M$ (e.g., that its encoding is in a form that guarantees that it terminates), this issue goes away. Resolving this issue that way seems more in the spirit of OP's question.

The remaining question is then whether the Condition 2 above holds for all $\epsilon_1, \epsilon_2$. Determining this for an arbitrary TM can be done in $\Pi_1$. So simply requiring the decider to determine whether the condition is met should not increase the complexity of either problem.

$\endgroup$

Your Answer

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

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