6
\$\begingroup\$

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 ω2 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 ω2 wins. Have fun.

\$\endgroup\$
  • 3
    \$\begingroup\$ Related. \$\endgroup\$ – Anders Kaseorg May 26 at 22:05
  • 4
    \$\begingroup\$ How exactly is outputting multiple programs defined? \$\endgroup\$ – Unrelated String May 26 at 22:48
  • 3
    \$\begingroup\$ So, if P0 outputs P1, where P1 has ordinal n, P0 has ordinal n + 1, but if P0 outputs P1 and P2, where both P1 and P2 have ordinal n, P0 has ordinal n? Since n is the supremum of the set {n}. \$\endgroup\$ – Abigail May 26 at 23:18
  • 3
    \$\begingroup\$ Maybe I'm misunderstanding something, but in your example program of ordinal \$\omega\$, shouldn't 0 be replaced by a program that prints nothing (for example, exit or print "")? What your example prints first is the number 0, which isn't a program (at least in most languages). \$\endgroup\$ – Mitchell Spector May 27 at 5:50
  • 3
    \$\begingroup\$ I take it that the pseudocode line x="print(x)" is meant to have x be replaced with its value within the string? \$\endgroup\$ – xnor May 27 at 5:55
1
\$\begingroup\$

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 ω2 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 ωn'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.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Not too sure I'd call it the same strategy when I reinvent the while loop and think I'm clever for using exec for it \$\endgroup\$ – Unrelated String May 27 at 6:39
  • 1
    \$\begingroup\$ Your new code looks quite close to the string literal in the loop inserted inside itself. \$\endgroup\$ – xnor May 27 at 8:00
  • 1
    \$\begingroup\$ @xnor I tried to extract the similar part into a common string. However, making sure that everything is escaped probably was super hard, and the overhead ended up being too large. \$\endgroup\$ – Surculose Sputum May 27 at 9:26
  • 2
    \$\begingroup\$ @SurculoseSputum I haven't read through your code, but when you say, "Finally, a program with ordinal \$\omega^2\$ is created by repeatedly printing out programs with ordinal \$\omega n, \omega n+1,\omega n+2,\ldots\$:", should the sequence of ordinals at the end be "\$0, \omega, \omega 2, \ldots, \omega n, \omega(n+1), \omega(n+2), \ldots\$"? \$\endgroup\$ – Mitchell Spector May 27 at 15:15
  • 2
    \$\begingroup\$ @MitchellSpector Thanks for catching that. I copy-pasted from the wrong place. \$\endgroup\$ – Surculose Sputum May 27 at 16:24
2
\$\begingroup\$

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 ω2.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ A minor point: (This isn't a comment on your code, which I haven't checked.) Ordinal multiplication isn't commutative. You meant \$\omega 2\$ and \$\omega 3\$, not \$2\omega\$ and \$3\omega\$. When you apply the definition of ordinal multiplication, \$\omega 2 = \omega+\omega\$, and \$\omega 3 = \omega+\omega+\omega\$, but \$2\omega = 3\omega = \omega.\$ \$\endgroup\$ – Mitchell Spector May 27 at 4:46
  • 1
    \$\begingroup\$ I think that the resulting "list of programs" must be clearly defined (it must be possible to determine where one program ends and the other begins). \$\endgroup\$ – user202729 May 27 at 6:12
  • \$\begingroup\$ That's my concern as well, but until the challenge author responds I've gone and erred on the side of convenience. I will add a less ambiguous version now though. \$\endgroup\$ – Unrelated String May 27 at 6:22
  • 1
    \$\begingroup\$ I added the rule that delimiters must exist, so I think the second version should be valid. \$\endgroup\$ – Andrew May 27 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.