<p>I tend to think this is undecidable:</p>

<p>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.</p>

<p>Deciding if this function computes a rational number is equivalent to the halting problem.</p>

CC BY-SA 3.0
2013-02-19T00:31:45.200Z
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).
dbarbosa
CC BY-SA 3.0
2013-02-19T06:09:42.987Z
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.
Kaveh
CC BY-SA 3.0
2013-02-19T06:49:49.993Z
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.
Shaull
CC BY-SA 4.0
2024-02-02T14:09:12.967Z
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.
Neal Young
CC BY-SA 4.0
2024-02-02T18:57:28.720Z
@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.
Shaull
CC BY-SA 4.0
2024-02-02T19:20:10.357Z
Ah, now I think I see what you have in mind.  I didn't understand the reduction from reading your second paragraph. First, I thought that "*Let $x$ be...*" was introducing the input to the reduction, then I thought that $M$ must be the TM computing $f_x$ (as I interpreted the "$\epsilon$" there as the $\epsilon$ input to $f_x$, i.e., a number).  Then I thought that "it" in "*it stops computing $x$*" referred to $M$, and misinterpreted "stops computing $x$."  So I was quite confused.  Thanks for the clarifications.
Neal Young
CC BY-SA 3.0
2013-02-17T09:02:32.843Z
2013-02-17T09:02:32.843Z
Shaull
<p>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).</p>

<p>Computable functions are continuous. IsRational and IsInteger are not continuous and therefore not computable.</p>

<p>IsInteger is <em>semi</em>-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).</p>

CC BY-SA 3.0
2013-02-18T23:41:02.207Z
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?
dbarbosa
CC BY-SA 3.0
2013-02-19T07:36:04.630Z
"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 (http://www.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.
Max
CC BY-SA 3.0
2013-02-18T08:46:14.093Z
2013-02-18T08:46:14.093Z
Max
<p>It is undecidable whether a given computable number is <strong>equal to zero</strong>.</p>

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

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

CC BY-SA 3.0
2013-02-19T06:19:28.630Z
2013-02-19T06:19:28.630Z
Jeffε
<p>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.</p>

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

<p>$$
F(r) = 
\begin{cases} 
YES &amp; r\in \mathbb{Q}\\
NO &amp; o.w.
\end{cases}
$$</p>

<p>is computable. </p>

<p>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$.</p>

<p>Then your function is not continuous and is therefore not computable.</p>

<p>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.</p>

<p>The proof that any computable function needs to be continuous is similar.</p>

