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

Question

It seems to me that most real numbers can't be calculated by any finite set of instructions, even if we make use of non-computable functions.

First, assume that we have an oracle that will provide the digits of any specified non-computable number to arbitrary precision. So, for example, if we state a particular instance of Chaitin's constant, then our oracle can gives us this value to arbitrary precision. This would allow us to perform operations on non-computable numbers. And by extension, we could even specify non-computable operations on non-computable numbers, so long as the result is also some real number, which our oracle can then provide to arbitrary precision.

Any such specification will consist of a finite set of instructions, some of which could include non-computable functions, the outputs of which will be provided by our oracle.

Note that the set of all such instructions is countable, since any language in which we express the instructions will necessarily be finite. It follows that even if we allow for the use and resolution of non-computable functions, we can only specify a countable subset of the reals using any particular language.

It follows that not only are most of the real numbers non-computable, they're incapable of articulation using a finite language.

Note that this is distinct from defining a particular real number. Instead, I am pointing out that even if we make use of non-computable functions, it does not seem possible to construct a one-to-one map from (A) the set of statements that define a computation to (B) the set of real numbers.

As a result, it does not appear to be possible to calculate the set of real numbers by making use of a finite set of non-computable functions.

In short, most real numbers can't even be calculated using a finite set of non-computable functions.

Is there a known set of functions that are capable of generating all real numbers?

Answer 1

A finite set of oracles can only compute a countable set of real numbers, because there are only a countable number of algorithms. So, because the entire set of real number is uncountable, no finite set of oracles can compute (even with different algorithms) the entire set of real numbers.

Answer 2

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.