Languages beyond enumerable

Question

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings.

Languages are commonly classified in a hierarchy, with the

• enumerable $\equiv$ recursively enumerable $\equiv$ Turing-recognizable

the outermost set, beyond decidability:

---

     
      ^{(Figure from Sipser.)}

---

My question is about the terminology extending this hierarchy. The non-enumerable are clearly outside the enumerable ($\equiv$ Turing-recognizable). But some languages $L$ are enumerable but their complement $\overline{L}$ is not enumerable (such as the language of all Turing Machines that halt on a given input), whereas other languages $L$ are not enumerable, and their complement $\overline{L}$ is also not enumerable (such as the pairs of "equivalent" Turing machines).

Q1. Are there standard names for languages that go farther outside of the above diagram?

The set of all languages is uncountable, so there is plenty of room for expanding the diagram. But I haven't seen a clear, "standard" expansion.

I am seeking a progression further and further out into the uncountable to help students (and me!) see the vastness. I am seeking the equivalent of this iconic complexity-theory hierarchy:

---

     
      ^{(Image from Seneca ICT.)}

---

Q2. Is there an equivalent diagram in language theory?

Answer 1

Yes, for starters there is the arithmetical hierarchy, where enumerable = $\Sigma^0_1$ and it continues $\Pi^0_1$, $\Delta^0_2$, $\Sigma^0_2$ etc.

See also the Computability Menagerie.

Answer 2

In my answer to a question about degrees of irrationality, I had posted the following summary account of degrees of complexity, which in the end I believe ultimately reaches into the realm of the upper hierarchies of vastness to which you seem to aspire.

Answer to Are some numbers more irrational than others?

The other answers and comments are fascinating, particularly about the irrationality measure, but allow me to give a little more information along the lines of Mark Sapir's answer by mentioning that there are several very large, intensely studied hierarchies of complexity for reals numbers. After the initial familiar notions come several others...

• rational

• algebraic

• computable

The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in computable analysis.) The computable subsets of $\mathbb{N}$ are those for which we can compute yes/no answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.

• computably enumerable

The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the yes answers for membership in finite time. The concept of relative (oracle) computability leads to the hierarchy of Turing degrees, which measures the comparative computable complexity of a real.

• arithmetic

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

• hyperarithmetic

A real is hyperarithmetic if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The hyperarithmetic hierarchy is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.

• projective

A real is projective if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The projective hierarchy is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.

• constructible

A real is constructible if it exists in Gödel's constructible universe $L$. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.

• ordinal-definable

A real (or set) is ordinal-definable if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.

• generic

A real is generic over $L$ (or some other fixed universe $V$) if it exists in a forcing extension of $L$ (or $V$) by set forcing. Of course, it is relatively consistent with ZFC that every real is generic over $L$, since this is true in $L$ itself, but under some large cardinal axioms, there are reals, such as $0^\sharp$, that cannot be added by forcing over $L$.

The higher levels of these latter hierarchies are further developed and stratified by the enormous variety of models of set theory arising from large cardinals, various inner model constructions, forcing extensions and so on, so that the hierarchy loses its linear nature, becoming instead a dense jungle of various interacting concepts of set theory.

Answer 3

There are many such classes of languages depending on the approach you want to use. Let me focus on just one class: the hyperarithmetic (hyperarithmetical?) class, and try to explain why it is a very natural class, by mentioning several equivalent definitions of it:

• "Computability in a type 2 functional": a hyperarithmetic set of integers is one that can be computed by a "hyperarithmetical" machine, where a "hyperarithmetical" machine is one that can do everything that a Turing machine can do, but with the additional ability to decide whether a function $f\colon \mathbb{N} \to \mathbb{N}$ takes a nonzero value, where the function $f$ is itself computed by a hyperarithmetical machine. (In other words, given a hyperarithmetical machine computing $f$, such that $f(n)$ is defined for every $n\in\mathbb{N}$, a hyperarithmetical machine can compute every $f(n)$ at once and decide whether there is one such that $f(n)\neq 0$, in which case of course it can also trivially find the corresponding $n$; if not every $f(n)$ is defined because the machine computing them does not halt, then the overall call will also not halt). This definition is recursive, of course, and I didn't formalize it completely, but it still makes sense as the smallest which satisfies the conditions. In the classical computability literature, this description is called "computability [à la Kleene] in the type 2 functional $\mathbf{E}$", but apparently it is never described in terms of "machines" like I tried to sketch.