CC BY-SA 3.0
2013-02-19T06:26:39.007Z
2013-02-19T06:26:39.007Z
Kaveh
<p>As a (hopefully fun) exercise, we pin down the complexities of the two problems more precisely.  Let <span class="math-container">$x$</span> be a given computable number (encoded as defined in the post).</p>
<p><strong>Lemma 1.</strong> <em>The problem of determining whether <span class="math-container">$x$</span> is an integer is complete for <span class="math-container">$\Pi_1$</span>.</em></p>
<p><strong>Lemma 2.</strong> <em>The problem of determining whether <span class="math-container">$x$</span> is rational is complete for <span class="math-container">$\Sigma_2$</span>.</em></p>
<p>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.)</p>
<p>[<em>EDIT: An <a href="https://cstheory.stackexchange.com/a/53879/8237">answer to a related post</a> shows that determining whether <span class="math-container">$x$</span> is transcendental is complete for <span class="math-container">$\Pi$</span>.</em>]</p>
<p>This answer can be viewed as a detailed elaboration of <a href="https://cstheory.stackexchange.com/a/16515/8237">Saul's previous answer</a>.</p>
<p>Here is how a number <span class="math-container">$x$</span> is encoded, according to the post:</p>
<blockquote>
<p>A computable number <span class="math-container">$x$</span> is given by a function <span class="math-container">$f_x(\epsilon)$</span> that can return a rational approximation of <span class="math-container">$x$</span> with precision <span class="math-container">$\epsilon$</span>: <span class="math-container">$|x - f_x(\epsilon)| \leq \epsilon$</span>, for any <span class="math-container">$\epsilon &gt; 0$</span>. Given such function, is it possible to test if <span class="math-container">$x \in \mathbb{Q}$</span> or <span class="math-container">$x \in \mathbb{Z}$</span>?</p>
</blockquote>
<p>Specifically, we assume that the function <span class="math-container">$f_x$</span> is encoded by (the encoding of) a TM <span class="math-container">$M_x$</span> that computes <span class="math-container">$f_x(\epsilon)$</span> given any <span class="math-container">$\epsilon$</span>.</p>
<p>Let <span class="math-container">$Z$</span> denote the problem of determining whether a given computable number <span class="math-container">$x$</span> is an integer (that is, in <span class="math-container">$\mathbb Z$</span>).
Let <span class="math-container">$Q$</span> denote the problem of determining whether a given <span class="math-container">$x$</span> is rational (that is, in <span class="math-container">$\mathbb Q$</span>).
Let <span class="math-container">$\mathbb Q_+$</span> denote the positive rationals.</p>
<h4>First upper bound: <span class="math-container">$Q$</span> is in <span class="math-container">$\Sigma_2$</span></h4>
<p>To see that <span class="math-container">$Q$</span> is in <span class="math-container">$\Sigma_2$</span>, note that, given an <span class="math-container">$x$</span> via a TM <span class="math-container">$M_x$</span> computing <span class="math-container">$x$</span> as described above, <span class="math-container">$x$</span> is rational if and only if
<span class="math-container">$$(\exists q\in \mathbb Q) ~ (\forall \epsilon \in \mathbb Q_+) ~|M_x(\epsilon) - q| \le \epsilon.$$</span>
Further, given <span class="math-container">$\epsilon$</span>, <span class="math-container">$M_x$</span>, and <span class="math-container">$q$</span>, the condition
<span class="math-container">$|M_x(\epsilon) - q| \le \epsilon$</span>
is computable.  By definition of <span class="math-container">$\Sigma_2$</span>, this shows <span class="math-container">$Q\in \Sigma_2$</span>.</p>
<h4>Second upper bound: <span class="math-container">$Z$</span> is in <span class="math-container">$\Pi_1$</span></h4>
<p>By similar reasoning, <span class="math-container">$Z$</span> is in <span class="math-container">$\Sigma_2$</span>.  But in fact something stronger holds:  <span class="math-container">$Z$</span> is in <span class="math-container">$\Pi_1$</span>.  To see this note that <span class="math-container">$x$</span> must be at distance at most <span class="math-container">$1/10$</span> from <span class="math-container">$M_x(1/10)$</span>,
so, if <span class="math-container">$x$</span> is an integer,
it has to equal <span class="math-container">$\lfloor M_x(1/10) + 1/2 \rfloor$</span>.
Hence, <span class="math-container">$x$</span> is an integer if and only ifn
<span class="math-container">$$(\forall \epsilon \in \mathbb Q_+) ~|M_x(\epsilon) - \lfloor M_x(1/10) + 1/2 \rfloor| \le \epsilon.$$</span>
The condition <span class="math-container">$|M_x(\epsilon) - \lfloor M_x(1/10) + 1/2 \rfloor| \le \epsilon$</span> is computable.
So <span class="math-container">$Z\in \Pi_1$</span>.</p>
<h3>Hardness results</h3>
<p>Next we sketch proofs that the two &quot;upper bounds&quot; above are tight.
That is, each problem is hard (under many-one reductions)
for its respective class.</p>
<h4>First hardness result: <span class="math-container">$Q$</span> is <span class="math-container">$\Sigma_2$</span>-hard</h4>
<p>We give a reduction via the following intermediate problem:</p>
<blockquote>
<p><strong>Problem <span class="math-container">$F$</span> (for &quot;finite&quot;).</strong> <em>Given (the encoding of) a TM <span class="math-container">$M$</span> that enumerates a sequence of bits, is <span class="math-container">$\sum_i M_i$</span> (where <span class="math-container">$M_i$</span> is the <span class="math-container">$i$</span>th bit enumerated by <span class="math-container">$M$</span>) finite?</em></p>
</blockquote>
<p><strong>Claim 1.</strong> <em><span class="math-container">$F$</span> is <span class="math-container">$\Sigma_2$</span>-hard</em></p>
<hr />
<p>We prove the claim by reduction from the following problem which is well known (and easily shown) to be <span class="math-container">$\Sigma_2$</span>-complete:</p>
<blockquote>
<p><em>Given a TM <span class="math-container">$M$</span>, is there an input on which <span class="math-container">$M$</span> runs forever?</em></p>
</blockquote>
<p>Given such an <span class="math-container">$M$</span>, the reduction outputs the following TM <span class="math-container">$M'$</span>:</p>
<p>TM <span class="math-container">$M'$</span>:</p>
<ol>
<li>for each input <span class="math-container">$y_1, y_2, \ldots$</span> to <span class="math-container">$M$</span> (in any order) do:</li>
<li><span class="math-container">$~~~$</span> output 1</li>
<li><span class="math-container">$~~~$</span> simulate <span class="math-container">$M(y_i)$</span>, outputting a 0 at each step of the simulation</li>
<li><span class="math-container">$~~~~~$</span> (if <span class="math-container">$M(y_i)$</span> halts, stop and move on to the next input <span class="math-container">$y_{i+1}$</span>)</li>
</ol>
<p>If <span class="math-container">$M$</span> halts on all inputs, then <span class="math-container">$\sum_i M'_i$</span> is infinite.
On the other hand, if <span class="math-container">$M$</span> runs forever on some input,
then, when the outer loop runs for the first such input, say <span class="math-container">$y_f$</span>,
the inner loop never terminates,
so <span class="math-container">$\sum_i M'_i = f &lt; \infty$</span>.
Hence, the reduction is correct, proving the claim.</p>
<hr />
<p>To prove that <span class="math-container">$Q$</span> is <span class="math-container">$\Sigma_2$</span>-hard, we will reduce <span class="math-container">$F$</span> to <span class="math-container">$Q$</span>.</p>
<p>Let <span class="math-container">$M$</span> be any TM that enumerates a bit sequence <span class="math-container">$M_1, M_2, \ldots$</span>.  Define
<span class="math-container">$$x(M) = \displaystyle\sum_{i=1}^\infty \frac{M_i}{i!}.$$</span></p>
<p><strong>Claim 2.</strong> <em><span class="math-container">$x(M)$</span> is rational iff <span class="math-container">$\langle M \rangle \in F$</span> (i.e., <span class="math-container">$\sum_i M_i &lt; \infty$</span>).</em></p>
<p>Indeed, if <span class="math-container">$\sum_i M_i &lt; \infty$</span>, then <span class="math-container">$x(M)$</span> is the sum of finitely many rationals, so is rational.
Conversely, if <span class="math-container">$\sum_i M_i = \infty$</span>, then for any integer <span class="math-container">$m$</span> we have
<span class="math-container">$$m! x(M) = \sum_{i=1}^\infty M_i m!/i!,$$</span>
and the first <span class="math-container">$m$</span> terms in the sum are integers,
while the sum of the remaining terms is strictly positive but at most <span class="math-container">$\sum_{i&gt;m} 1/m^{i-m} &lt; 1$</span>.
So <span class="math-container">$m! x(M)$</span> is not an integer for any integer <span class="math-container">$m$</span>.
So <span class="math-container">$x(M)$</span> is not rational.
This proves Claim 2.</p>
<p>Given <span class="math-container">$M$</span> as described above,
the reduction (from <span class="math-container">$F$</span> to <span class="math-container">$Q$</span>)
outputs the following TM <span class="math-container">$M'$</span>:</p>
<p>TM <span class="math-container">$M'$</span> on input <span class="math-container">$\epsilon&gt;0$</span>:</p>
<ol>
<li>return <span class="math-container">$\sum_{i=1}^{m(\epsilon)} M_i / i!$</span>, where <span class="math-container">$m(\epsilon) = \lceil 2/\epsilon\rceil$</span></li>
</ol>
<p>Note that <span class="math-container">$M'$</span> computes (by OP's definition) <span class="math-container">$x(M)$</span>.
(Indeed, <span class="math-container">$\sum_{n=m(\epsilon)}^{\infty} 1/n! &lt; \epsilon$</span>,
so the sum returned by <span class="math-container">$M'(\epsilon)$</span> is within <span class="math-container">$\epsilon$</span> of <span class="math-container">$x(M)$</span>.)</p>
<p>By Claim 2, then, <span class="math-container">$\langle M' \rangle \in Q$</span> iff <span class="math-container">$\langle M \rangle \in F$</span>.
That is, the reduction is correct.
This shows that <span class="math-container">$Q$</span> is also <span class="math-container">$\Sigma_2$</span>-hard.
This completes the proof of Lemma 2.</p>
<h4>Second hardness result: <span class="math-container">$Z$</span> is <span class="math-container">$\Pi_1$</span>-hard</h4>
<p>The proof is by reduction from the complement of the halting problem.  Given a TM <span class="math-container">$M$</span>, the reduction outputs a computable <span class="math-container">$x$</span> such that <span class="math-container">$x$</span> is an integer iff <span class="math-container">$M$</span> runs forever on empty input.</p>
<p>The machine <span class="math-container">$M_x$</span> that computes <span class="math-container">$x$</span> does the following:</p>
<p>TM <span class="math-container">$M_x$</span> on input <span class="math-container">$\epsilon$</span>:</p>
<ol>
<li>simulate <span class="math-container">$M()$</span> for <span class="math-container">$1/\epsilon$</span> steps</li>
<li>if <span class="math-container">$M()$</span> does not halt within <span class="math-container">$1/\epsilon$</span> steps: output <span class="math-container">$0$</span></li>
<li>else: output <span class="math-container">$1/(h+1)$</span>, where <span class="math-container">$M()$</span> halts in <span class="math-container">$h \le 1/\epsilon$</span> steps</li>
</ol>
<p>If <span class="math-container">$M()$</span> never halts, then <span class="math-container">$M_x$</span> always outputs 0, and <span class="math-container">$x=0$</span> (which is an integer).
If <span class="math-container">$M()$</span> halts in some <span class="math-container">$h$</span> steps, then <span class="math-container">$M_x$</span> outputs <span class="math-container">$0$</span> for <span class="math-container">$\epsilon \ge 1/h$</span>, and outputs <span class="math-container">$1/(h+1)$</span> for all smaller <span class="math-container">$\epsilon$</span>.
In this case <span class="math-container">$x=1/(h+1)$</span> (which is not an integer).</p>
<p>We leave it as an exercise to verify that <span class="math-container">$|M_x(\epsilon) - x| \le \epsilon$</span> for all <span class="math-container">$\epsilon\ge 0$</span>, as required.</p>
<p>This completes the reduction and the proof of Lemma 1.</p>
<hr />
<p><strong>Note on a technical subtlety.</strong> A-priori, the problems <span class="math-container">$Q$</span> and <span class="math-container">$Z$</span> are <em>promise</em> problems.  The input is encoded as a TM <span class="math-container">$M_x$</span> that is <em>promised</em> to encode some <span class="math-container">$x$</span> via a function <span class="math-container">$f_x$</span>.
To be complete, we should specify what decision should be reached in the event that the given TM does not properly encode such an <span class="math-container">$x$</span>.</p>
<p>Given that <span class="math-container">$M$</span> computes a function (with rational input and output), <span class="math-container">$M$</span> will properly encode some <span class="math-container">$x$</span> if and only if</p>
<ol>
<li><span class="math-container">$M$</span> halts on all inputs, and</li>
<li><span class="math-container">$|M_x(\epsilon_1) - M_x(\epsilon_2)| \le \epsilon_1 + \epsilon_2$</span> for all inputs <span class="math-container">$\epsilon_1$</span> and <span class="math-container">$\epsilon_2$</span>.</li>
</ol>
<p>Deciding Condition 1 (whether <span class="math-container">$M$</span> halts on all inputs)
is <span class="math-container">$\Pi_2$</span>-complete,
so requiring the decider of <span class="math-container">$Q$</span> or <span class="math-container">$Z$</span> 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 <span class="math-container">$M$</span> (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.</p>
<p>The remaining question is then whether the Condition 2 above
holds for all <span class="math-container">$\epsilon_1, \epsilon_2$</span>.
Determining this for an arbitrary TM can be done in <span class="math-container">$\Pi_1$</span>.
So simply requiring the decider to determine whether the condition is met should not increase the complexity of either problem.</p>

CC BY-SA 4.0
2024-02-02T17:34:01.183Z
2024-02-05T20:09:20.943Z
2024-02-05T20:09:20.943Z
Neal Young
<p>It is easy to get confused about what it means to &quot;represent&quot; or &quot;implement&quot; a real number. In fact, we are witnessing a discussion in the comments where the representation is contentious. So let me address this first.</p>
<h3>How do we know that an implementation is correct?</h3>
<p>The theory which explains how to represent things in a computer is <em>realizability</em>. The basic idea is that, given a set <span class="math-container">$X$</span>, we pick a datatype <span class="math-container">$\tau$</span> and to every <span class="math-container">$x \in X$</span> a set of values of type <span class="math-container">$\tau$</span> which <em>realize</em> it. We write <span class="math-container">$v \vdash x \in X$</span> when <span class="math-container">$v$</span> is a value that realizes <span class="math-container">$x$</span>. For example (I shall use Haskell for no good reason), a sensible implementation of <span class="math-container">$\mathbb{N}$</span> might be the datatype <code>Integer</code> where <span class="math-container">$v \vdash k \in \mathbb{N}$</span> when <span class="math-container">$v$</span> evaluates to the numeral <span class="math-container">$\overline{k}$</span> (thus in particular <code>-42</code> does not represent a natural number, and neither does a diverging program). But some joker could walk by and suggest that we use <code>Bool</code> to represent natural numbers with <span class="math-container">$\mathtt{True} \vdash 42 \in \mathbb{N}$</span> and <span class="math-container">$\mathtt{False} \vdash n \in \mathbb{N}$</span> for <span class="math-container">$n \neq 42$</span>. Why is this incorrect? We need a <em>criterion</em>.</p>
<p>In the case of &quot;joker numbers&quot; the easy observation is that addition cannot be implemented. Suppose I tell you I have two numbers, both represented by <span class="math-container">$\mathtt{False}$</span>. 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 &quot;essential part of what natural numbers are&quot;, this is unacceptable. In other words, implementation is not about sets, but about <em>structures</em>, 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:</p>
<blockquote>
<p><strong>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.</strong></p>
</blockquote>
<p>If you do not abide by this principle, then you have to suggest an alternative <em>mathematical</em> criterion of correctness. I do not know of one.</p>
<h3>Example: representation of natural numbers</h3>
<p>For natural numbers the relevant structure is described by Peano axioms, and the crucial axiom that has to be implemented is induction (but also <span class="math-container">$0$</span>, successor, <span class="math-container">$+$</span> and <span class="math-container">$\times$</span>). We can compute, using realizability, what the implementation of induction does. It turns out to be a map (where <code>nat</code> is the yet unknown datatype which represents natural numbers)</p>
<blockquote>
<p><code>induction : 'a -&gt; (nat -&gt; 'a -&gt; 'a) -&gt; 'nat -&gt; 'a</code></p>
</blockquote>
<p>satisfying <code>induction x f zero = x</code> and <code>induction x f (succ n) = f n (induction x f n)</code>. 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 <span class="math-container">$X \mapsto 1 + X$</span>.</p>
<h3>Correct implementation of real numbers</h3>
<p>Let us turn attention to the real numbers and the question at hand. The first question to ask is &quot;what is the relevant structure of the real numbers?&quot; The answer is: <em>Archimedean Cauchy complete ordered field</em>. This is the established meaning of &quot;real numbers&quot;. 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 &quot;I do not care about implementing addition&quot;, or &quot;I do not care about the order&quot;. If you do that, you must not call it &quot;real numbers&quot;, but something like &quot;real numbers where we forget the linear order&quot;.</p>
<p>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:</p>
<ul>
<li>the <em>Archimedean</em> axiom is about computing <em>rational</em> approximations of reals</li>
<li>the field structure gives the usual arithmetical operations</li>
<li>the linear order gives us a <em>semidecidable</em> procedure for testing <span class="math-container">$x &lt; y$</span></li>
<li>the <em>Cauchy completeness</em> gives us a function <code>lim : (nat -&gt; real) -&gt; real</code> which takes a (representation of) <em>rapid</em> Cauchy sequence and returns its limit. (A sequence <span class="math-container">$(x_n)_n$</span> is rapid if <span class="math-container">$|x_n - x_m| \leq 2^{-\min(n,m)}$</span> for all <span class="math-container">$m, n$</span>.)</li>
</ul>
<p>What we do <em>not</em> get is a test function for equality. There is nothing in the axioms for reals which asks that <span class="math-container">$=$</span> be decidable. (In contrast, the Peano axioms imply that the natural numbers are decidable, and you can prove that by implementing <code>eq : nat -&gt; nat -&gt; Bool</code> using only <code>induction</code> as a fun exercise).</p>
<p>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 <em>signed</em> 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.</p>
<h3>The Tsuyoshi representation also implements something, but not <span class="math-container">$\mathbb{R}$</span></h3>
<p>Let us consider the following representation of reals: a real <span class="math-container">$x$</span> is represented by a pair <span class="math-container">$(q,b)$</span> where <span class="math-container">$(q_n)_n$</span> is a rapid Cauchy sequence converging to <span class="math-container">$x$</span> and <span class="math-container">$b$</span> is a Boolean indicating whether <span class="math-container">$x$</span> 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 <em>not</em> a representation of the reals. But it still does represent something, namely the subset of the reals <span class="math-container">$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$</span>. 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, <span class="math-container">$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$</span> is a <em>not</em> equal to <span class="math-container">$\mathbb{R}$</span>, unless you believe in excluded middle, which cannot be implemented and is therefore quite irrelevant for this discussion. We are of <em>forced by computers</em> to do things intuitionistically.</p>
<h3>We cannot test whether a real is an integer</h3>
<p>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.)</p>
<p><strong>Theorem:</strong> Testing whether a real is an integer is not decidable.</p>
<p><em>Proof.</em> 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 <span class="math-container">$(x_n)_n$</span> of non-integers which converges to an integer. This is easy, just take <span class="math-container">$x_n = 2^{-n}$</span>. Next, solve the Halting problem as follows. Given a Turing machine <span class="math-container">$T$</span>, define a new sequence <span class="math-container">$(y_n)_n$</span> by
<span class="math-container">$$y_n = \begin{cases}
x_n &amp; \text{if $T$ has not stopped within $n$ steps}\\
x_m &amp; \text{if $T$ stopped in step $m$ and $m \leq n$}
\end{cases}$$</span>
That is, the new sequence looks like the sequence <span class="math-container">$(x_n)_n$</span> as long as <span class="math-container">$T$</span> runs, but then it gets &quot;stuck&quot; at <span class="math-container">$x_m$</span> if <span class="math-container">$T$</span> halts in step <span class="math-container">$m$</span>. Very importantly, the new sequence is also a rapid Cauchy sequence (and we can prove this without knowing whether <span class="math-container">$T$</span> halts). Therefore, we can compute its limit <span class="math-container">$z = \lim_n y_n$</span>, because our representation of reals is correct. Test whether <span class="math-container">$z$</span> is an integer. If it is, then it must be <span class="math-container">$0$</span> and this only happens if <span class="math-container">$T$</span> runs forever. Otherwise, <span class="math-container">$z$</span> is not an integer, so <span class="math-container">$T$</span> must have stopped. QED.</p>
<p>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).</p>
<p>Sometimes people get confused about all this testing business. They think we have proved that we can <em>never</em> 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 <em>particular</em> real we come up with, <span class="math-container">$\sin 11$</span>, <span class="math-container">$88 \ln 89$</span>, <span class="math-container">$e^{\pi \sqrt{163}}$</span>, etc., we can perfectly well tell whether they are integers. Precisely, <em>we</em> can tell because <em>we</em> 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 <em>not</em> mean a symbolic expression describing the sequence, but a black box which outputs the <span class="math-container">$n$</span>-th term on input <span class="math-container">$n$</span>) then we will be just as helpless as machines.</p>
<h3>The moral of the story</h3>
<p><em>It makes no sense to talk about implementation of a set unless we know what sort of operations we want to perform on it.</em></p>

