9
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ If reals are represented by programs computing a given bit, or programs computing rational approximations, or any similar kind of programs, then the only decidable sets of reals are the trivial ones (i.e., those that contain either all computable reals or no computable reals), by Rice’s theorem. $\endgroup$ – Emil Jeřábek Mar 2 '12 at 16:32
  • 1
    $\begingroup$ How is that implication shown? $\:$ $\endgroup$ – user6973 Mar 3 '12 at 8:24
8
$\begingroup$

Kristoffer's solution can be used to show that, assuming reals are represented 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 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 the set $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ of rational numbers translated by a non-computable number $\alpha$. Exercise: is $S$ decidable?

$\endgroup$
  • $\begingroup$ Thanks for your reply. Just a clarification, does the theorem say that if the set S has at least one limit point outside S, then deciding whether an element x is in S undecidable ? Then, I am a bit confused about the closed interval in the examples. $\endgroup$ – ipsofacto Mar 2 '12 at 12:13
  • $\begingroup$ The closed interval follows by the dual theorem in which you take a sequence outside $S$ whose limit is in $S$. $\endgroup$ – Andrej Bauer Mar 2 '12 at 18:11
  • $\begingroup$ What does it mean for $x$ to be "outside $S$ computably" (as opposed to "outside $S\hspace{.01 in}$")$\:$? $\;\;$ $\endgroup$ – user6973 Mar 2 '12 at 20:02
  • $\begingroup$ That was a typo. I fidex it, thanks for noticing. Otherwise, "$x$ is computably outside $S$" might mean something like "for every $y \in S$ we may compute a positive rational $q$ such that $d(x,y) > q$", i.e., the statement "$\forall y \in S . \exists q \in \mathbb{Q} . 0 < q < d(x,y)$" is realized. But if you believe in Markov principle, then you can reconstruct such a map by just knowing that $x$ is not in $S$, so in this case there is no difference between "outside $S$ and "computably outside $S$". $\endgroup$ – Andrej Bauer Mar 3 '12 at 6:52
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The set of transcendentals is not open in $\mathbf R$ (in particular, it is dense and codense in $\mathbf R$. Hence it is undecidable.

$\endgroup$
  • 4
    $\begingroup$ The set of computable real numbers is not open in $\mathbf{R}$ (in particular, it is dense and codense in $\mathbf{R}$), but it is decidable. $\:$ $\endgroup$ – user6973 Mar 2 '12 at 19:59
  • 1
    $\begingroup$ Ricky, this is not true. Given an oracle for a real number, you cannot determine if it is computable or not. $\endgroup$ – David Harris Mar 3 '12 at 23:06
  • 1
    $\begingroup$ The set I gave is decidable, by the algorithm that always answers "Yes". $\:$ Your second sentence shows that the set I gave is not type-two decidable. $\;\;$ $\endgroup$ – user6973 Mar 3 '12 at 23:20
  • $\begingroup$ @Ricky Demer: The set of computable real numbers is undecidable in two senses: (1) given an arbitrary index $e \in \mathbb{N}$, decide whether $e$ is the index of a Turing machine that computes a computable real. (2) given an arbitrary quickly-converging Cauchy sequence, determine whether it is a computable sequence. There is no common sense in which the set of computable real numbers is decidable. $\endgroup$ – Carl Mummert Mar 14 '12 at 21:17
  • $\begingroup$ @Carl: There is an algorithm to given an index $\: e\in \mathbb{N} \:$ that is the index of a Turing machine that computes a computable real, decide whether $e$ is the index of a Turing machine that computes $\hspace{.1 in}$ a computable real. $\;\;$ This is the only interesting sense of decidability of sets of reals, because $\hspace{.2 in}$ your (1) is satisfied exactly by sets with no computable reals $\hspace{2.2 in}$ and your (2) is satisfied exactly by $\: \{\} \:$ and $\mathbf{R}$. $\;\;\;$ $\endgroup$ – user6973 Mar 17 '12 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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