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'$:
- for each input $y_1, y_2, \ldots$ to $M$ (in any order) do:
- $~~~$ output 1
- $~~~$ simulate $M(y_i)$, outputting a 0 at each step of the simulation
- $~~~~~$ (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$:
- 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$:
- simulate $M()$ for $1/\epsilon$ steps
- if $M()$ does not halt within $1/\epsilon$ steps: output $0$
- 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
- $M$ halts on all inputs, and
- $|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.
My understanding is that how they are given is irrelevant to answer this question.
For more information about Computable Numbers, take a look at http://en.wikipedia.org/wiki/Computable_number. One implementation in C++ is http://daimi.au.dk/~barnie/RealLib/.
– dbarbosa Feb 17 '13 at 08:49