CC BY-SA 3.0
2013-02-19T07:32:03.113Z
If your answers were people, I would marry them. All of them.
Vijay D
CC BY-SA 3.0
2013-02-19T07:40:45.460Z
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.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T14:22:10.517Z
Where can I read more about this? I guess this is "computable analysis"?
usul
CC BY-SA 3.0
2013-02-19T15:31:48.780Z
@AndrejBauer: in my answer I refer to the theorem "computable => continuous" without citation. I guess that you might know the originator of this insight?
Max
CC BY-SA 3.0
2013-02-19T15:40:45.520Z
An alternative viewpoint is to ask which tuples of operations are computable on the representations of sets. In this viewpoint we can make IsInteger and IsRational computable (using flags), but not IsInteger and addition.
Max
CC BY-SA 3.0
2013-02-19T17:10:35.277Z
@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".
Andrej Bauer
CC BY-SA 3.0
2013-02-19T17:12:12.233Z
@Max: if you have a structure with a bunch of operations, and then you take a subset of the operations, that is called a *reduct*. So sure, we can think about which reducts are computable, but that is not really an alternative viewpoint. You are still thinking about *structures*.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T17:13:15.010Z
@usul: Klaus Weihrauch "Introduction to Computable Analysis". Also my PhD thesis, but that might be hard to digest. I need to write a textbook.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T18:20:38.657Z
Andrej, I know that I have asked this before on your blog a few years ago and you have answered it there and I think I understand what you are saying. However I kind of feel that this is not satisfying. Let me say why I feel so: 1. we are kind of assuming that equality is not decidable from the beginning, and then we select such a representation. Finally unsurprisingly we end up with an uncomputability result. It seems that we kind of assumed what we were going to prove. 2. If I understand you correctly, you are saying we don't represent sets alone but structures. However this doesn't seem to
Kaveh
CC BY-SA 3.0
2013-02-19T18:20:55.193Z
[cont.] be clearly the case. You are using this to rule out some representations like the one mentioned by Tsuyoshi since other operations are not computable. However I don't see why by default one would require such operations always. When we say real numbers we don't really mean the field structure of real numbers or ordered field structure of real numbers or ... we simply mean real numbers. The operations come later. Are these operations essential to call something a real number? I don't see why. If you say that we *define* a real number a special kind of sequences of rationals so we
Kaveh
CC BY-SA 3.0
2013-02-19T18:22:52.417Z
_I need to write a textbook_ — (Google google google).  Okay, good, you have tenure.  Go for it!
Jeffε
CC BY-SA 3.0
2013-02-19T18:24:52.453Z
[cont.] should at least be able to compute arbitrary elements of that sequence I feel that is natural (and more generally whenever we define a new kind of object as quotient classes of countable infinite sequences of some other objects). However I don't see why we *must* assume anything more like some operations being computable from the beginning. You seem to imply this is the only way *we know* how to distinguish reasonable representations from other representations, however it doesn't mean that it is the only way or it is required. At the end, we have to state what we consider to be
Kaveh
CC BY-SA 3.0
2013-02-19T18:28:47.690Z
[cont.] essential for a real number object.
Kaveh
CC BY-SA 3.0
2013-02-19T19:58:20.697Z
I have a similar sentiment to that of Kaveh: why should < be semidecidable and = not? Or would this just be another structure (for which we could show that there is no possible "implementation"). But why does your version get to be called "the reals"?
cody
CC BY-SA 3.0
2013-02-19T20:18:03.860Z
@Andrej, the issue has been bothering me for a considerable time and I haven't been able to find an answer which is satisfying. I posted a follow-up question [here](http://cstheory.stackexchange.com/questions/16556/what-is-a-reasonable-representation). I would appreciate if you can have a look at it. It is possible that I have some basic misunderstanding about the issue that doesn't let me correctly understand your answer, please let me know if that is the case.
Kaveh
CC BY-SA 3.0
2013-02-19T20:34:44.470Z
“It makes no sense to talk about implementation of a set unless we know what sort of operations we want to perform on it.”  Absolutely.  And that is exactly why the silly encoding (q,b) was valid as long as revision 1 of the question was concerned: the question did not define any set of operations which the OP wanted to perform, except for `isInteger` and `isRational`.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-19T22:03:09.437Z
@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.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T22:07:33.790Z
Whoa, a barrage of comments, I am not sure I can cope, but thanks for expressing so much interest. It might be better to spawn new questions and I'll try to answer them, and others get to contribute as well.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T22:10:31.797Z
Let me address semidecidability of $<$ first. The axioms for reals say nothing about decidability or semidecidability of $=$ and $<$. They say things like "$<$ is a irreflexive, transitive, preserved by addition, etc." They *imply* that $<$ is semidecidable. The axioms for reals do *not* imply that $=$ is decidable, but they do imply that $\neq$ is semidecidable (I am skipping over some details ).
Andrej Bauer
CC BY-SA 3.0
2013-02-19T22:13:33.590Z
@Kaveh: a bare set without a structure is the same thing as a cardinal number (in classical math). Yes, it is most definitely *essential* that the reals form a Cauchy complete Archimedean ordered field. That's why the reals are useful, because this is the structure that is important to us. If some other set had the same structure it would be equally good. So it doesn't matter which set it is, but what structure we equip it with. Let me try this way: what is important about a class in Java? Which objects it has, or which methods? Only the methods matter (assume no direct access to components.)
Andrej Bauer
CC BY-SA 3.0
2013-02-19T22:27:11.190Z
(1) Where in the question is the word “real” used?  (2) The definition of real numbers is standard, but there is no “standard” set of operations on real numbers.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-19T23:17:43.773Z
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 .....).
Andrej Bauer
CC BY-SA 3.0
2015-06-12T04:54:39.550Z
"(and I do not mean a symbolic expression describing the sequence, but a black box which outputs the n-th term on input n) " However, what if we are given an arbitrary _computer program_ which outputs some term of the sequence converging to the real? Then we don't just have a black box.
The_Sympathizer
CC BY-SA 4.0
2022-07-04T04:09:21.257Z
@Andrej is your definition of rapid Cauchy sequence missing a minus sign in the exponent of 2? I would expect $2^{-\min(n,m)}$...
David Roberts
CC BY-SA 4.0
2022-07-04T08:49:38.127Z
Yes, thank you. Fixed.
Andrej Bauer
CC BY-SA 4.0
2013-02-19T07:22:12.343Z
2022-07-04T08:49:24.583Z
2022-07-04T08:49:24.583Z
Andrej Bauer
<p>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 <code>isInteger</code> or <code>isRational</code>?</p>

