Kürzestes Abschlussprogramm, dessen Ausgabegröße Grahams Nummer überschreitet

37

Schreiben Sie das kürzestmögliche Programm (Länge in Byte), das die folgenden Anforderungen erfüllt:

  • keine Eingabe
  • Ausgabe ist auf Standard
  • Die Ausführung wird schließlich abgebrochen
  • Die Gesamtzahl der ausgegebenen Bytes übersteigt die Anzahl von Graham

Nehmen Sie an, dass Programme bis zur "normalen" Beendigung auf einem idealen Computer 1 ausgeführt werden , der auf unbegrenzte Ressourcen zugreifen kann, und dass die allgemeinen Programmiersprachen bei Bedarf geändert werden (ohne die Syntax zu ändern), um dies zu ermöglichen. Aufgrund dieser Annahmen können wir dies eine Art Gedankenexperiment nennen.

Hier ist ein 73-Byte-Ruby-Programm, das fω + 1 (99) in der schnell wachsenden Hierarchie berechnet :

f=proc{|k,n|k>0?n.times{n=f[k-1,n]}:n+=1;n};n=99;n.times{n=f[n,n]};puts n

1 BEARBEITEN: Nehmen wir genauer an, wir nehmen ein vorhandenes System und ändern es nur, um keine Obergrenze für die Speichergröße zu haben (aber es ist immer endlich). Die Ausführungszeiten von Anweisungen werden nicht angenommen , geändert werden, aber die Maschine angenommen wird ideal in sein , dass es keine Obergrenze für seine Betriebslebensdauer hat.

res
quelle
Dies bringt meine Tetrationsfrage auf eine ganz neue Ebene!
MrZander
1
Es gab einmal einen ähnlichen Programmierwettbewerb namens Bignum Bakeoff. Einige der Einträge sind sehr interessant; Die Ergebnisse sind hier: djm.cc/bignum-results.txt
Danny Chia

Antworten:

11

GolfScript ( 49 47 Zeichen)

