Make the largest infinity that you can!

The ordinal number system is a system with infinite numbers. A lot of infinite numbers. So many infinite numbers that it literally does not have an infinity to represent its own infiniteness. The image above gives a little idea of how they work. An ordinal number (Von Neumann construction) is a set of previous ordinals. For example, 0 is the empty set, 1 is the set {0}, 2 is the set {0, 1} and etc. Then we get to ω, which is {0, 1, 2, 3 ...}. ω+1 is {0, 1, 2, 3 ... ω}, ω times two is {0, 1, 2 ... ω, ω + 1, ω + 2...} and you just keep going like that.

Your program will output a set of ordinals, such {0, 1, 4}. Your score will then be the least ordinal more than all the ordinal in your set. For {0, 1, 4} the score would be 5. For {0, 1, 2 ...}, the score would be ω.

How do you output your ordinals you ask. Code of course. Namely, your program will output a potentially infinite list of other programs, in quotes, one on each line (use the literal string "\n" to represent new lines). A program corresponds to its score as indicated above. For example, if you output

"A"
"B"
"C"


where A, B, and C are themselves valid answers and have scores {0, 1, 4}, the score of your program would be 5. Note that A, B, and C, have to be full programs, not fragments.

Based on the above rules, a program that outputs nothing has a score of 0 (the least ordinal greater than all {} is 0). Also, remember a set cannot contain itself, via the axiom of foundation. Namely, every set (and therefore ordinal) has a path down to zero. This means the a full-quine would be invalid as its not a set.

Also, no program is allowed to access outside resources (its own file, the internet etc...). Also, when you list your score, put the cantor normal form of the score alongside it if it isn't in cantor normal form already, if you can (if not, someone else can).

After taking all the above into account, the actual answer you post must be under 1,000,000 bytes (not counting comments). (This upper bound will likely only come into play for automatically generated code). Also, you get to increment your score for each byte you don't use (since we are dealing with infinities, this will probably only come into account when ordinals are very close or the same). Again, this paragraph only applies to the posted answer, not the generated ones, or the ones the generated ones generate, and so on.

This has the quine tag, because it may be helpful to generate at least part of the sources own code, for use in making large ordinals. It is by no means required though (for example, a submission with score 5 would probably not need its own source code).

For a worked out and annotated example, see here.

• Does it mean it should not terminate to output infinite number of cardinals? And where is the restricted-source part? I think this tag isn't for code length limitations. Requiring both quoted and newlines converted to \n seemed redundant to me, should other built-in list formats be allowed? Apr 17, 2015 at 1:43
• @user23013 It may, at your option, never terminate to output an infinite number of ordinals. Although quoting and escaping newlines is redundant, many languages have built in facilities for just that task. What do you mean by other list formats? Apr 17, 2015 at 1:48
• I meant any list or array format recognizable by the used language. Or just make converting \n optional. A quick fix in many languages is to just not use any newlines, though. Apr 17, 2015 at 1:53
• Image is broken. What does "set cannot can it" mean? "the actual answer you post must be under 1,000,000 bytes" is far weaker than the actual limit, because StackExchange won't allow an answer of more than 30000 characters. Apr 17, 2015 at 7:54
• @NateEldredge Worded differently, prove that a computable ordinal must be countable. Nov 13, 2017 at 21:52

main=print$f++shows f"$iterate(Z:@)Z";f="data N=Z|N:@N deriving Show;r=repeat;s Z=[];s(a:@Z)=r a;s(Z:@b)=($u b)<$>h b;s(a:@b)=do(f,c)<-h bzips a;f<$>[c:@b,a]\nh=scanl(flip(.))id.t;t(Z:@Z)=r(:@Z);t(Z:@b)=((Z:@).)<$>t b;t(a:@b)=flip(:@).(:@b)<$>s a;u Z=Z;u(Z:@b)=u b;u(a:@_)=a;g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"


329 bytes of code with ordinal ψ(ΩΩω) + 1. Uses a tree-based representation of ordinals discovered by Jervell (2005). The tree with children α, β, …, γ is denoted α :@ (β :@ (… :@ (γ :@ Z)…)). This left-to-right order agrees with Jervell, although note that Madore flips it right-to-left.

main=print$f++shows f"$iterate((:[]).T)[]";f="data T=T[T]deriving(Eq,Ord,Show);r=reverse;s[]=[];s(T b:c)=(++c)<$>scanl(++)[](b>>cycle[fst(span(>=T b)c)++[T$r d]|d<-s$r b]);g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"


