New here. I'm wanting to know whether or not it's theoretically possible to construct a function which can map the set of all real numbers to the set of all computable functions, and whether or not this supposed function is even computable to begin with.
Mapping real numbers to functions
computabilityfunctionsreal-analysis
Related Solutions
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.
I'm not familiar with computable analysis. But it seems to me that irrational numbers are not $O(1)$-computable: Let $r$ be an irrational number, and $(q_n)$ a Cauchy name for $r$. Suppose there exists a constant-time algorithm to compute $q : \mathbb{N} \rightarrow \mathbb{N}$. There is some constant $c$ such that the algorithm takes at most $c$ steps. In particular, the output of the algorithm can have at most $c$ bits, a contradiction to the fact that the number of decimal digits of $q_n$ tends to infinity. (Alternatively, if $q_n$ is represented as a fraction, the size of the denominator tends to infinity.)
Best Answer
The answer is indeed "no", but that's not because there are more computable functions than real numbers, but because there are more real numbers than computable functions. Citing Wikipedia: "Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only countably many computable functions". If there are countably many computable functions, there is a bijection from natural numbers to that set. And there are uncountably many real numbers, so there cannot exist a bijection from real numbers to computable functions.