System liczb porządkowych jest systemem o liczbach nieskończonych. Wiele nieskończonych liczb. Tak wiele nieskończonych liczb, że dosłownie nie ma nieskończoności reprezentującej swoją nieskończoność. Powyższy obraz pokazuje, jak działają. Liczba porządkowa ( konstrukcja von Neumanna ) jest zbiorem poprzednich rzędnych. Na przykład 0 to pusty zbiór, 1 to zbiór {0}, 2 to zbiór {0, 1} itd. Następnie dochodzimy do ω, czyli {0, 1, 2, 3 ...}. ω + 1 to {0, 1, 2, 3 ... ω}, ω razy dwa to {0, 1, 2 ... ω, ω + 1, ω + 2 ...} i po prostu dalej że.

Twój program wyświetli zestaw rzędnych, takich jak {0, 1, 4}. Twój wynik będzie wtedy najmniejszy porządek większy niż cały porządek w twoim zestawie. Dla {0, 1, 4} wynik wyniósłby 5. Dla {0, 1, 2 ...} wynik wyniósłby ω.

Jak wyprowadzasz swoje porządki, o które pytasz. Kod oczywiście. Mianowicie, twój program wyświetli potencjalnie nieskończoną listę innych programów, w cudzysłowach, po jednym w każdym wierszu (użyj literału „\ n” do przedstawienia nowych wierszy). Program odpowiada punktacji, jak wskazano powyżej. Na przykład, jeśli wyprowadzasz

"A"
"B"
"C"

gdzie A, B i C same są poprawnymi odpowiedziami i mają wyniki {0, 1, 4}, wynik twojego programu wynosiłby 5. Zauważ, że A, B i C muszą być pełnymi programami, a nie fragmentami.

W oparciu o powyższe zasady, program, który nic nie wypisuje, ma wynik 0 (najmniej porządkowa większa niż wszystkie {} to 0). Pamiętaj też, że zbiór nie może się zawierać, poprzez aksjomat podstaw . Mianowicie, każdy zestaw (a zatem porządek) ma ścieżkę do zera. Oznacza to, że pełny quine byłby nieprawidłowy, ponieważ nie jest zbiorem.

Ponadto żaden program nie ma dostępu do zasobów zewnętrznych (własnego pliku, Internetu itp.). Również, kiedy wymienić swój wynik, umieścić Cantor normalną formę partytury obok niego, jeśli nie jest w postaci normalnej kantora już, jeśli możesz (jeśli nie, ktoś inny).

Po uwzględnieniu wszystkich powyższych faktów rzeczywista odpowiedź, którą wysyłasz, musi być mniejsza niż 1 000 000 bajtów (nie licząc komentarzy). (Ta górna granica prawdopodobnie wejdzie w grę tylko w przypadku automatycznie generowanego kodu). Ponadto możesz zwiększyć swój wynik za każdy bajt, którego nie używasz (ponieważ mamy do czynienia z nieskończonościami, prawdopodobnie będzie to brane pod uwagę tylko wtedy, gdy porządki są bardzo bliskie lub takie same). Ponownie, ten akapit dotyczy tylko wysłanej odpowiedzi, a nie tych wygenerowanych lub wygenerowanych przez wygenerowane itd.

Ma to znak quine, ponieważ może być pomocne wygenerowanie co najmniej części własnego kodu źródłowego, do użycia przy tworzeniu dużych porządków. Nie jest to jednak w żaden sposób wymagane (na przykład zgłoszenie z wynikiem 5 prawdopodobnie nie potrzebowałoby własnego kodu źródłowego).

Aby zapoznać się z opracowanym i opatrzonym komentarzem przykładem, zobacz tutaj .

Haskell: ψ (Ω ^{Ω ω} ) + 999672 punktów

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 bajtów kodu z porządkowym ψ (Ω ^{Ω ω} ) + 1. Używa drzewiastej reprezentacji rzędnych odkrytych przez Jervell (2005) . Drzewo z dziećmi a , β , ..., γ oznaczamy α :@ (β :@ (… :@ (γ :@ Z)…)). Ta kolejność od lewej do prawej zgadza się z Jervellem, choć zauważ, że Madore odwraca ją od prawej do lewej.

Haskell: Γ ₀ + 999777 punktów

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 bajty kodu z porządkiem Γ ₀ + 1. Jest to oparte na uogólnieniu robaka Beklemisheva na elementy o wartości porządkowej, które same są rekurencyjnie reprezentowane przez robaki.

Haskell: ε ₀ + 999853 punktów

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 bajtów kodu z porządkowym ε ₀ + 1. Jest to oparte na robaku Beklemisheva . Lista

map(+1)α ++ [0] ++ map(+1)β ++ [0] ++ ⋯ ++ [0] ++ map(+1)γ

oznacza liczbę porządkową (ω ^y + ⋯ + ω ^beta + ω ^a ) - 1. Tak wyjścia drugiego stopnia [0], [1], [2], [3]... reprezentują 1 ω, ω ^ω , ω ^{ω ω} , ..., wyjście pierwszego poziomu oznacza ε ₀ , a program początkowy reprezentuje ε ₀ + 1.

Haskell: ε ₀ + 999807 punktów

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 bajtów kodu z porządkowym ε ₀ + 1.

Zreprezentuje 0, i możemy udowodnić przez indukcję transfinitu na α , a następnie na β , że α :@ β≥ ω ^α + β . Są więc wyjścia drugiego poziomu co najmniej tak duże, jak każda wieża ω ^{ω ⋰ ω} , co oznacza, że ​​wyjście pierwszego poziomu wynosi co najmniej ε _0, a program początkowy to co najmniej ε ₀ + 1.