<p>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.</p>

<p>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 &gt; 0$. Given such function, is it possible to test if $x \in \mathrm{Q}$ or $x \in \mathrm{Z}$?</p>

CC BY-SA 3.0
2013-02-17T05:32:40.040Z
How is the computable number given?
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-17T08:49:47.000Z
A computable number is a function that can give approximations to the number with arbitrarily good precision. Besides implementing the numbers, the library should provide ways of doing computation with these numbers.

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
CC BY-SA 3.0
2013-02-17T12:00:11.883Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-17T13:41:06.560Z
Similar question: http://cstheory.stackexchange.com/questions/10495/decidability-of-transcendental-numbers/10496#10496
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-02-18T20:30:39.670Z
I think it falls under Rice's theorem, so it is undecidable.
Denis
CC BY-SA 3.0
2013-02-18T23:46:05.303Z
@TsuyoshiIto performing computation using irrational numbers can result in an integer number, having a flag doesn't help. For example, take a irrational number $x$ and compute $sin^2(x) + cos^2(x)$. How do you know that this is an integer? If you see the two answers so far, they don't mention anything about the implementation.
dbarbosa
CC BY-SA 3.0
2013-02-18T23:55:03.753Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-19T00:21:19.163Z
Sorry @TsuyoshiIto, but that's exactly the question. Computation with computable numbers generate new computable numbers. Given any computable number, how can you test if it is rational or an integer?
If $x$ is a computable number, $sin^2(x) + cos^2(x)$ is also computable, so the algorithm should be able to answer this example.
dbarbosa
CC BY-SA 3.0
2013-02-19T00:23:32.047Z
Relevant information: $cos(x\pi) = 0$ iff $x$ is integer, so if you can test if a computable number is 1, you can test if a computable number is an integer.
Unfortunately you cannot test if a computable number is equal to 1.
dbarbosa
CC BY-SA 3.0
2013-02-19T00:31:12.150Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-19T00:41:33.310Z
The encoding of a number $x$ is a function $f_x(\epsilon)$ that returns a rational approximation of $x$ with precision $\epsilon$: $|f_x(\epsilon) - x| < \epsilon$.
I believe that's all one needs to know to answer this question. If this is not the case, feel free to answer for a given encoding, representation, or new assumptions or restrictions. I will be happy to read any answer. :)
I will edit the question adding this.
dbarbosa
CC BY-SA 3.0
2013-02-19T07:22:40.863Z
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.
Andrej Bauer
CC BY-SA 3.0
2013-02-19T17:48:18.673Z
@Kaveh Sure. Sorry for that, I didn't know about "cstheory" vs. "cs" on stackexchange.
dbarbosa
CC BY-SA 3.0
2013-02-19T18:54:13.370Z
It seems that the question is OK here, particularly after Andrej's answer.
Kaveh
<computability><computing-over-reals>
Is it possible to test if a computable number is rational or integer?
dbarbosa
# Is it possible to test if a computable number is rational or integer?

