31
\$\begingroup\$

cantor normal form

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – jimmy23013 Apr 17 '15 at 1:43
  • \$\begingroup\$ @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? \$\endgroup\$ – PyRulez Apr 17 '15 at 1:48
  • \$\begingroup\$ 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. \$\endgroup\$ – jimmy23013 Apr 17 '15 at 1:53
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Apr 17 '15 at 7:54
  • 1
    \$\begingroup\$ @NateEldredge Worded differently, prove that a computable ordinal must be countable. \$\endgroup\$ – Simply Beautiful Art Nov 13 '17 at 21:52
20
\$\begingroup\$

Haskell: ψ(ΩΩω) + 999672 points

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 b`zip`s 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.

Haskell: Γ0 + 999777 points

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.

Haskell: ε0 + 999853 points

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice answer. Do you think you could explain it more? I like your idea of using a well-ordered type. \$\endgroup\$ – PyRulez Apr 17 '15 at 9:42
  • 1
    \$\begingroup\$ Specifically, which ordinals is it producing as output? \$\endgroup\$ – PyRulez Apr 17 '15 at 22:25
  • \$\begingroup\$ Also, do you know the Cantor's normal form of these ordinals? \$\endgroup\$ – PyRulez Nov 14 '17 at 1:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Anders Kaseorg Nov 14 '17 at 8:54
  • 1
    \$\begingroup\$ Hence why you should use a Veblen-like normal form for ordinal collapsing functions :p. As such, you would write Γ₀ = ψ(Ω^Ω) and ε₀ = ψ(0). \$\endgroup\$ – Simply Beautiful Art Nov 14 '17 at 14:11
4
\$\begingroup\$

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));}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ To your taste, of course, but using the real name makes it easier to search. :) \$\endgroup\$ – luser droog Sep 27 '15 at 22:14
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Oct 1 '15 at 16:13
  • \$\begingroup\$ @mbomb007 are you suggesting that typing "brainfuck|brainf*ck|brainfcuk|brainf**k|brainf***|brain****|brainfu*k|..." is of equal difficulty to typing "brainfuck"? \$\endgroup\$ – Sparr Nov 15 '17 at 6:34
  • \$\begingroup\$ @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 \$\endgroup\$ – mbomb007 Nov 15 '17 at 14:44
  • \$\begingroup\$ @mbomb007 thanks, I didn't know that \$\endgroup\$ – Sparr Nov 15 '17 at 15:51
4
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ Now go write a serious solution :-) \$\endgroup\$ – Simply Beautiful Art Nov 15 '17 at 11:58
4
\$\begingroup\$

Ruby, ψ0X(ψM+1M+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, ψ0I(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, ψ0I(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]
\$\endgroup\$
  • \$\begingroup\$ According to the Googology wikia, I is the first inaccessible cardinal, nor first inaccessible ordinal. \$\endgroup\$ – PyRulez Nov 14 '17 at 1:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Simply Beautiful Art Nov 14 '17 at 1:29
2
\$\begingroup\$

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~
\$\endgroup\$
1
\$\begingroup\$

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+")")
\$\endgroup\$
  • \$\begingroup\$ Is it 2ω or ω²? \$\endgroup\$ – kamoroso94 Nov 13 '17 at 2:06
  • \$\begingroup\$ @kamoroso94 FYI 2ω = ω. \$\endgroup\$ – Simply Beautiful Art Nov 13 '17 at 19:14
  • \$\begingroup\$ Okay, ω•2, my bad. \$\endgroup\$ – kamoroso94 Nov 13 '17 at 20:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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