Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help.
My question is whether it is known that deciding whether a number is transcendental is undecidable.
Possibly, one assumes as input, say a program that returns the i^th bit of the number. Thanks in advance for any pointers.
The subset of transcedental numbers is not decidable. We assume here that reals are represented in a standard way, so that we can compute limits of sequences of reals which are computably Cauchy.
Recall that a sequence $(a_n)_n$ is computably Cauchy if there is a computable map $f$ such that, given any $k$ we have $|a_{m} - a_{n}| < 2^{-k}$ for all $m, n \geq f(k)$. The standard representations of reals are like that, for example the one where a real is represented by a machine that computes an arbitrarily good rational approximation. (We can also speak in terms of computing digits, but then we have to allow negative digits. This is a well known issue in computability theory of the reals.)
Theorem: Suppose $S \subseteq \mathbb{R}$ is a subset such that there exists a computable sequence $(a_n)_n$ which is computably Cauchy and its limit $x = \lim_n a_n$ is outside $S$. Then the question "is a real number $x$ an element of $S$" is undecidable.
Proof. Suppose $S$ were decidable. Given any Turing machine $T$, consider the sequence $b_n$ defined as $$b_n = \begin{cases} a_n & \text{if $T$ has not halted in the first $n$ steps,}\\\\ a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.} \end{cases}$$ It is easy to check that $b_n$ is computably Cauchy, therefore we can compute its limit $y = \lim_n b_n$. Now we have $y \in S$ iff $T$ halts, so we can solve the Halting Problem. QED.
There is a dual theorem in which we assume the sequence is outside $S$ but its limit is in $S$.
Examples of sets $S$ satisfying these conditions are: an open interval, a closed interval, the negative numbers, the singleton $\lbrace 0 \rbrace$, rational numbers, irrational numbers, transcedental numbers, algebraic numbers, etc.
A set which does not satisfy the conditions of the theorem is $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ of rational numbers translated by a non-computable number $\alpha$. Exercise: is $S$ decidable?
Given a Turing machine $M$, define a Turing machine $M'$ representing a number as follows: On input $i$ run $M$ for $i$ steps on the empty input. If $M$ halted, output $0$. Otherwise output the $i$th bit of $\pi$.
The set of transcendentals is not open in $\mathbf R$ (in particular, it is dense and codense in $\mathbf R$. Hence it is undecidable.