(Asked by: username_0 on 2013-02-17)

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}$?

**Tags:** computability, computing-over-reals

> **Comments:**
> **username_1**: How is the computable number given?  
> **username_0**: A computable number is a function that can give approximations to the number with arbitrarily good precision. Besides implementing the numbers, the library should provide ways of doing computation with these numbers.  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/.  
> **username_1**: 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.  
> **username_2**: Similar question: http://cstheory.stackexchange.com/questions/10495/decidability-of-transcendental-numbers/10496#10496  
> **username_3**: I think it falls under Rice's theorem, so it is undecidable.  
> **username_0**: @TsuyoshiIto performing computation using irrational numbers can result in an integer number, having a flag doesn't help. For example, take a irrational number $x$ and compute $sin^2(x) + cos^2(x)$. How do you know that this is an integer? If you see the two answers so far, they don't mention anything about the implementation.  
> **username_1**: (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.  
> **username_0**: Sorry @TsuyoshiIto, but that's exactly the question. Computation with computable numbers generate new computable numbers. Given any computable number, how can you test if it is rational or an integer? If $x$ is a computable number, $sin^2(x) + cos^2(x)$ is also computable, so the algorithm should be able to answer this example.  
> **username_0**: Relevant information: $cos(x\pi) = 0$ iff $x$ is integer, so if you can test if a computable number is 1, you can test if a computable number is an integer. Unfortunately you cannot test if a computable number is equal to 1.  
> **username_1**: 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.  
> **username_0**: The encoding of a number $x$ is a function $f_x(\epsilon)$ that returns a rational approximation of $x$ with precision $\epsilon$: $|f_x(\epsilon) - x| < \epsilon$. I believe that's all one needs to know to answer this question. If this is not the case, feel free to answer for a given encoding, representation, or new assumptions or restrictions. I will be happy to read any answer. :) I will edit the question adding this.  
> **username_4**: 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.  
> **username_0**: @username_5 Sure. Sorry for that, I didn't know about "cstheory" vs. "cs" on stackexchange.  
> **username_5**: It seems that the question is OK here, particularly after Andrej's answer.  

---

## 6 answers

### Answer by username_4 on 2013-02-19. Score: 44 | Accepted answer

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.*

> **Comments:**
> **username_10**: If your answers were people, I would marry them. All of them.  
> **username_4**: 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.  
> **username_11**: Where can I read more about this? I guess this is "computable analysis"?  
> **username_8**: @AndrejBauer: in my answer I refer to the theorem "computable => continuous" without citation. I guess that you might know the originator of this insight?  
> **username_8**: An alternative viewpoint is to ask which tuples of operations are computable on the representations of sets. In this viewpoint we can make IsInteger and IsRational computable (using flags), but not IsInteger and addition.  
> **username_4**: @username_8: 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".  
> **username_4**: @username_8: if you have a structure with a bunch of operations, and then you take a subset of the operations, that is called a *reduct*. So sure, we can think about which reducts are computable, but that is not really an alternative viewpoint. You are still thinking about *structures*.  
> **username_4**: @username_11: Klaus Weihrauch "Introduction to Computable Analysis". Also my PhD thesis, but that might be hard to digest. I need to write a textbook.  
> **username_5**: Andrej, I know that I have asked this before on your blog a few years ago and you have answered it there and I think I understand what you are saying. However I kind of feel that this is not satisfying. Let me say why I feel so: 1. we are kind of assuming that equality is not decidable from the beginning, and then we select such a representation. Finally unsurprisingly we end up with an uncomputability result. It seems that we kind of assumed what we were going to prove. 2. If I understand you correctly, you are saying we don't represent sets alone but structures. However this doesn't seem to  
> **username_5**: [cont.] be clearly the case. You are using this to rule out some representations like the one mentioned by Tsuyoshi since other operations are not computable. However I don't see why by default one would require such operations always. When we say real numbers we don't really mean the field structure of real numbers or ordered field structure of real numbers or ... we simply mean real numbers. The operations come later. Are these operations essential to call something a real number? I don't see why. If you say that we *define* a real number a special kind of sequences of rationals so we  
> **username_9**: _I need to write a textbook_ — (Google google google).  Okay, good, you have tenure.  Go for it!  
> **username_5**: [cont.] should at least be able to compute arbitrary elements of that sequence I feel that is natural (and more generally whenever we define a new kind of object as quotient classes of countable infinite sequences of some other objects). However I don't see why we *must* assume anything more like some operations being computable from the beginning. You seem to imply this is the only way *we know* how to distinguish reasonable representations from other representations, however it doesn't mean that it is the only way or it is required. At the end, we have to state what we consider to be  
> **username_5**: [cont.] essential for a real number object.  
> **username_12**: I have a similar sentiment to that of username_5: why should < be semidecidable and = not? Or would this just be another structure (for which we could show that there is no possible "implementation"). But why does your version get to be called "the reals"?  
> **username_5**: @Andrej, the issue has been bothering me for a considerable time and I haven't been able to find an answer which is satisfying. I posted a follow-up question [here](http://cstheory.stackexchange.com/questions/16556/what-is-a-reasonable-representation). I would appreciate if you can have a look at it. It is possible that I have some basic misunderstanding about the issue that doesn't let me correctly understand your answer, please let me know if that is the case.  
> **username_1**: “It makes no sense to talk about implementation of a set unless we know what sort of operations we want to perform on it.”  Absolutely.  And that is exactly why the silly encoding (q,b) was valid as long as revision 1 of the question was concerned: the question did not define any set of operations which the OP wanted to perform, except for `isInteger` and `isRational`.  
> **username_4**: @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.  
> **username_4**: Whoa, a barrage of comments, I am not sure I can cope, but thanks for expressing so much interest. It might be better to spawn new questions and I'll try to answer them, and others get to contribute as well.  
> **username_4**: Let me address semidecidability of $<$ first. The axioms for reals say nothing about decidability or semidecidability of $=$ and $<$. They say things like "$<$ is a irreflexive, transitive, preserved by addition, etc." They *imply* that $<$ is semidecidable. The axioms for reals do *not* imply that $=$ is decidable, but they do imply that $\neq$ is semidecidable (I am skipping over some details ).  
> **username_4**: @username_5: a bare set without a structure is the same thing as a cardinal number (in classical math). Yes, it is most definitely *essential* that the reals form a Cauchy complete Archimedean ordered field. That's why the reals are useful, because this is the structure that is important to us. If some other set had the same structure it would be equally good. So it doesn't matter which set it is, but what structure we equip it with. Let me try this way: what is important about a class in Java? Which objects it has, or which methods? Only the methods matter (assume no direct access to components.)  
> **username_1**: (1) Where in the question is the word “real” used?  (2) The definition of real numbers is standard, but there is no “standard” set of operations on real numbers.  
> **username_4**: 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 .....).  
> **username_13**: "(and I do not mean a symbolic expression describing the sequence, but a black box which outputs the n-th term on input n) " However, what if we are given an arbitrary _computer program_ which outputs some term of the sequence converging to the real? Then we don't just have a black box.  
> **username_14**: @Andrej is your definition of rapid Cauchy sequence missing a minus sign in the exponent of 2? I would expect $2^{-\min(n,m)}$...  
> **username_4**: Yes, thank you. Fixed.  