224 bytes of code with ordinal Γ0 + 1. This is based on a generalization of Beklemishev’s Worm to ordinal-valued elements, which are themselves recursively represented by worms.

main=print$f++shows f"$map(:[])[0..]";f="s[]=[];s(0:a)=[a];s(a:b)=b:s(a:fst(span(>=a)b)++a-1:b);g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"  148 bytes of code with ordinal ε0 + 1. This is based on Beklemishev’s Worm. The list map(+1)α ++ [0] ++ map(+1)β ++ [0] ++ ⋯ ++ [0] ++ map(+1)γ  represents the ordinal (ωγ + ⋯ + ωβ + ωα) − 1. So the second-level outputs [0], [1], [2], [3], … represent 1, ω, ωω, ωωω, …, the first-level output represents ε0, and the initial program represents ε0 + 1. Haskell: ε0 + 999807 points main=print$f++shows f"$iterate(:@Z)Z";f="data N=Z|N:@N deriving Show;s Z=[];s(Z:@b)=repeat b;s(a:@Z)=scanl(flip(:@))Z$s a;s(a:@b)=(a:@)<$>s b;g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"


194 bytes of code with ordinal ε0 + 1.

Z represents 0, and we can prove by transfinite induction on α, then on β, that α :@ β ≥ ωα + β. So there are second-level outputs at least as big as any tower ωωω, which means the first-level output is at least ε0 and the initial program is at least ε0 + 1.

• Nice answer. Do you think you could explain it more? I like your idea of using a well-ordered type. Apr 17, 2015 at 9:42
• Specifically, which ordinals is it producing as output? Apr 17, 2015 at 22:25
• Also, do you know the Cantor's normal form of these ordinals? Nov 14, 2017 at 1:14
• @PyRulez Cantor normal form is not helpful for describing these ordinals. ψ(Ω^Ω^ω), Γ₀, and ε₀ are all epsilon numbers, so while we can write uselessly similar circular equations for their “single-level” Cantor normal form (ψ(Ω^Ω^ω) = ω^ψ(Ω^Ω^ω), Γ₀ = ω^Γ₀, ε₀ = ω^ε₀), we cannot write them as expressions where every exponent is recursively in Cantor normal form. Nov 14, 2017 at 8:54
• Hence why you should use a Veblen-like normal form for ordinal collapsing functions :p. As such, you would write Γ₀ = ψ(Ω^Ω) and ε₀ = ψ(0). Nov 14, 2017 at 14:11

Ruby, ψ0(ψX(ψM+1(ΩM+1ΩM+1))(0)) + 999663 points

Assuming I understand my program properly, my score is ψ0X(ψM+1M+1ΩM+1))(0)) + 999663 points where ψ is an ordinal collapsing function, X is the chi function (Mahlo collapsing function), and M is the first Mahlo 'ordinal'.

This program is an extension of the one I wrote on Golf a number bigger than TREE(3) and utterly trumps all of the other solutions here for now.

z=->x,k{f=->a,n,b=a,q=n{c,d,e=a;!c ?q:a==c ?a-1:e==0||e&&d==0?c:e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:n<1?9:!d ?[f[b,n-1],c]:c==0?n:[t=[f[c,n],d],n,d==0?n:[f[d,n,b,t]]]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+";"};y)};h=-1;(0..1.0/0).map{|i|puts "puts \"#{z[[i,h=[h,h,h]],1]}\""}


Try it online!

Ruby, ψ0(ψI(II)) + 999674 points

z=->x,k{f=->a,n,b=a{c,d,e,q=a;a==c ?a-1:e==0||d==0?(q ?[c]:c):e ?[[c,d,f[e,n,b],q],f[d,n,b],c,q]:[n<1?9:d&&c==0?[d]:d ?[f[c,n],d]:[f[b,n-1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..1.0/0).map{|i|puts("puts(\"#{z[h=[h,h,h,0],1]}\")")}


Try it online! (warning: it won't do much, since clearly (0..1.0/0).map{...} cannot terminate. It's how I print infinitely many programs as well.)

Ruby, ψ0(ψI(0)) + 999697 points

z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..1.0/0).map{|i|h=[h];puts|i|puts("puts(\"#{z[hz[h=[h],1]}\")")}


Try it online!

A more reasonable test program that implements (0..5).map{...} instead:

z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..5).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..5).map{|i|h=[h];puts("puts(\"#{z[h,1]}\")")}


Try it online!

Unfortunately, even with (1..1).map{...}, you will find this program to be extremely memory intensive. I mean, the length of the output exceeds things like SCG(13).

By using the simpler program, we may consider a few values:

a = value you want to enter in.
z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="x=#{f[x,k]};puts(x==0??p:"+w+"#{z[f[x,k],k*2+1]}"+w+");";y)};puts("puts(\"#{z[a,1]}\")")


