Skip to main content
2 of 3
added 437 characters in body
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Languages beyond enumerable

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][1].)
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](https://scs.senecac.on.ca/~gpu621/pages/content/intro.html).)

Q2. Is there an equivalent diagram in language theory?

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958