Computability – Examples of Non-Computable Real Numbers

computability

Is this true, that if we can describe any (real) number somehow, then it is computable?

For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, that there are some simple periodic formulas to calcualte $\pi$. If it wasn't than we were unable to calculate $\pi$ ans it was non-computable.

If so, that we can't provide any examples of non-computable numbers? Is that right?

The only thing that we can say is that these numbers are exist in many, but we can't point to any of them. Right?

Best Answer

I haven't thought this through, but it seems to me that if you let $BB$ be the Busy Beaver function, then $$\sum_{i=1}^\infty 2^{-BB(i)}=2^{-1}+2^{-6}+2^{-21}+2^{-107}+\ ... \ \approx 0.515625476837158203125000000000006$$ should be a noncomputable real number, since if you were able to compute it with sufficient precision you would be able to solve the halting problem.

Related Solutions

Is there literature on non-computable numbers that can’t be even be identified

Essentially, it sounds like you're looking for computability theory, and specifically the theory of the Turing degrees. You already understand the notion of relative (= oracle) computability; the Turing degrees are the resulting equivalence classes. Each real $a$ (or function from naturals to naturals, or set of naturals, or [naturally equivalent object]) generates a Turing degree $$deg(a)=\{b: b\equiv_Ta\}.$$ Here "$x\equiv_Ty$" means "$x\le_Ty$ and $y\le_Tx$," as expected. The Turing degrees form a partial order - denoted $\mathcal{D}$ - with respect to $\le_T$: for Turing degrees ${\bf a},{\bf b}$ we say ${\bf a}\le_T{\bf b}$ if every element of ${\bf a}$ is $\le_T$ every element of ${\bf b}$ (note that we can replace "every" with "some" without affecting the meaning).

The (correct) observation you've made amounts to the statement that the Turing degrees have the countable predecessor property - for each ${\bf a}$, there are at most countably many ${\bf b}\le_T{\bf a}$ - and hence no single Turing degree (or finite set of degrees, or even countable set of degrees) "covers" everything. This is just the start of things, though - one of the major topics in computability theory is the study of the structural features of $\mathcal{D}$. Some basic questions:

Is $\mathcal{D}$ linearly ordered? (No.)
- Note that this doesn't follow immediately from your observation: there are uncountable linear orders with the countable predecessor property, such as the first uncountable ordinal $\omega_1$. However, the countable predecessor property does imply that $\mathcal{D}$ isn't linearly unless CH holds; it turns out that we can then use a couple bits of heavy set-theoretic machinery (here and here) to give a very silly proof of non-linearity.
Does every pair of Turing degrees have a least upper bound? (Yes.) Greatest lower bound? (No.)
Does every countable set of Turing degrees have an upper bound? (Yes.) A least upper bound? (No - in fact, basically never!)
Does $\mathcal{D}$ have any nontrivial automorphisms? (Open, and maybe THE major open question!)
EDIT: In response to "is there a known set of functions that are capable of generating all real numbers?," here is a very cute fact. Say that a Turing degree is minimal if it is nonzero (= doesn't consist of computable sets) but isn't strictly above anything nonzero. One might think that there are very few minimal degrees, and perhaps be surprised they exist in the first place; after knowing they exist, one might still reasonably think that there isn't much "strength" to be found in the minimal degrees. This turns out to be false, however: every Turing degree is below the least upper bound of some pair of minimal degrees. Rephrasing that, the set of functions of minimal Turing degree lets you compute every real!

There are also "local" questions. E.g. we can look at the substructure $\mathcal{R}$ consisting of Turing degrees of computably enumerable sets, and ask similar questions. Local problems are generally more complicated than global problems; for example, the nonlinearity of $\mathcal{D}$ was proved a decade before the nonlinearity of $\mathcal{R}$, and the proof of the latter required a fundamental new insight (the idea that different "requirements" in a construction can wind up interfering with each other, and how to manage this; this interference is called "injury" and proofs which deal with it are called "priority arguments").

A final side note: there's nothing in the argument you've rediscovered that needs computability specifically. Rather, there is a general fact that any specific reasonable notion of definability fails to capture all the reals (here "reasonable" means that definitions must be "finitary").

It turns out, however, that there are surprising subtle limits to this principle: most drastically, there are models of ZFC where every real is first-order definable (assuming ZFC is consistent in the first place, of course). The issue here is that first-order definability over the whole set-theoretic universe is far less well-behaved than computability, which in some sense is "local." So the obvious argument (which the linked article above calls the "math-tea argument") only applies to "concrete" situations. This isn't worth diving into deeply until you have a good understanding of basic computability theory and set theory, but it's good to know it exists down the road.

Best Answer

Related Solutions

Is there literature on non-computable numbers that can’t be even be identified

Related Question