7
\$\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\$
14
  • 3
    \$\begingroup\$ Related. \$\endgroup\$ Commented May 26, 2020 at 22:05
  • 4
    \$\begingroup\$ How exactly is outputting multiple programs defined? \$\endgroup\$ Commented May 26, 2020 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
    Commented May 26, 2020 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\$ Commented May 27, 2020 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
    Commented May 27, 2020 at 5:55

4 Answers 4

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
\$\endgroup\$
5
  • \$\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\$ Commented May 27, 2020 at 6:39
  • 1
    \$\begingroup\$ Your new code looks quite close to the string literal in the loop inserted inside itself. \$\endgroup\$
    – xnor
    Commented May 27, 2020 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\$ Commented May 27, 2020 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\$ Commented May 27, 2020 at 15:15
  • 2
    \$\begingroup\$ @MitchellSpector Thanks for catching that. I copy-pasted from the wrong place. \$\endgroup\$ Commented May 27, 2020 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.

\$\endgroup\$
4
  • 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\$ Commented May 27, 2020 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\$
    – DELETE_ME
    Commented May 27, 2020 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\$ Commented May 27, 2020 at 6:22
  • 1
    \$\begingroup\$ I added the rule that delimiters must exist, so I think the second version should be valid. \$\endgroup\$ Commented May 27, 2020 at 10:04
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.

\$\endgroup\$
0
\$\begingroup\$

Self-modifying Brainfuck, 47 bytes

-[[<]>[>.]+0]<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]

The 0 represents a null byte \x00 and will be used as the delimiter between programs. I will also use 1 and ÿ to represent the bytes \x01 and \xff respectively.

The idea here is to use the program <[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ with some leading and trailing 1s to represent ordinals between 0 and \$\omega^2\$. The number of trailing 1s represent how many multiples of \$\omega\$ there are, and the number of leading 1s is how much is added to it. The program 11111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111, for example, represents \$\omega3+5\$ and prints the \$\omega3+4\$ program 1111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111.

11111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111     // w3+5
11111                                           // Do nothing
     <[<]>-                                     // Decrement the first character of the code (a '1')
           [?????????????????????]              // If it's not zero do this (not in this case)
                                  >[.>]         // Print the remaining code
                                       ÿ111     // Do nothing

The leading 1s will continue to be deleted until the \$\omega3\$ program is reached.

<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111  // w3
<[<]>-                                  // Decrement the first character (the '<')
      [                     ]           // If it's not zero
       +                                // Increment it back to '<'
        [>]<-                           // Decrement the last character of the code (a '1')
             [?]                        // If it's not zero do this (not in this case)
                <[         ]            // Loop
                  [<]+                  // Add a '1' to the start of the program
                      [>.]<             // Print the code with a trailing '0'

This will print the following programs (delimited by 0s):

<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11       // w2
1<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11      // w2+1
11<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11     // w2+2
111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11    // w2+3
...

These programs will keep deleting the leading 1s until the program starts with <, then they delete a trailing 1 and print programs with an increasing number of leading 1s. This continues until the 0 program is reached.

<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ     // 0
<[<]>-                                  // Decrement the first character (the '<')
      [                     ]           // If it's not zero
       +                                // Increment it back to '<'
        [>]<-                           // Decrement the last character (the 'ÿ')
             [<]                        // Go to the start of the code
                <[?????????] >[??]ÿ     // Halt without printing anything

The \$\omega^2\$ program simply prints the \$0, \omega, \omega2, \omega3, ...\$ programs.

-[[<]>[>.]+0]<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]     // w^2
-                                                   // Append a 'ÿ' to the end of the code
 [          ]                                       // Loop
  [<]                                               // Find the '0'
     >[>.]                                          // Print the program with a trailing '0'
          +                                         // Add a '1' to the end

This prints:

<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ     // 0
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ1    // w
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11   // w2
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111  // w3
...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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