Try it online!

It basically prints the same program repeatedly, in the format of:

x=...;puts(x==0??p:"...");


where the initialized x records the ordinal the program is related to, and the "..." holds the programs after x has been reduced. If x==0, then it prints

p


which is a program that prints nothing with a score of zero, hence

x=0;puts(x==0??p:"p");


has a score of 1, and

x=1;puts(x==0??p:"x=0;puts(x==0??p:\"p\");");


has a score of 2, and

x=2;puts(x==0??p:"x=1;puts(x==0??p:\"x=0;puts(x==0??p:\\\"p\\\");\");");


has a score of 3, etc., and my original program prints these programs in the format

puts("...")


where ... are the programs listed above.

My actual program actually prints these programs in the format

x=0;puts(x==0??p:"p;p;p;p;p;...");


Infinitely many times, and for values such as ω, it does something akin to

x=ω;puts(x==0??p:"(x=0 program); (x=1 program); (x=2 program); ...")


And thus, the score of the program

x=(some_ordinal);puts(x==0??p:"...")


is 1+some_ordinal, and the score of

puts("x=(some_ordinal);puts(x==0??p:\"...\")")


is 1+some_ordinal+1, and the score of

z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};puts("puts(\"#{z[some_ordinal,1]}\")")


is 1+some_ordinal+2.

Explanation of ordinals:

f[a,n,b] reduces an ordinal a.

Every natural number reduces to the natural number below it.

f[k,n,b] = k-1


[c,0,e] is the successor of c, and it always reduces down to c.

f[[c,0,e],n,b] = c


[c,d,e] is a backwards associative hyperoperation, are reduces as follows:

f[[c,d,0],n,b] = c
f[[c,d,e],n,b] = [[c,d,f[e,n,b]],f[d,n,b],c]


[0] is the first infinite ordinal (equivalent to ω) and reduces as follows:

f[[0],0,b] = [9,0,0]
f[[0],n,b] = [n,n,n]


[c] is the cth omega ordinal and reduces as follows:

f[[c],0,b] = [9,0,0]
f[[c],n,b] = [[f[b,n-1,b],f[c,n,b]],n,n]
Note the two-argument array here.


[c,d] is ψd(c) and reduces as follows:

f[[c,d],0,b] = [9,0,0]
f[[0,d],n,b] = [[d],n,n]
f[[c,d],n,b] = [[f[c,n,c],d],n,n]


[c,d,e,0] is basically the same as [c,d,e], except it enumerates over the operation [c] instead of the successor operation.

f[[c,0,e,0],n,b] = [c]
f[[c,d,0,0],n,b] = [c]
f[[c,d,e,0],n,b] = [[c,d,f[e,n,b],0],f[d,n,b],c,0]

• According to the Googology wikia, I is the first inaccessible cardinal, nor first inaccessible ordinal. Nov 14, 2017 at 1:22
• @PyRulez Yes, though it makes more sense to have an ordinal here instead of a cardinal. Usually one says that I is the ordinal that relates to the first inaccessible cardinal, just as ω relates to aleph null. Nov 14, 2017 at 1:29

Java + Brainf***, ω+999180 points

A java program that produces infinitely many Brainf*** programs, of which each produces the last as output.

Why? Because I can.

Any improvements to the Brainf*** generation part are definitely welcome.

import java.io.*;import java.util.*;import static java.lang.System.*;
class O{
static String F(String s){
String t="++++++++++++++++++++";
List<Character> c=Arrays.asList('+','-','.','<','>','[',']');
t+="[->++>++>++>+++>+++>++++>++++<<<<<<<]>+++>+++++>++++++>>++>+++++++++++>+++++++++++++";
for(int x=0,i=6;x<s.length();x++){
int d=c.indexOf(s.charAt(x)),k=d;
while(d>i){d--;t+=">";}
while(d<i){d++;t+="<";}
t+=".";i=k;
}return t;
};
static void p(String a){
int i=48;while(i<a.length()){out.println(a.substring(i-48,i));i+=48;}
out.println(a.substring(i-48));out.println();
}
public static void main(String[]a) throws Exception{setOut(new PrintStream("o.txt"));String b="";while(true)p(b=F(b));}
}

