Robert's Mistakes

Ordinals from loops

Nov 01, 2021

In model theory, ordinals can be related to the strength of formal systems. Programming languages are formal systems, so what are the ordinals for various constructs in modern programming languages? For example, the following would print ten exclamation marks, or bangs:

for(i in 1..10) print "!";

So for loops, where we have to specify the number of times it is supposed to repeat, can be made to print any finite number of bangs. The first ordinal that cannot be reached by a for loop is ω\omega, the smallest of the infinite ordinals.

Note, that all this can be achieved with a single for loop, as long as we are allowed to mention the desired ordinal as bounds. For now, let's not allow infinite ordinals as bounds in any loop. Just out of curiosity, what would it mean if we'd limit bounds in for loop to some very large, but finite number, say, 3? We could still model larger ordinals than 3 by writing more than just a single for loop:

for(i in 1..3) "!";
"!";

I have taken liberty to abbreviate that print keyword away. Anyways, this gives 3+1. We could also combine for loops, like running a number of for loops one after another:

for(i in 1..3) "!";
for(i in 1..3) "!";
for(i in 1..3) "!";

Should we be allowed to write more than our huge number 3 many for loops? Like the limitation to not use large ordinals in our construction this can be argued about. However, this wouldn't stop us from writing some larger ordinals:

for(i in 1..3) {
  for(i in 1..3) "!";
  "!";
}

The Cantor normal form of the above might be something like (3+1)×3(3+1) \times 3 which can be expanded to 3×3+33 \times 3 + 3.