• …In practice, a hyperarithmetical machine is one that can compute not only with integers, but also with exact real numbers (i.e., sequences of integers), not all real numbers but, precisely, those which are hyperarithmetical. I think this makes the definition fairly natural.

• …Yet another way of rephrasing the same definition is that a hyperarithmetical machine is one that can compute infinite conjunctions/disjunctions (logical and/or), provided the terms of the conjunction/disjunction are themselves computed hypearithmetically. This is just a rephrasing of the above, but it provides a link with certain kinds of infinitary logic.

• "Metarecursion": a set of integers is hyperarithmetic when it can be computed by a machine much like a register machine, except that the registers are allowed to hold ordinal values, the ordinals ranging up to the Church-Kleene ordinal (=smallest nonrecursive ordinal) $\omega_1^{\mathrm{CK}}$, and the machine is allowed to "loop" up to that value (I tried to summarize the idea of such ordinal computations here, in which terminology I would be speaking of $(\omega_1^{\mathrm{CK}},\omega_1^{\mathrm{CK}})$-machines). These machines can compute much more than sets of integers, but those sets of integers which they can compute are precisely the hyperarithmetic ones.

• The level $\Delta^1_1$ of the analytical hierarchy is again the class of hyperarithmetic sets: essentially those sets of integers which can be defined using one second-order quantifier, both in an existential and in a universal manner. This is an analogue (the so-called "lightface" analogue) of one of the definitions of Borel sets in descriptive set theory.

• Iterating the Turing jump: a $0$-machine is just a Turing machine; a $0'$-machine is one that has access to an oracle that can tell it whether a $0$-machine halts; a $0''$-machine is one that has access to an oracle that can tell it whether a $0'$-machine halts; a $0^{(n)}$-machine is what you imagine; a $0^{(\omega)}$-machine (or arithmetical machine) is one that has access to an oracle that can tell it, given $n$, whether a $0^{(n)}$-machine halts; it is possible (although not completely trivial) to iterate this over the recursive ordinals, and hyperarithmetic sets are precisely those which are recognized by a $0^{(\alpha)}$-machine for some recursive ordinal $\alpha$.

• The sets of integers belonging to the level $L_{\omega_1^{\mathrm{CK}}}$ of Gödel's constructible universe where each level is defined essentially by adding every subset of the previous level that can be defined in it by a first-order formula. Also, this level $L_{\omega_1^{\mathrm{CK}}}$ is the first one which satisfies a sizable amount of set theory, namely Kripke-Platek.

Since all these definitions conspire to give the same class of hyperarithmetic sets, I think it's fair to say that it's a natural class. There are plenty of classes both above and below, but I think this one deserves to be better known.

(Also, concerning complexity: there are also plenty of classes between $\mathsf{EXPTIME}$ and $\mathsf{REC}$: there are $\mathsf{ELEMENTARY}$ and $\mathsf{PR}$, but also lots of classes which can be defined between the class $\mathsf{PR}$ of primitive recursive sets/functions and that $\mathsf{REC}$ of recursive sets/functions, and that try to bridge the gap between complexity and computability. These "subrecursive" hierarchies also deserve to be better known.)

Answer 4

Bjørn mentioned the arithmetical and analytical hierarchies and Joel gave some of the big classifications beyond that, but there's also a theory of the finer gradations (Turing degrees). Moving up levels of the arithmetical and analytical hierarchies is done by iterating the Turing jump, to transfinite depth once you are past the arithmetic hierarchy.

The polynomial hierarchy in complexity theory is analogous to the arithmetical hierarchy in logic.