---

### Answer by username_6 on 2013-02-17. Score: 12

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.

> **Comments:**
> **username_0**: 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).  
> **username_5**: 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.  
> **username_6**: Indeed, my answer refers to representations as posted in the question, be them practical or not. @username_0 - 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.  
> **username_7**: 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.  
> **username_6**: @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.  
> **username_7**: Ah, now I think I see what you have in mind.  I didn't understand the reduction from reading your second paragraph. First, I thought that "*Let $x$ be...*" was introducing the input to the reduction, then I thought that $M$ must be the TM computing $f_x$ (as I interpreted the "$\epsilon$" there as the $\epsilon$ input to $f_x$, i.e., a number).  Then I thought that "it" in "*it stops computing $x$*" referred to $M$, and misinterpreted "stops computing $x$."  So I was quite confused.  Thanks for the clarifications.  

---

### Answer by username_8 on 2013-02-18. Score: 10

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).

> **Comments:**
> **username_0**: 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?  
> **username_8**: "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 (http://www.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.  

---

### Answer by username_9 on 2013-02-19. Score: 7

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.


---

### Answer by username_5 on 2013-02-19. Score: 2

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.


---

### Answer by username_7 on 2024-02-02. Score: 1

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](https://cstheory.stackexchange.com/a/53879/8237) 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](https://cstheory.stackexchange.com/a/16515/8237).

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.


---

