Program ordinals and omega squared

Question

A program ordinal is a (possibly transfinite) ordinal which can be assigned to programs in some language depending on their output.

To be more specific:

• Strings that give no output have ordinal 0
• Programs that output a program of ordinal n have ordinal n+1
• Programs P0 outputting multiple programs P1, P2... Pn have ordinal S, where S is the supremum of the set of program ordinals corresponding to the programs P1, P2... Pn

Your goal is to create the shortest possible program with program ordinal ω*ω, also writable as ω² or omega squared.

Output is required for a program. As well as this, the output must go through STDOUT or closest equivalent.

All programs printed by your program must be delimited by any string, so long as the delimiter is always the same. (acbcd and accbccd are allowed, but not acbed) These delimiters must be the only output other than the programs themselves, unless your language must output trailing characters.

Here is a program-ordinal ω program created in pseudocode, which generates programs of the form "exit, print(exit), print("print(exit)")...:

x=exit
loop{
print(x)
x='print(#x)'
}

Within each iteration of the loop, x is printed and then wrapped in print() (exit becomes print(exit)). # is put before x in pseudocode to indicate that it is the variable x and not the actual alphabetical character x.

The shortest program (measured in bytes) which has program ordinal ω² wins. Have fun.

Answer 1

Mathematica, 38 bytes

Nest[Nest[HoldForm@*Print,#,∞]&,,2]

Thinking process:

y=w="x=0;Do[Print[x=\"Print[\"<>ToString[x,InputForm]<>\"]\"],∞]";Do[Print[y=StringReplace[w,"0"->ToString[y,InputForm]]],∞]

This first solution is the same as the other solutions, it is a port of Surculose Sputum's answer, so I think it is correct. ToString[x,InputForm] sanitizes a string to be fed into it's own print statement. w stores the program that outputs the 0,1,2,3,... or the first ω, and y stores the program fed into itself n times that outputs ω+1,ω+2,ω+3..., when looped gives ω*ω.

But that got me thinking, all that nested loop does, is, well, Nest. Which is a function in Mathematica, and Mathematica also can output "held" code, meaning no handling strings. Which means I could change w to

w="Nest[HoldForm@*Print,0,∞]"

Which makes w hold a program that doesn't have a loop for n=0,1,2,3... , but has ω more directly inside it by just holding prints. Alternatively NestList would return the same n as the original program, but why waste time with printing 1, and then 2, and then 3, when we can just print a program ω.

But if I do that for the first part, what's stopping me from doing that to the last part?

Nest[HoldForm@*Print, Nest[HoldForm@*Print, 0, ∞], ∞]

Well, now we have that ω² program we wanted, but it looks a bit... referential? Like it's code is nesting itself. Nesting nests time!

Nest[Nest[HoldForm@*Print,#,∞]&,0,2]

That looks very nice. And since the program of just the keyword "Null" (not to be mistaken for the null program) is a valid program, we can golf out that 0.

And it could even be changed for arbitrary ωⁿ's, or even ω^ω for just two bytes more. If anyone wanted to run this themselves, I would change out the ∞ for a 3.

Side note: if you really wanted to keep using strings instead of holdform:

Nest[Nest["Print["<>ToString[#,InputForm]<>"]"&,#,∞]&,,2]

is 57 bytes, and good for learning.

Answer 2

Python 2, 67 63 65 bytes

x=""
while 1:x="x=%r\nwhile 1:x='print%%r;'%%x;exec x;"%x;print x

Try it online!

Use the same strategy as @UnrelatedString's answer, be sure to check out and upvote his answer! Repeatedly print out programs with ordinal \$0, \omega, \omega2, \omega3,\ldots \$. The programs are separated by the string ";\n" (a semi-colon and a new line).

68 bytes to separate programs by a blank line.

Explanation

A program with ordinal \$n+1\$ is created by adding a print statement around an \$n\$-ordinal program:

print <escaped string of ordinal-n program>

A program with ordinal \$\omega(n+1)\$ is created by repeatedly printing out programs with ordinal \$\omega n, \omega n+1,\omega n+2,\ldots\$

x = <string of omega*n program>
while 1:
  x = 'print %r' % x
  exec x

Note the use of %r, which escapes the given string x. This way, we don't have to worry about quote and new line characters.

Finally, a program with ordinal \$\omega^2\$ is created by repeatedly printing out programs with ordinal \$0, \omega, \omega 2,\omega 3,\ldots\$:

# string of program to go from omega*n to omega*(n+1)
s = "x=%r\nwhile 1:x='print%%r'%%x;exec x" 
# current omega*n program, start with n=0
x = ""
while 1:
  # create the omega*(n+1) program from omega*n
  x = s % x
  # print it out
  print x

Answer 3

Python 3, 85 bytes

s='def l(f,x):\n print(x+"\\n")\n l(f,"%s%r)"%(f,x))'
exec(s)
l(s+"\nl('print(',",'')

Try it online!

I... think this might be valid? This should print a sequence of programs, separated by blank lines, with ordinals ω, ω·2, ω·3, ω·4, ..., but the reasoning by which I arrived at those ordinals was pretty shaky and I've already forgotten what it even was, so I'd appreciate being shown that I'm completely wrong. The general idea of it is that one program with ordinal ω+ω = ω2 is one which prints a program with ordinal ω, then prints a program that prints that program (so that it has ordinal ω + 1), then prints a program that prints that, and so on... and the part I don't feel too solid about is doing that with the program with ordinal ω·2 to get to ω·3, and iterating to get ω².