4.,{\):i\.0={.0+.({<}+??\((\+.@<i*\+}{(;}if.}do

Ausführliche Informationen finden Sie unter Lebensdauer eines Wurms . Kurz gesagt, dieses druckt eine Zahl größer als f & ohgr; & ohgr; (2).

Peter Taylor
quelle
f_ (ω ^ ω) (2) ist ungefähr so ​​groß wie g_ (f_8 (8)), also nicht so übertrieben, wie dieser Ausdruck implizieren würde.
Simply Beautiful Art
21

Haskell, 59 57 55 63

(f%s)1=s;(f%s)n=f.(f%s)$n-1
main=print$((flip((%3)%(3^))3)%4)66

So funktioniert es: %Nimmt einfach eine Funktion und setzt sie n-1mal auf s; dh %3nimmt eine Funktion fund gibt eine Funktion , ndass es die Anwendung ist gleich fzu 3 - n-1mal in einer Reihe. Wenn wir die Anwendung dieser Funktion höherer Ordnung iterieren, erhalten wir eine schnell wachsende Folge von Funktionen - beginnend mit der Potenzierung ist es genau die Folge von Knuth-Pfeil-Waldgrößen:
((%3)%(3^))1 n = (3^)n     = 3ⁿ = 3↑n
((%3)%(3^))2 n = ((3^)%3)n = (3↑)ⁿ⁻¹ $ 3 = 3↑↑n
((%3)%(3^))3 n = (((3^)%3)%3)n = (3↑↑)ⁿ⁻¹ $ 3  = 3↑↑↑n
und so weiter. ((%3)%(3^))n 3ist 3 ↑ⁿ 3, was in der Berechnung zu Grahams Zahl erscheint. Sie müssen nur noch die Funktion komponieren(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3mehr als 64 Mal, zusätzlich zu 4 (die Anzahl der Pfeile, mit denen die Berechnung beginnt), um eine Zahl zu erhalten, die größer als Grahams Zahl ist. Es ist offensichtlich, dass der Logarithmus (was für eine lahmende langsame Funktion das ist!) g₆₅Immer noch größer als g₆₄=Gist. Wenn wir also diese Zahl drucken, überschreitet die Ausgabelänge G.

hörte auf, sich gegen den Uhrzeigersinn zu drehen
quelle
Wenn ich das mit testeprint$((flip((%3)%(3*))3)%2)1 , gibt es einen Laufzeitfehler - kannst du sagen warum? Dies 2ist erfolgreich, wenn auf geändert wird 1(Ausgabe ist 81).
Res
Oh ... ideone scheint eine 32-Bit-Version auszuführen, so dass es Intschnell zu einem Überlauf kommt . Auf einem 64-Bit-System verbraucht das zu viel Speicher, um reproduziert zu werden, lässt es aber trotzdem nicht zu G. Ich benötige den IntegerTyp (big-int) , kann ihn also nicht verwenden !!. Warten Sie ...
nicht mehr gegen den Uhrzeigersinn am
Es wurde jetzt behoben, musste explizite Rekursion verwenden, um zu implementieren %.
drehte nicht mehr gegen den Uhrzeigersinn am
Ich finde ((%3)%(3*))2 ntatsächlich wächst schneller als Sie sagen (eine gute Sache), aber mein Haskell-Fu ist nicht ausreichend zu verstehen, warum. Denn n = 0, 1, 2, ...statt zu geben 3, 3^3, 3^(3^3), ..., gibt es 3, 3^(3+1), 3^((3^(3+1))+1), ....
Res
Wie gesagt: " ((%3)%(3*))n 3ist größer als 3 ↑ⁿ 3". Oder meinst du etwas anderes? Wie auch immer, ich habe die Definition so geändert, dass es nur um Gleichheit geht (zumindest denke ich, dass es zu faul ist, dies jetzt zu überprüfen ...), anstatt größer zu sein. Und wenn Sie ändern , 66um 65es tatsächlich produziert Gselbst, ist das nicht schön?
drehte sich nicht mehr gegen den Uhrzeigersinn am
5

Pyth , 29 28 Bytes

M?*GHgtGtgGtH^ThH=ZTV99=gZTZ

Definiert ein Lambda für die Hyperoperation und ruft es rekursiv auf. Wie die Definition für Grahams Zahl, aber mit größeren Werten.

Dies:

M?*GHgtGtgGtH^3hH

Definiert ein Lambda, das ungefähr der Python entspricht

g = lambda G, H:
  g(G-1, g(G, H-1)-1) if G*H else 3^(H+1)

Dies ergibt die Hyperoperationsfunktion, g (G, H) = 3 ↑ G + 1 (H + 1).
So ist beispielsweise g (1,2) = 3 ↑ 2 3 = 7.625.597.484.987, was Sie hier testen können .

V<x><y>beginnt eine Schleife, die den Körper führt, y, xmal.
=gZTist hier der Körper der Schleife, was äquivalent zu istZ=g(Z,10)

Der Code:

M?*GHgtGtgGtH^3hH=Z3V64=gZ2)Z

Sollte die Hyperoperation rekursiv über 64-mal aufrufen und dabei Grahams Nummer angeben.

In meiner Antwort habe ich jedoch die einzelnen Ziffern durch T10 ersetzt und die Rekursionstiefe auf 99 erhöht. Bei Verwendung der Graham-Array-Notation ist Grahams Zahl [3,3,4,64] und meine Programm gibt das größere [10,11,11,99] aus. Ich habe auch das entfernt ), das die Schleife schließt, um ein Byte zu speichern, so dass jeder nachfolgende Wert in den 99 Iterationen gedruckt wird.

KSmarts
quelle
3

Python (111 + n), n = Länge (x)

Obwohl dieses Programm nicht so kurz ist wie das Ruby-Programm des Antwortenden, werde ich es trotzdem posten, um diese Möglichkeit auszuschließen.

Es verwendet die Ackermann-Funktion und ruft die Ackermann-Funktion auf, wobei m und n die Werte eines anderen Aufrufs der Ackermann-Funktion sind.

Das ist wahrscheinlich größer als Grahams Zahl, aber ich bin mir nicht sicher, weil niemand die genaue Länge weiß. Es kann leicht erweitert werden, wenn es nicht größer ist.

x=999
b='A('*x+'5,5'+')'*x
def A(m,n):n+1 if m==0 else A(m-1,A(m,n-1)if n>0 else 1)
exec('print A('%s,%s')'%(b,b))
beary605
quelle
auf stdout ausgeben? außerdem brauchst du eine returnaussage oder eine lambda.
Stand
7
Auch wenn A (m, n) einen einzelnen Wert zurückgibt, fehlt A (A (5,5)) dann kein Argument? ... Dies ist das Problem bei einer solchen Herausforderung: Es fordert die Leute auf, ihren Code nicht zu testen, da ein vollständiger Durchlauf rein theoretisch ist.
Brotkasten
Wenn Sie Ihre letzte Zeile durch ersetzen exec'x=A(x,x);'*x;print x, ist das Programm in Ordnung und die Ausgabe ist ungefähr f_ (ω + 1) (x) (vorausgesetzt, der Ackermann-Funktionscode ist korrekt), was sogar für x = 99 mehr als G Bytes hat, sagen wir . (In meinem Ruby - Programm, f[m,n]ist eine Version A(m,n).)
res
@breadbox - Ein guter Punkt ... Bei theoretischen Fragen wie diesen müssen wir sicherstellen, dass ein Programm für Testfälle mit kleinen (dh nicht theoretischen) Parametern geeignet ist, die sich eindeutig verallgemeinern lassen, um eine korrekte Antwort zu erhalten.
Res
1
Es ist länger, aber wenn Sie evalstattdessen verwenden möchten exec, könnte Ihre letzte Zeile sein f=lambda x:A(x,x);print eval('f('*x+'x'+')'*x). Außerdem muss Ihr Def von A (m, n) gemäß dem Kommentar des Boothby korrigiert werden.
Res
2

Ruby, 54 52 50 Bytes

f=->b{a*=a;eval"f[b-1];"*b*a};eval"f[a];"*a=99;p a

Ruby, 85 81 76 71 68 64 63 59 57 Bytes

f=->a,b=-a{eval"a*=b<0?f[a,a]:b<1?a:f[a,b-1];"*a};p f[99]

Ziemlich schnell wachsende Hierarchie mit f (a + 1)> fω + 1 (a).


Ruby, 61 Bytes

f=->a,b=-a{a<0?9:b==0?a*a:f[f[a-1,b],b>0?b-1:f[a,b+1]]};f[99]

Grundsätzlich eine Ackermann-Funktion mit einem Dreh.


Rubin, 63 59 Bytes

n=99;(H=->a{b,*c=a;n.times{b ?H[[b-1]*n*b+c]:n+=n}})[n];p n

Ein weiterer Ruby, 74 71 Bytes

def f(a,b=a)a<0?b:b<0?f(a-1):f(a-1,f(a,b-1))end;n=99;n.times{n=f n};p n

Grundsätzlich funktioniert Ackermann 99 mal für sich.

Einfach schöne Kunst
quelle
0

Python: 85

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*99
exec'f('*64+'3'+',3)'*64

Was vielleicht auf 74 +length(X) verkürzt werden könnte :

f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*int('9'*X)
f(3,3)

Wo Xist eine geeignete große Zahl, so dass die resultierende Hyperoperation 3, 3größer ist als Grahams Zahl (wenn diese Zahl kleiner ist als 99999999999dann wird ein gewisses Byte gespeichert).


Hinweis: Ich gehe davon aus, dass der Python-Code auf dem interaktiven Interpreter ausgeführt wird, daher wird das Ergebnis auf stdout ausgegeben. Andernfalls fügen Sie 9jeder Lösung für den Aufruf von Bytes hinzu print.

Bakuriu
quelle
2
Ihre 74-Byte-Lösung erzeugt keine Ausgabe, die fast groß genug ist.
Lirtosiast
0

Javascript, 83 Bytes

Eine weitere Ackermann-Funktionslösung.

(function a(m,n,x){return x?a(a(m,n,x-1),n,0):(m?a(m-1,n?a(m,n-1):1):n+1)})(9,9,99)
SuperJedi224
quelle
0

JavaScript, 68 Byte, jedoch nicht konkurrenzfähig für die Verwendung von ES6

a=(x,y)=>y?x?a(a(x-1,y)*9,y-1):a(9,y-1):x;b=x=>x?a(9,b(x-1)):9;b(99)

a Die Funktion ähnelt der Aufwärtspfeilnotation mit der Basis 9.

       /a(a(x-1,y)*9,y-1)  x>0, y>0
a(x,y)=|a(9,y-1)           x=0, y>0
       \x                  y=0

bFunktion ist: b (x) = b x (9).

b(99)ist ~ fω + 1 (99), verglichen mit Grahams Zahl < fω + 1 (64).

Naruyoko
quelle
Wenn Sie dieses Wettbewerbsverbot markiert haben, weil die Sprache neuer als die Frage ist, müssen Sie dies nicht mehr tun
Jo King,