Let's call regular Scheme, with which I assume everybody is familiar, "Scheme-0".
Now let's introduce another programming language, Scheme-1: It's just like Scheme-0, but has an extra function, (H x code), which takes two arguments - x, which has to be 0, and code, a piece of Scheme-0 code.
H will determine whether the piece of code will halt or not, and return true if it does and false otherwise (a syntactically incorrect program is assumed to halt). H itself is guaranteed to halt, because it is "magical". Giving it a first parameter greater than 0 results in an error.
Now let's introduce another programming language, Scheme-2. It's just like Scheme-1, but the instruction H will now accept 0 or 1 as its first argument. (H 1 code) will halt-check a Scheme-1 program.
Now that we have Scheme-1 and Scheme-2, we can also have Scheme-N for an arbitrary natural number N.
Now consider the following program:
(let loop ((n 0)) (H n '(quote ())) (loop (+ n 1)))
It's pretty clear that this program does not halt. A more interesting question is: What programming language is it written in? It's clearly not Scheme-N for any natural number N, since, given sufficient time, the program will execute (H X '(quote ())), with X > N.
The language in which this program is valid is the first transfinite Scheme - Scheme-omega. Note that Scheme-omega, unlike any Scheme-N, does NOT add a new legal x value to the "previous" scheme. This is because omega is a limit ordinal, which doesn't have a "previous" ordinal.
Scheme-omega is important because in it you can, if you want, write a Brainhype interpreter. Anybody care to implement one?
The next Scheme after Scheme-omega is, of course, Scheme-omega+1, which does add a new valid x value, allowing (H omega code), capable of halt-checking Scheme-omega code. Note that in order to fully support this, our Scheme would require a transfinite ordinal datatype - not a big deal. Note however than any fixed finite notation for ordinals can support only countably many of them, so that there is always a next (still countable) ordinal which requires a new kind of representation.
- Oracle machine on Wikipedia
- Ordinal number on Wikipedia
- Arithmetical hierarchy (Relation to Turing machines) on Wikipedia