{transcendental numbers} \ {computable transcendental numbers}

Question

I know Chaitin's constant Ω is not computable (and therefore transcendental). Are there other specific, known noncomputable numbers? I am trying to understand what distinguishes a computable transcendental number, such as π, from a noncomputable transcendental number, such as Ω. Is there anything revealing that can be said about the set difference {transcendental numbers} \ {computable transcendental numbers}?

I ask this as a novice. I am re-visiting a wonderful book that sadly can no longer be updated by Victor Klee, in which he and Wagon pose this as an open problem: If an irrational number is real-time computable, is it then necessarily transcendent? [Problem 23]

Update (19Jun12). There is an illuminating discussion under the title "Why The Hartmanis-Stearns Conjecture Is Still Open" at the Lipton-Regan blog. The Hartmanis-Stearns Conjecture is the open problem mentioned above: If a number is real-time computable, it is either rational or transcendental. If true, this has what strikes me as a counterintuitive consequence: that algebraic irrationals like $\sqrt{3}$ are in some sense "more complicated" than transcendentals.

Answer 1

Note: Answer is pending update per attached comments.

The difference, stated informally, is that that the non-computable transcendentals in their k-base digit representation are entirely random and non compressible. A computable transcendental, such as e, can be represented by a finite algorithmic description, such as a series expansion, which is a form of compression. For the non-computable numbers no such shorter representation exist. Their shortest computational description is their own infinite digit sequence. You can read more about computational complexity here: http://en.wikipedia.org/wiki/Kolmogorov_complexity.

There is a wealth of similar numbers to the Ω class of numbers. In general it is "easy" to come up with new definitions for such numbers. These all belong to the countably infinite set of non-computable definable numbers.

To make matters worse, what is left are the non-definable (and therefore also non-computable) numbers. They are the numbers that cannot be described in any way what-so-ever, other than by just iterating through their infinite non-compressible digit sequence. The set of all non-definable numbers is uncountable.

Answer 2

Let me consider your question: Are there other specific, known non-computable numbers?

There are indeed numerous specific, known definable real numbers that we know are not computable. Many of these real numbers arise when considering various notions of definability in various stronger-than-computable systems, such as the arithmetic hierarchy, the projective hierarchy and other hierarchies of definability and complexity, some of which I describe in my answer to I. J. Kennedy's question Are some numbers more irrational than others? In my answer to Paul Budnik's question Is there a well-defined subset of the integers that cannot be defined as a property of a recursive process or Turing machine?, I mention several specific numbers that are definable, but not computable. In this information-theoretic context, the difference between a real number and a set of natural numbers is often not so great, and every set of natural numbers (or sentences in a given language) naturally corresponds to a real number, whose digits indicate membership or non-membership in that set. Let me list several definable non-computable reals by their names:

• The real $0'$, pronounced "$0$-jump". This is just the halting problem, which you can think of as the real number whose $n^{th}$ digit is $1$ if the $n^{th}$ Turing machine program halts on trivial input, and was mentioned already in some of the other answers.

• Kleene's $O$.

• $0''$, $0'''$, the double jump, triple jump and so on, which relativizes the halting problem to an oracle.

• $x'$ for any definable $x$, we have the halting problem relative to Turing machines with oracle $x$, which is strictly harder than $x$ to compute.

• Tot, the set of programs computing total functions. This has complexity $\Pi^0_2$.

• Fin, the set of programs computing a finite function. This has complexity $\Sigma^0_2$.

• TA, or "true arithmetic", is the set of arithmetic sentences true in $\langle\mathbb{N},+,\cdot,0,1,\lt\rangle$. It is Turing equivalent to $0^{(\omega)}$, the $\omega^{th}$ jump.

• WO, the set of programs computing a well-ordered relation on $\mathbb{N}$. This has complexity complete $\Pi^1_1$, just beyond the hyperarithmetic hierarchy.

• Th(HC), the set of statements true for hereditarily countable sets. This is an analogue of TA for the projective hiearchy.

• One can define other specific real numbers, which are not computable, such as the real number whose $n^{th}$ binary digit records whether or not $2^{\aleph_n}=\aleph_{n+1}$. This real number is definable, but not necessarily computable. In fact, for any real number, there is a forcing extension of the universe in which this definition defines that number. So in this sense, any number you like can be made to be a specific definable number in some set-theoretic universe.

• $0^\sharp$, pronounced "$0$-sharp", is a real number whose existence is a kind of large cardinal assertion, equivalent to the existence of a proper class of order-indiscernible ordinals for the constructible hierarchy. The real $0^\sharp$ is the theory of these indiscernibles.

• One can iterate this with $0^{\sharp\sharp}$ and $x^\sharp$ for any $x$.

• $0^\dagger$, pronounced "$0$-dagger", is a similar theory for indiscernibles over a richer inner model $L[\mu]$, with a measurable cardinal. This is a specific real number whose existence has consistency strength greater than the existence of a measurable cardinal.

• There are other similar reals, such as $0$-hand-grenade and others, which carry a stronger large cardinal strength.

Answer 3

The other standard example is to order the Turing machines and take the binary number with the nth decimal being 1 if the nth Turing machine stops. The computability of this number is (obviously) equivalent to the Halting problem.

Here computable means that the digits are literally computable by a Turing machine. Thus, Sqrt(2) is certainly computable. The book you're referring to defines a notion of "real-time computable" which also puts restrictions on how many steps it takes to compute the digits.

Answer 4

I think the same sort of trick (sticking a 1 or 0 in each decimal place according to some rule) can be played with several variants of the "Turing machine trick."

Here's one of a somewhat different flavor. Choose an enumeration of the Diophantine equations (over $\mathbb{Z}$), and define a number with decimal expansion $0.a_1a_2a_3\ldots$ where

$$ a_i=\begin{cases} 1&\text{ if the $i$-the Diophantine equation has a solution}\\\ 0&\text{ if not.} \end{cases} $$

This is non-computable by the negative solution to Hilbert's 10th problem.

(Though to be fair, by that same solution, this is probably tantamount to permuting the digits in one of the Turing machine examples.)