• To your taste, of course, but using the real name makes it easier to search. :) Sep 27, 2015 at 22:14
• @luserdroog Not true. Since I'm sure you know how to include multiple search terms, it's of equal difficulty to search for BF programs with different namings. Oct 1, 2015 at 16:13
• @mbomb007 are you suggesting that typing "brainfuck|brainf*ck|brainfcuk|brainf**k|brainf***|brain****|brainfu*k|..." is of equal difficulty to typing "brainfuck"? Nov 15, 2017 at 6:34
• @Sparr StackExchange uses * as a wildcard character, so just type brainf***, or brainf. All of those variations come up in the search results. codegolf.stackexchange.com/help/searching Nov 15, 2017 at 14:44
• @mbomb007 thanks, I didn't know that Nov 15, 2017 at 15:51

Literate Haskell (GHC 7.10): ω² + 999686 points.

This will serve as an example answer. Since its an example, it only makes sense to use literate programming. It won't score well though. The birdies will decrease my score, but oh well. First, let's make a helper function s. If x is an ordinal, s x = x+1, but we find unexpected uses of s.

> s x="main=putStrLn "++show x


The show function luckily does all the string sanitization for us. Its also worth making 0. Zero is not the successor of anything, but s"" will equal "main=putStrLn """, which equals 0.

> z=s""


Now we will make a function that takes n, and returns ω*n.

> o 0=z
> o n=q++"\nmain=putStrLn$unlines$map show$iterate s$o "++show(n-1)


It works by making ω*n by {ω*(n-1), ω*(n-1)+1, ω*(n-1)+2, ...}. What is this q? Why, its the reason we have a tag. q is the above helper functions so far.

> h x = x ++ show x
> q = h "s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h "


Note that only o n needs q, not any of its successors (s(o(n)), s(s(o(n)))), since they don't need the helper functions (except indirectly from o n.) Now we only have to output all of ω*n for finite n.

> main=mapM(print.o)[0..]


There we go. ω^2 Having used only 314 code character, I claim a final bonus of 999686, giving me a final score of ω^2 + 999686, which is already in cantor's normal form.

First four lines of output (0, ω, ω*2, ω*3):

"main=putStrLn \"\""
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 0"
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 1"
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 2"

• Now go write a serious solution :-) Nov 15, 2017 at 11:58

GolfScript, ε₀+1 + 999537 points

{{
{"{"lib+"}:lib~~"@++"~"+p}:output;
{{}}:nothing;
{{1{).2$+output 1}do}}:list; {{\.(2$+" iter"+@if output}}:iter;
{{1${@@(2${rep~}+++\}{;;}if~}}:rep;
{\\+}:combine;
{{\@@~}}:swap;
{{1${1$(1\${rangemap~}+[+@@[\\]]{~}/+}{;;}if}}:rangemap;
{{}+}:wrap;
}}:lib~~
nothing {iter combine list~} {rep combine} {~swap combine combine} rep combine swap combine combine {~list~} combine rangemap {~~} combine combine swap combine combine swap combine combine list~


It can probably be better, but I became too lazy to debug and prove larger ordinals.

Smaller ordinals

#ω^ω^ω
#nothing {iter combine list~} {rep combine swap combine combine list~} {rep combine swap combine combine swap combine combine list~} rep combine swap combine combine swap combine combine swap combine combine list~
#ω^ω^2
#nothing {iter combine list~} { {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~} rep combine swap combine combine swap combine combine list~
#ω^nω
#nothing {iter combine list~} 2 { {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~} rep~
#ω^ω
#nothing {iter combine list~} {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~
#ω^n
#nothing {iter combine list~} 3 {rep combine swap combine combine list~} rep~
#ω^3
#nothing {{iter combine list~} rep combine swap combine combine list~} rep combine swap combine combine list~
#ω^2
#nothing {iter combine list~} rep combine swap combine combine list~
#nω
#nothing 3 {iter combine list~} rep~
#2ω
#nothing iter combine list combine iter combine list~
#ω
#nothing iter combine list~
#finite
#2 nothing iter~


Javascript (Nashorn), ω2+999807 points

Nashorn is the Javascript engine which comes built into Java. This may also work in Rhino, but I haven't tested it in that yet.

c="(b=function(a){print(a?\"(b=\"+b+\")(\"+(a-1)+\")\":\"c=\\\"(b=function(a){print(a?'(b='+b+')'+'('+(a-1)+')':'')})(\\\";a=0;while(++a)print(c+a+\\\")\\\")\")})(";a=0;while(++a)print(c+a+")")

• Is it 2ω or ω²? Nov 13, 2017 at 2:06
• @kamoroso94 FYI 2ω = ω. Nov 13, 2017 at 19:14
• Okay, ω•2, my bad. Nov 13, 2017 at 20:03