Ruby, ψ ₀ (ψ _{X (ψ M + 1 (Ω M + 1 ^{Ω M + 1} ))} (0)) + 999663 punktów

Zakładając, że dobrze rozumiem mój program, mój wynik to ψ ₀ (ψ _{X (ψ M + 1 (Ω M + 1 ^{Ω M + 1} ))} (0)) + 999663 punktów, gdzie ψ jest funkcją zwijania porządkowego, X jest chi funkcja (funkcja zwijania Mahlo), a M jest pierwszą „porządkową” Mahlo.

Ten program jest rozszerzeniem tego, który napisałem na Golfie o liczbie większej niż TREE (3) i całkowicie wyprzedza wszystkie inne rozwiązania tutaj.

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]}\""}

Wypróbuj online!

Rubin, ψ ₀ (ψ _I (I ^I )) + 999674 punktów

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]}\")")}

Wypróbuj online! (ostrzeżenie: nie zrobi wiele, ponieważ najwyraźniej (0..1.0/0).map{...}nie można go zakończyć. Tak też drukuję nieskończenie wiele programów.)

Rubin, ψ ₀ (ψ _I (0)) + 999697 punktów

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]}\")")}

Wypróbuj online!

Bardziej rozsądny program testowy, który (0..5).map{...}zamiast tego implementuje :

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]}\")")}

Wypróbuj online!

Niestety, nawet przy (1..1).map{...}tym program będzie wymagał dużej ilości pamięci. Mam na myśli, że długość wyjścia przekracza rzeczy takie jak SCG (13).

Korzystając z prostszego programu, możemy rozważyć kilka wartości:

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]}\")")

Wypróbuj online!

Zasadniczo drukuje wielokrotnie ten sam program, w formacie:

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

gdzie zainicjowany xzapisuje porządek, z którym związany jest program, i "..."przechowuje programy po xtym, jak został zmniejszony. Jeśli x==0, to drukuje

p

który jest programem, który niczego nie wypisuje z wynikiem zero

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

ma wynik 1 i

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

ma wynik 2 i

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

ma wynik 3 itd., a mój oryginalny program drukuje te programy w formacie

puts("...")

gdzie ...są programy wymienione powyżej.

Mój rzeczywisty program faktycznie drukuje te programy w formacie

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

Nieskończenie wiele razy i dla takich wartości jak ωrobi coś podobnego

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

I tak wynik programu

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

jest 1+some_ordinal, a wynik

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

jest 1+some_ordinal+1, a wynik

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]}\")")

jest 1+some_ordinal+2.

Objaśnienie porządków:

f[a,n,b]zmniejsza porządek a.

Każda liczba naturalna zmniejsza się do liczby naturalnej poniżej.

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

[c,0,e]jest następcą ci zawsze sprowadza się do c.

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

[c,d,e] jest wsteczną hiperoperacją asocjacyjną, zmniejsza się w następujący sposób:

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] jest pierwszą nieskończoną liczbą porządkową (równoważną ω) i zmniejsza się w następujący sposób:

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

[c] jest cth omega porządkową i zmniejsza w następujący sposób:

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]jest ψ _d (c) i zmniejsza się w następujący sposób:

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]jest w zasadzie taki sam jak [c,d,e], z tym wyjątkiem, że wylicza operację [c]zamiast operacji następczej.

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]

Java + Brainf ***, ω + 999180 punktów

Program Java, który produkuje nieskończenie wiele programów Brainf ***, z których każdy produkuje ostatni jako wynik.

Czemu? Bo mogę.

Wszelkie ulepszenia części generującej Brainf *** są zdecydowanie mile widziane.

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));}
}

Literate Haskell (GHC 7.10): ω² + 999686 punktów.

Będzie to służyć jako przykładowa odpowiedź. Ponieważ jest to przykład, sensowne jest jedynie stosowanie umiejętności czytania i pisania . Jednak nie zdobędzie gola. Ptaszki obniżą mój wynik, ale no cóż. Najpierw utwórzmy funkcje pomocnicze. Jeśli x jest liczbą porządkową, sx = x + 1, ale znajdujemy nieoczekiwane użycie s.

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

Funkcja show na szczęście wykonuje dla nas całą dezynfekcję łańcucha. Warto również zrobić 0. Zero nie jest następcą czegokolwiek, ale s „” będzie równy ”main = putStrLn„ ””, co równa się 0.

> z=s""

Teraz stworzymy funkcję, która przyjmuje n i zwraca ω * n.

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

Działa, tworząc ω * n przez {ω * (n-1), ω * (n-1) +1, ω * (n-1) +2, ...}. Co to jest q? Dlaczego to dlatego mamy quine tag. q to dotychczasowe funkcje pomocnicze.

> 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 "

Zauważ, że tylko na potrzeby q, nie ma żadnego z następców (s (o (n)), s (s (o (n))), ponieważ nie potrzebują one funkcji pomocniczych (z wyjątkiem pośrednio od o n.) Teraz musimy wyprowadzić wszystkie ω * n dla skończonego n.

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

No to jedziemy. ω ^ 2 Po użyciu tylko 314 znaków kodu, żądam ostatecznej premii 999686, co daje mi końcowy wynik ω ^ 2 + 999686, który jest już w normalnej formie kantora.

Pierwsze cztery wiersze wyniku (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"

GolfScript, ε₀ + 1 + 999537 punktów

{{
{"{"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~

Prawdopodobnie może być lepiej, ale stałem się zbyt leniwy, aby debugować i sprawdzać większe porządki.

Mniejsze porządki

#ω^ω^ω
#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 punktów

Nashorn to silnik JavaScript wbudowany w Javę. Może to również działać w Rhino, ale jeszcze tego nie przetestowałem.

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+")")