Skip to main content
1 of 2
Gro-Tsen
  • 32.5k
  • 5
  • 87
  • 373

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.)

Gro-Tsen
  • 32.5k
  • 5
  • 87
  • 373