Ranks of reals in the Constructible Universe $L$ In the Constructible Universe $L$ every real number (subset of $\omega$) has an $L$-rank less than $\omega_1$, and the set of such ranks is unbounded in $\omega_1$. A natural question arises as to what the ranks of a specific given real numbers are: For instance $$\{0,2,4,6,...\}$$
$$\{2,3,5,7,...\}$$
$$\{2,4,16,32,...\}$$
Now, it would seem that every one of these sets could in principle be defined in first order logic without parameters (though I am unsure how this would work in practice), therefore they would all have rank $\omega +1$. Indeed, it seems probable that all computable reals would also be definable, therefore at $L_{\omega +1}$ we get all computable subsets of $\omega$. However, suppose we consider these subsets as ranges of functions, then we would naturally like to know the rank of the set 
$$\{1, 4, 6, 13,...\}$$
of values of the Busy Beaver function. This function is definable, but not computable, so we could expect its rank to be $\ge \omega + 2$? Is its rank known? A number of other questions present themselves.
Given a particular countable ordinal $\alpha$, can we always find (by which I mean, explicitly describe) a real $X$ with $L$-rank $\alpha$?
In terms of complexity, the reals clearly become more complex as their $L$-rank increases, but is there a way to formalize this precisely?
Finally, if the reals become more complex with increasing $L$-rank, then would a non-constructible real (assuming its existence) be in some sense infinitely complex in that it could not be described in any form whatsoever, either directly, or via some cumulative process?
 A: Below I've addressed your specific questions. However, based on your multiple questions about this I think it might be more useful to give a list of good sources, so I'll do that first.


*

*On "gaps" in the constructible universe: Marek/Srebrny, Gaps in the constructible universe. The introduction is very readable and will give you a good sense of what's going on.

*On the mastercode hierarchy (and what happens when new reals do appear): Hodes' paper Jumping through the transfinite. This is also closely connected with the study of gaps. Like the paper above, the introduction is a very good read.

*On the general structure of $L$: Devlin's book Constructibility. It has a serious error unfortunately, but that error doesn't affect the important results; see this review by Stanley  for a summary of the issue (and if you're interested in how to correct it, this paper by Mathias). Ultimately the error is very limited and easily avoided once you know it exists - basically, doubt anything involving a claim about the (aptly named) set theory "BS," but pretty much everything else is correct. 


Now, it would seem that every one of these sets could in principle be defined in first order logic without parameters (though I am unsure how this would work in practice)

There's no subtlety here: we first define addition and multiplication of finite ordinals, and now we can use port the usual definitions in $(\mathbb{N}; +,\times)$ of those sets into the set theory context. Indeed, there's a natural way (the Ackermann interpretation) to pass between $L_\omega$ and $(\mathbb{N};+,\times)$, so definability in $L_\omega$ can be reasoned about by proving things in the more familiar setting of definability in arithmetic; e.g. this lets us argue that the Busy Beaver function is indeed in $L_{\omega+1}$.

would a non-constructible real (assuming its existence) be in some sense infinitely complex in that it could not be described in any form whatsoever, either directly, or via some cumulative process?

Certainly not: e.g. $0^\sharp$ is definitely definable (it's $\Delta^1_3$, and in particular is definable in second-order arithmetic) but is not in $L$ (assuming it exists at all). ZFC can't prove that something matching the definition of $0^\sharp$ exists, but it can prove that if it exists then it's not constructible.

Given a particular countable ordinal $\alpha$, can we always find (by which I mean, explicitly describe) a real X with L-rank $\alpha$?

No; for many (indeed, club-many) ordinals $<\omega_1^L$, we have no new reals at that level. Indeed, the $L$-hierarchy is "filled with gaps" - even very long gaps. If you google "gaps in $L$-hierarchy" you'll find a lot of information around this; roughly speaking, an ordinal $\alpha<\omega_1^L$ starts a "long" gap if it is "very" similar to $\omega_1^L$.

In terms of complexity, the reals clearly become more complex as their $L$-rank increases, but is there a way to formalize this precisely?

Well, the obvious one is that if $A$ has $L$-rank greater than that of $B$, then the set $A$ is not definable in the structure $(\mathbb{N}; +,\times, B)$ (that is, arithmetic augmented by a predicate naming the naturals in $B$). In particular $A\not\le_TB$. On the other hand, $A$ might not compute $B$ either (e.g. if $A$ is "sufficiently Cohen generic" over $L_\beta$ then $A$ won't compute any noncomputable real in $L_\beta$ - in particular, it won't compute any real in $L_\beta$ not in $L_{\omega+1}$).
