13
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ I would expect any sensible definition of "computable" makes $\sqrt2$ a computable number... yet it is not trascendent. $\endgroup$ May 30, 2010 at 0:42
  • 2
    $\begingroup$ What does real-time computable mean? $\endgroup$ May 30, 2010 at 1:52
  • 11
    $\begingroup$ Chaitin's Ω is not a specific number. It is only defined relative to a universal prefix-free machine, and there are many choices of such a machine with no single "correct" choice. Any sense of "specific" that applies to Ω also applies to the Turing jump of the empty set, 0'. $\endgroup$ May 30, 2010 at 2:47
  • 3
    $\begingroup$ A number is real-time computable, if there is an algorithm that computes its digit sequence for which there is a constant c, such that for every n, the algorithm uses at most cn steps to compute the first n digits. $\endgroup$ May 30, 2010 at 5:08
  • 1
    $\begingroup$ In the context of Turing machines, a real-time algorithm always inputs a symbol, then outputs a symbol within a constant c number of steps. $\endgroup$ May 30, 2010 at 5:15

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
19
  • $\begingroup$ Haldfan, I give up with my attempts to understand the question. Maybe, not a motivation, but just the question itself. The only thing I do understand that the question has nothing to do with nt.number-theory. $\endgroup$ May 30, 2010 at 7:05
  • $\begingroup$ yes, agreed; the tag 'number theory' is misleading. $\endgroup$ May 30, 2010 at 7:27
  • 8
    $\begingroup$ The claims about non-definable numbers in this answer are problematic, as I explain in this MO answer: mathoverflow.net/questions/44102/… and also in my article: jdh.hamkins.org/pointwisedefinablemodelsofsettheory. The basic situation is that the notion of "definable" is simply not expressible, and if there are any models of ZFC at all, then there are models in which every real number is definable. $\endgroup$ Apr 18, 2012 at 8:07
  • 8
    $\begingroup$ I look forward to your update. Although a naive treatment of definability may be common, I think we can aspire here at mathoverflow to treat the topic with precision and correctness. The naive treatment is indeed incorrect, since using it one could argue like this: there are only countably many definable ordinals, but uncountably many ordinals; thus, there is a least ordinal $\alpha$ that is not definable. But this defines $\alpha$, a contradiction if this usage of "definability" is legitimate. $\endgroup$ Apr 20, 2012 at 6:08
  • 6
    $\begingroup$ Uncomputable does not imply incompressible (although the converse is true). For example, the number obtained by interleaving the digits of $\Omega$ with the digits of $\pi$ is uncomputable, but can be compressed by a factor of $\frac{1}{2}$. $\endgroup$ Mar 6, 2015 at 23:30
9
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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