Wenn ein Programm beendet wird und niemand es sieht, hört es dann auf?

99

Es ist Zeit, sich der Wahrheit zu stellen: Wir werden nicht für immer hier sein, aber zumindest können wir ein Programm schreiben, das die Menschheit überlebt, auch wenn sie bis zum Ende der Zeit kämpft.

Ihre Aufgabe ist es, ein Programm zu schreiben, dessen erwartete Laufzeit die verbleibende Zeit bis zum Ende des Universums überschreitet.

Sie können davon ausgehen, dass:

  • Das Universum wird in 10 1000 Jahren an Entropie sterben .
  • Dein Computer:
    • Wird das Universum überleben, weil es aus Unobtainium besteht .
    • Hat unendlich Speicher / Stapel / Rekursionslimit.
    • Sein Prozessor hat eine begrenzte Geschwindigkeit.

Sie müssen zeigen, dass Ihr Programm beendet wird (sorry, keine Endlosschleifen) und die erwartete Laufzeit berechnen.

Es gelten die Standardlücken .

Dies ist eine Code-Golf-Herausforderung, daher gewinnt der kürzeste Code, der die Kriterien erfüllt.

EDIT :

Leider wurde festgestellt (30 Minuten später), dass das Unwahrscheinlichkeitsfeld von Unobtainium die interne Uhr des Computers stört und ihn unbrauchbar macht. So stoppen zeitbasierte Programme sofort. (Wer würde ein Programm verlassen, das nur als lebendiges Vermächtnis wartet?).

Der Computerprozessor ähnelt dem Intel i7-4578U. Eine Möglichkeit, die Laufzeit zu messen, besteht darin, Ihr Programm auf einem ähnlichen Computer mit einer geringeren Eingabe auszuführen (ich hoffe) und die Laufzeit zu extrapolieren.


Podium

#CharsLanguageUpvotes        Author        
1    5      CJam              20       Dennis                  
2    5      J                      5         algorithmshark      
3    7      GolfScript       30       Peter Taylor          
4    9     Python             39       xnor                      
5    10   Matlab             5         SchighSchagh      

* Upvotes am 31.08

kb_sou
quelle
40
Ich war versucht, ein [langsamster Code] -Tag für diese Frage zu erstellen. : P
Türklinke
5
Ein Bogosort würde nicht funktionieren, da es zwar unendlich unwahrscheinlich ist, dass er niemals fertig wird, aber möglicherweise unendlich viel Zeit benötigt, um fertig zu werden. Es gibt jedoch viele schreckliche reguläre Ausdrücke auf NFA-Basis, die das Kriterium "Werden beendet, aber nicht bevor das Universum tot ist" erfüllen könnten.
DavidO
49
Dein Titel sollte ein T
-Shirt
4
Schöne Frage, aber sollte es nicht ein Beliebtheitswettbewerb sein?
IazertyuiopI

Antworten:

34

CJam, 5 Bytes

0{)}h

Wie es funktioniert

 0   " Push 0.                                 ";
 {   "                                         ";
   ) " Increment the Big Integer on the stack. ";
 }h  " Repeat if the value is non-zero.        ";

Dieses Programm wird angehalten, wenn der Heap die Big Integer nicht mehr speichern kann, was auf einem modernen Desktop-Computer in Kürze nicht mehr der Fall sein wird.

Die Standard-Heap-Größe beträgt 4.179.623.936 Byte auf meinem Computer (Java 8 auf Fedora). Es kann mit auf einen beliebigen Wert erhöht werden -Xmx, so dass die einzige reale Grenze der verfügbare Hauptspeicher ist.

Zeitpunkt des Todes

Unter der Annahme, dass der Interpreter x Speicherbits benötigt, um eine nicht negative ganze Zahl von weniger als 2 x zu speichern , müssen wir bis zu 2 8 × 4.179.623.936 = 2 33.436.991.488 zählen . Bei einem Inkrement pro Taktzyklus und meinem Core i7-3770 (3,9 GHz mit Turbo) dauert dies 2 33.436.991.488 ÷ 3.400.000.000> 10 10.065.537.393 Sekunden, was über 10 10.065.537.385 Jahren liegt.

Dennis
quelle
14
Ich glaube nicht, dass Sie sich auf endliche Ressourcen verlassen können, da die Frage lautet "Ihr Computer verfügt über ein unbegrenztes Speicher- / Stapel- / Rekursionslimit".
Greg Hewgill
4
Unendlicher Speicher !=Unendliche Datentypen. Wenn ich ein Terabyte RAM habe, reicht eine 8-Bit-Ganzzahl ohne Vorzeichen immer noch bis zu 255.
wchargin
6
@GregHewgill: Mit unbegrenzten Ressourcen können Sie die maximale Größe des Java- Heapspeichers auf einen beliebigen Wert erhöhen , der jedoch immer endlich ist.
Dennis
2
@Dennis, aber fügen Sie dann jedes Mal eine Zeile durch die Schleife hinzu, um die Größe des Heapspeichers zu verdoppeln. Es ist eine lustige Sache über Unendlichkeiten :-)
Carl Witthoft
9
@CarlWitthoft: Das kann man nicht aus dem Programm heraus machen.
Dennis
62

JavaScript, 39

(function f(x){for(;x!=++x;)f(x+1)})(0)

Erläuterung

Da JavaScript große Ganzzahlen nicht genau darstellt, wird die Schleife bei einem Treffer for(;x!=++x;)beendet .x9007199254740992

Der Body der for-Schleife wird Fib(9007199254740992) - 1mal ausgeführt , wobei Fib(n)es sich um die n-te Fibonacci-Zahl handelt.

Nach dem Testen weiß ich, dass mein Computer weniger als 150.000 Iterationen pro Sekunde ausführt. In Wirklichkeit würde es viel langsamer laufen, da der Stapel sehr groß werden würde.

Das Programm benötigt also mindestens (Fib(9007199254740992) - 1) / 150000Sekunden, um ausgeführt zu werden. Ich habe nicht rechnen können, Fib(9007199254740992)weil es so groß ist, aber ich weiß, dass es viel größer als 10 1000 * 150 000 ist.

BEARBEITEN: Wie in den Kommentaren vermerkt, Fib(9007199254740992)ist das ca. 4,4092 * 10 1882393317509686 , was in der Tat groß genug ist.

Peter Olson
quelle
9
Da fib(n)dies angenähert werden kann phi^n, können wir log((sqrt(5) + 1)/2)*9007199254740992berechnen, um wie viele Stellen fib(9007199254740992)es sich handelt 1.8823933*10^15.
Overactor
11
@overactor ist laut Wolfram Alpha Fib(9007199254740992)(mit Endlosformular phi) ungefähr 4.4092... * 10^1882393317509686. Berechnung
Brian S
1
Ein wachsender Stack verringert die CPU-Geschwindigkeit nicht ... es sei denn, Sie berücksichtigen die begrenzte Adresszeilenbreite / unbegrenzte Adressbreite (in diesem Fall ist die Adresslänge bei angemessener Codierung immer noch linear) oder sogar die physischen Einschränkungen in Bezug auf die Speicherkapazität und die Lichtgeschwindigkeit (in diesem Fall ist die Verlangsamung des Adresswerts unter der Annahme einer räumlichen Speicherung von Bedeutung; selbst die DNA-Werte der Datendichte summieren sich schließlich, selbst wenn Sie einen platzsparenden Direktzugriff verwalten)
John Dvorak
1
@JamesKhoury Nein, die Funktion, die Sie gerade geschrieben haben, entspricht for(x=0;x!=++x;)9007199254740992 Mal und wird nur iteriert.
Peter Olson
4
@ SylvainLeroux Eine Architektur mit unendlich viel RAM würde wahrscheinlich nur den Heap und den Stack verschachteln und beide nach oben wachsen lassen.
John Dvorak
47

Python (9)

9**9**1e9

Dies hat mehr als 10 ** 10000000 Bits, so dass die Berechnung uns weit über den Hitzetod hinausbringen sollte.

Ich habe überprüft, dass dies für größere, aber immer noch vernünftige Werte immer mehr Zeit in Anspruch nimmt, damit es nicht nur vom Interpreter optimiert wird.

Bearbeiten: Golf zwei Zeichen durch Entfernen von Eltern dank @ user2357112. Bis dass Python aufeinanderfolgende Exponenten als Power Tower behandelt.

xnor
quelle
4
OverflowError: (34, 'Ergebnis zu groß')
apple16
93
@ apple16 Vielleicht auf deinem Computer, aber meiner hat ein "unendliches Speicher- / Stapel- / Rekursionslimit".
Xnor
64
Es ist in Ordnung, Jungs. Ich ließ es letztes Universum ...82528057365719799011536835265979955007740933949599830498796942400000000009laufen und bekam (2,6 * 10 ^ 954242509 Stellen weggelassen, um einen Zusammenbruch des Schwarzen Lochs zu vermeiden ). Sie sollten wirklich auf Unobtanium upgraden.
Xnor
10
Die Potenzierung ist rechtsassoziativ, sodass Sie die Klammern fallen lassen können.
user2357112
10
Es ist erwähnenswert, dass 9**9**9e9es genauso kurz ist und etwas mehr Universumslänge benötigt, um berechnet zu werden. Außerdem sieht es ein bisschen besser aus.
Abarnert
35

GolfScript ( 12 7 Zeichen)

9,{\?}*

Dies berechnet und druckt 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Um es (ohne Rücksicht auf die Berechnung) in 10 ^ 1000 Jahren ~ = 10 ^ 1007,5 Sekunden zu drucken, müssen ungefähr 10 ^ (10 ^ 10 ^ 10 ^ 183230 - 10 ^ 3) Stellen pro Sekunde gedruckt werden.

Peter Taylor
quelle
22
Aber es wird lange davor mit einer Meldung "Drucker hat kein Papier mehr" aufhören ...
Floris
1
@ Floris wer zum Teufel nutzt heutzutage physische Medien?
John Dvorak
3
@JanDvorak, ich habe gerade angenommen, dass Floris und die 7 Leute, die ihn geworben haben, aus der Generation meines Großvaters stammen, als die gesamte Ausgabe auf Endlospapier erfolgte.
Peter Taylor
2
@PeterTaylor - vielleicht nicht ganz so alt, aber ich bin alt genug, um mich daran zu erinnern, "Batch-Jobs" an "den Computer" gesendet zu haben (in den Tagen, als es keinen Zweifel gab, bei einer Studentenbevölkerung von 20.000, welchen Computer du meintest), und Abholung des Ausdrucks am nächsten Tag. Sie (und 7 andere) haben richtig vermutet, dass dies ein Versuch des Humors war, keine ernsthafte Kritik an Ihrem ausgezeichneten und lächerlich kurzen Drehbuch.
Floris
35

Marbelous 68 66 Bytes

}0
--@2
@2/\=0MB
}0@1\/
&0/\>0!!
--
@1
00@0
--/\=0
\\@0&0

Marbelous ist eine 8-Bit-Sprache mit Werten, die nur durch Murmeln in einer Rube Goldberg-ähnlichen Maschine dargestellt werden. Dies war also nicht sehr einfach. Dieser Ansatz entspricht in etwa dem folgenden Pseudocode:

function recursiveFunction(int i)
{
    for(int j = i*512; j > 0; j--)
    {
        recursiveFunction(i - 1);
    }
}

Da der Maximalwert 256 ist (dargestellt durch 0 im Marbleous-Programm, das an verschiedenen Stellen unterschiedlich gehandhabt wird), wird recursiveFunction (1) aufgerufen, 256!*512^256wovon insgesamt ungefähr gleich sind 10^1200, was leicht genug ist, um das Universum zu überleben.

Marbelous hat keinen sehr schnellen Interpreter, es scheint, als könne er 10^11Aufrufe dieser Funktion pro Jahr ausführen , was bedeutet, dass wir eine Laufzeit von 10^1189Jahren haben.

Weitere Erklärung der Marmorplatte

00@0
--/\=0
\\@0&0

00ist ein Sprachliteral (oder ein Marmor), das hexadezimal dargestellt wird (also 0). Diese Murmel fällt auf die --, die jede Murmel um 1 dekrementiert (00 wird umbrochen und in FF oder 255 in Dezimalzahl umgewandelt). Der Marmor mit jetzt dem Wert FF fällt auf den, \\der ihn eine Spalte nach rechts nach unten schiebt @0. Dies ist ein Portal, das den Marmor zum anderen @0Gerät teleportiert . Dort landet der Marmor auf dem /\Gerät, bei dem es sich um einen Duplikator handelt. Er platziert eine Kopie des Marmors auf der --linken Seite (dieser Marmor wird zwischen den Portalen weitergeschleift und bei jeder Schleife dekrementiert) und eine Kopie auf der =0rechten Seite.=0vergleicht den Marmor mit dem Wert Null und lässt den Marmor fallen, wenn er gleich ist, und schiebt ihn nach rechts, wenn nicht. Wenn der Marmor den Wert 0 hat, landet er auf &0einem Synchronisator, den ich später noch erläutern werde.

Alles in allem beginnt dies einfach mit einer Murmel mit dem Wert 0 in einer Schleife und dekrementiert sie, bis sie wieder den Wert 0 erreicht. Anschließend wird diese Murmel mit dem Wert 0 in einen Synchronizer gelegt und die Schleife wird gleichzeitig fortgesetzt.

}0@1
&0/\>0!!
--
@1

}0Ist ein Eingabegerät, wird anfangs die n-te (Basis 0) Befehlszeileneingabe beim Aufrufen des Programms in jedes }nGerät eingefügt. Wenn Sie dieses Programm also mit der Befehlszeileneingabe 2 aufrufen, wird dies durch einen 02-Wert ersetzt }0. Diese Murmel fällt dann in das &0Gerät, ein weiterer Synchronisierer, &nSynchronisierer halten Murmeln, bis auch alle anderen Entsprechungen &nabgelegt sind. Der Marmor wird dann dekrementiert, teleportiert und dupliziert, ähnlich wie in der zuvor erläuterten Schleife. Die richtige Kopie wird dann mit zero ( >0) auf Ungleichheit überprüft. Wenn sie nicht 0 ist, fällt sie durch. Wenn es 0 ist, wird es nach rechts gedrückt und landet auf !!, wodurch das Board beendet wird.

Okay, bis jetzt haben wir eine Schleife, die kontinuierlich von 255 auf 0 herunterzählt und eine andere, ähnliche Schleife (gespeist von der Befehlszeileneingabe) jedes Mal einmal ausführen lässt, wenn sie 0 trifft. Wenn diese zweite Schleife n-mal ausgeführt wurde (maximal 256) ) Das Programm wird beendet. Das sind also maximal 65536 Runden der Schleife. Nicht annähernd genug, um das Universum zu überleben.

}0
--@2
@2/\=0MB

Dies sollte vertraut aussehen, die Eingabe wird einmal dekrementiert, dann wird dieser Wert in einer Schleife verschoben und kopiert (beachten Sie, dass die Murmel nur einmal dekrementiert wird, nicht bei jedem Durchlauf der Schleife). Es wird dann auf Gleichheit mit 0 geprüft und wenn es nicht Null ist, landet es auf MB. Dies ist eine Funktion in Marbelous, jede Datei kann mehrere Karten enthalten und jede Karte ist eine Funktion, jede Funktion muss durch Voranstellen des Gitters mit benannt werden :[name]. Jede Funktion mit Ausnahme der ersten Funktion in der Datei, die einen Standardnamen hat: MB. Diese Schleife ruft also die Hauptplatine fortlaufend erneut mit dem Wert auf, n - 1wobei n der Wert ist, mit dem diese Instanz der Funktion aufgerufen wurde.

Warum also n*512?

Nun, die erste Schleife läuft in 4 Ticks (und 256-mal) und die zweite Schleife läuft n-mal, bevor das Board endet. Dies bedeutet, dass das Board ungefähr n*4*256Ticks läuft . Die letzte Schleife (die den rekursiven Funktionsaufruf ausführt) ist kompakter und läuft in 2 Ticks, was bedeutet, dass sie die Funktionszeiten aufruft n*4*256/2 = n*512.

Welche Symbole haben Sie nicht erwähnt?

\/ ist ein Mülleimer, mit dem Murmeln vom Brett entfernt werden. Auf diese Weise wird sichergestellt, dass verworfene Murmeln andere Murmeln, die eine Runde durchlaufen, nicht stören und verhindern, dass das Programm beendet wird.

Bonus

Da Murmeln, die vom Boden einer Marmorplatte fallen, an STDOUT ausgegeben werden, druckt dieses Programm während der Ausführung eine Vielzahl von ASCII-Zeichen.

Überakteur
quelle
2
Tolle Erklärung, danke!
Beta Decay
2
Wow, das ist eine geniale Idee! Die Marmorsprache macht so viel Spaß!
Rubik
2
+1 Genau das, was ich sehen wollte. Eine verrücktere Sprache als BrainFuck :) Gibt es eine Website mit Tutorial und mehr Infos dazu? (Der Titellink scheint weniger doc als Ihre Antwort zu haben)
Sylwester
2
@ Sylwester, ich bin froh, dass es Ihnen gefällt. Marbelous befindet sich derzeit noch in der Entwicklung. Wir gehen jedoch davon aus, dass es in naher Zukunft einen stabileren Zustand haben wird. An diesem Punkt werden Tutorials, umfangreichere Dokumentationen, Standardbibliotheken und hoffentlich ein Online-Dolmetscher bereitgestellt Folgen.
Overactor
21

Perl, 66 58 Zeichen

sub A{($m,$n)=@_;$m?A($m-1,$n?A($m,$n-1):1):$n+1;}A(9,9);

Das Obige ist eine Implementierung der Ackermann-Péter-Funktion . Ich habe keine Ahnung, wie groß A (9,9) ist, aber ich bin mir ziemlich sicher, dass die Bewertung erstaunlich lange dauern wird.

Greg Hewgill
quelle
5
+1 ... Ich habe versucht, eine Sprache mit integrierter Ackermann-Funktion zu finden, habe dies jedoch nicht getan, bevor meine Geduld erschöpft war. : D
Martin Ender
3
$n?A($m-1,A($m,$n-1)):A($m-1,1)Ermöglicht eine einfache 8-Zeichen-Einsparung durch Drücken des ternären Operators.
Peter Taylor
3
Ich bin mir ziemlich sicher, dass die Anzahl der Stellen in A (9,9) größer ist als das Volumen des beobachtbaren Universums, gemessen in kubischen Planck-Längen.
Kasperd
6
@kasperd Das ist eine ziemlich massive Untertreibung. Das Volumen des beobachtbaren Universums liegt nur in der Größenordnung von 10 ^ 184 Planck-Volumina. Zum Vergleich: Die Zahl enthält etwa 10 ^ 19700 Stellen, die die Anzahl der Stellen in A (4,4) beschreiben, was wiederum im Vergleich zu A (9,9) unverständlich klein ist.
user19057
3
@ user19057 Es klingt so, als würde man Kasperds Behauptung "massive Untertreibung" als massive Untertreibung bezeichnen. : P
Nicu Stiurca
20

MATLAB, 58 52 Zeichen

Wir brauchen mindestens eine Rechenlösung mit endlicher Genauigkeit, also:

y=ones(1,999);while y*y',y=mod(y+1,primes(7910));end

x = Einsen (1.999); y = x; während jedes (y), y = mod (y + x, Primzahlen (7910)); Ende

( danke an @DennisJaheruddin für das Abschalten von 6 Zeichen )

Die Anzahl der zur Vervollständigung erforderlichen Zyklen ergibt sich aus dem Produkt der ersten 999 Primzahlen. Da die überwiegende Mehrheit von diesen weit über 10 liegt, würde die Zeit, die zur Realisierung der Konvergenz benötigt wird, Hunderte oder Tausende von Größenordnungen über der Mindestzeitgrenze liegen.

COTO
quelle
+1 Es hat eine Weile gedauert, bis ich gesehen habe, was Sie dort machen. Nett!
Festpunkt
+1 CRT, nicht wahr?
Fehler
Nizza, ich denke, einige Zeichen können wie folgt gespeichert werden: y = Einsen (1.999), während y * y ', y = Mod (y + 1, Primzahlen (7910)); Ende
Dennis Jaheruddin
@ TennisJaheruddin: Geniale Verkürzung. Ich werde aktualisieren.
COTO
Obwohl es nicht mehr die gleiche Lösung ist, sollte dies immer noch ähnlich und wieder etwas kürzer sein:p=1:9e9;y=p;while+y*y',y=mod(y+1,p),end
Dennis Jaheruddin
19

Mathematica, 25 - 19 Bytes

Diese Lösung wurde veröffentlicht, bevor Zeitfunktionen disqualifiziert wurden.

While[TimeUsed[]<10^10^5]

TimeUsed[]Gibt die Sekunden seit dem Start der Sitzung zurück, und Mathematica verwendet Typen mit willkürlicher Genauigkeit. Ein Jahr hat ungefähr 10 7 Sekunden, also sollte das Warten auf 10 10000 Sekunden ausreichen.

Kürzere / einfachere (/ gültige) Alternative:

For[i=0,++i<9^9^9,]

Lass uns stattdessen einfach zählen. Wir müssen ein bisschen weiter zählen, weil wir in einer Sekunde eine ganze Menge Inkremente machen können, aber das höhere Limit kostet eigentlich keine Charaktere.

Technisch könnte ich in beiden Lösungen eine viel niedrigere Grenze verwenden, da das Problem keine minimale Prozessorgeschwindigkeit angibt.

Martin Ender
quelle
Liebe es! Diese Antwort ließ mich tatsächlich mit einem breiten Lächeln auf meinem Gesicht laut lachen.
Todd Lehman
1
Tut mir leid, aus Gründen der Kreativität musste ich zeitbasierte Lösungen herausschneiden (wie Ihre erste). Bitte hasse mich nicht. :)
kb_sou
5
@kbsou Nun, ich habe es mit meinem anderen geschlagen, also ist es mir eigentlich egal. Aber ansonsten ist es nicht cool, Antworten nachträglich für Regeländerungen zu disqualifizieren. ;)
Martin Ender
1
Ist Mathematica wirklich so langsam, dass das Rechnen 9^9^9mehr als 10^1000Jahre dauert ? Ich schätze, dass die 9^9^9Nutzung meines 1,3-GHz-U7300 bcweniger als 6 Monate dauern würde. (Basierend auf der Extrapolation der Zeit zu berechnen 9^200000und 9^400000.)
Kasperd
2
@ArtOfCode Mathematica verwendet Typen mit beliebiger Genauigkeit, sodass tatsächlich versucht wird, den richtigen Wert zu ermitteln.
Martin Ender
16

Python 3 - 49

Dies ist nützlich: Mit der unendlichen Gregory-Leibniz-Reihe wird der Pi mit beispielloser Genauigkeit berechnet.

Nur für den Fall, dass Sie sich wundern, schleift dieses Programm 10**10**10**2.004302604952323mal.

sum([4/(i*2+1)*-1**i for i in range(1e99**1e99)])

Beliebige Genauigkeit: 78

from decimal import*
sum([Decimal(4/(i*2+1)*-1**i)for i in range(1e99**1e99)])

Bildquelle

Der unendliche Atem

Aufgrund der umfangreichen Berechnungen 1e99**1e99dauern die Iterationen knapp 1e99**1e99Jahre. Jetzt (1e99**1e99)-1e1000macht das kaum noch einen Unterschied. Das bedeutet, dass dieses Programm viel länger läuft als der Tod unseres Universums.

Wiedergeburt

Jetzt schlagen Wissenschaftler vor, dass 10**10**56 yearsdas Universum aufgrund von Quantenschwankungen oder Tunneleffekten wiedergeboren wird. Also, wenn jedes Universum genau dasselbe ist, wie viele Universen wird mein Programm durchleben?

(1e99**1e99)/(1e10+1e1000+10**10**56)=1e9701

Unter der Annahme, dass das Universum immer Jahre leben wird 1e10+1e1000und es dann Jahre dauern wird, 10**10**56bis es neu gestartet ist, wird mein Programm 1e9701Universen durchleben . Dies setzt natürlich voraus, dass Unobtainium den Urknall überstehen kann.

Beta-Zerfall
quelle
3
es wird beendet, sobald es das Ende des Bereichs @Philipp erreicht. ja es endet schließlich.
Malachi
1
1000**1000ist 1e3000nicht 1e2000.
Cornstalks
1
@Cornstalks Danke, ich hatte keinen Taschenrechner, der gut genug war, um das zu finden, also habe ich eine Vermutung gemacht, die auf der Tatsache basiert, dass 100**100=1E200.
Beta Decay
1
@BetaDecay: Ich könnte Wolfram | Alpha als Online-Rechner vorschlagen . Wenn Sie es noch nie benutzt haben, ist es ziemlich genial!
Cornstalks
2
@anyoneinterested Oder 1000 ^ 1000 = (10 ^ 3) ^ 1000 = (10 * 10 * 10) * (10 * 10 * 10) * ... * (10 * 10 * 10) [1000-mal] = 10 ^ 3000
IazertyuiopI
12

Python 59 (funktioniert meistens)

Ich konnte nicht widerstehen

from random import*
while sum(random()for i in range(99)):0

Es ist zwar richtig, dass dies theoretisch in weniger als einer Millisekunde enden könnte, die durchschnittliche Laufzeit ist jedoch um ein 10^400Vielfaches länger als die angegebene Lebensdauer des Universums. Vielen Dank an @BetaDecay, @undergroundmonorail und @DaboRoss, dass sie es auf ungefähr 17 Zeichen gebracht haben.

KSab
quelle
Um es auf 71 nach unten können Sie ersetzen continuemitpass
Beta Decay
@ BetaDecay Nice catch
KSab
3
Ich denke, da die Frage nach der erwarteten Laufzeit fragt , ist es kein Problem, dass dies vorzeitig beendet wird. Das größere Problem ist, dass es nicht bewiesen werden kann, dass es überhaupt endet.
user19057
4
@ user19057 Unter der Annahme, dass KSab dies gesagt hat, ist die erwartete Laufzeit endlich und das Programm wird mit einer Wahrscheinlichkeit von 100% beendet. Natürlich verwendet das Zufallsmodul tatsächlich ein PRNG, das zyklisch ist, so dass dies höchstwahrscheinlich niemals enden wird.
Jerome Baum
1
Ich denke, Sie können 3 Zeichen abschneiden, indem Sie 'pass' durch '0' ersetzen.
Daboross
8

J - 5 Zeichen, denke ich

Beachten Sie, dass alle folgenden Angaben in Arithmetik mit willkürlicher Genauigkeit erfolgen, da die Zahl 9 immer ein wenig xdaneben steht.

In sieben Zeichen haben wir !^:!!9x, was ein bisschen wie Laufen ist

n = 9!
for i in range(n!):
    n = n!

in willkürlicher Genauigkeit arithmetisch. Dies ist definitiv über der Grenze, weil Synthetica dies gesagt hat , also haben wir eine Obergrenze.

Im sechs Zeichen können wir auch schreiben ^/i.9x, was jedes Zwischenergebnis von berechnet 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha sagt 2^3^4^5^6^7^8ist ungefähr 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, was wahrscheinlich auch Inspektion klärt.

Wir haben auch die fünf Zeichen!!!9x , die nur ((9!)!) Ist. W | A sagt, es 10 ^ 10 ^ 10 ^ 6.2695sollte immer noch groß genug sein ... Das sind wie 1.6097e1859933-ish Ziffern, die entschieden größer sind als 3.154e1016die Anzahl der Nanosekunden im Universum, aber ich gebe zu, ich habe keine Ahnung, wie man das herausfinden könnte die realen Laufzeiten dieser Dinge.

Das Drucken allein sollte jedoch so lange dauern, dass es länger hält als das Universum. Es sollte also in Ordnung sein.

algorithmshark
quelle
7

C 63 56 Zeichen

f(x,y){return x?f(x-1,y?f(x,y-1):1):y+1;}main(){f(9,9);}

Dies basiert auf einer Idee eines Mannes namens Wilhelm. Mein einziger Beitrag ist es, den Code auf dieses kurze (und unlesbare) Stück zu reduzieren.

Der Nachweis, dass es endet, erfolgt durch Induktion.

  • Wenn x 0 ist, wird es sofort beendet.
  • Wenn es für x-1 und irgendein y endet, endet es auch für x, dies kann selbst durch Induktion gezeigt werden.

Induktionsschritt durch Induktion beweisen:

  • Wenn y 0 ist, gibt es nur einen rekursiven Aufruf mit x-1, der durch Induktionsannahme endet.
  • Wenn f (x, y-1) endet, endet auch f (x, y), weil der innerste Aufruf von f genau f (x, y-1) ist und der äußerste Aufruf gemäß der Induktionshypthesis endet.

Die erwartete Laufzeit beträgt A (9,9) / 11837 Sekunden. Diese Zahl hat mehr Stellen als die Anzahl der Quarks im beobachtbaren Universum.

Kasperd
quelle
(Ab) benutze den Präprozessor und definiere m = main, r = return und z = 99999, dann schreibe dein Programm um als, f (x, y) {rx? F (x-1, y? F (x, y- 1): 1): y + 1;} m () {f (z, z);} was erstaunlich lange dauern wird :-)
ChuckCottrill
5
@ChuckCottrill Wenn die Regeln Programme zuließen, für die bestimmte Präprozessor-Makros erforderlich sind, und für die die Programmlänge nicht berücksichtigt wurde, kann jede Aufgabe in einem Zeichen gelöst werden.
Kasperd
6

Matlab ( 10 8 Zeichen)

1:9e1016

IMHO, die meisten Einträge sind zu bemüht, indem sie große, komplizierte Dinge berechnen. Dieser Code initialisiert einfach ein Array von 9x10 1016 double s, wobei von 1 aufwärts gezählt wird, was 7,2x10 ^ 1017 Bytes benötigt. Auf einer modernen CPU mit einer maximalen Speicherbandbreite von 21 GB / s oder 6,63 x 10 ^ 17 Byte / Jahr werden mindestens 1,09 x 10 1000 benötigt Jahre benötigt, um das Array zu initialisieren, geschweige denn zu drucken, da ich mich nicht darum gekümmert habe Unterdrücken der Ausgabe mit einem nachgestellten Semikolon. (;


alte Lösung (en)

nan(3e508)

Alternative

inf(3e508)

Dieser Code erzeugt einfach eine quadratische Matrix aus NaNs / unendlich großen 3e508x 3e508 = 9e10168-Byte-Doppel- oder 7.2e1017-Bytes.

Nicu Stiurca
quelle
1
Was ist das? 1016? Das muss 9999 sein! (Oder habe ich etwas falsch verstanden?)
Mega Man
@MegaMan Die Problemmeldung fordert eine Laufzeituntergrenze von 10 ^ 1000 Jahren an. Da ich Golf spielen wollte, wollte ich nicht zu viel Zeit verschwenden und zu lange rechnen , also versuchte ich, es so schnell wie möglich zu stoppen, nachdem ich die Schwelle erreicht hatte. :)
Nicu Stiurca
ah, ok, wusste diese Regel nicht
Mega Man
5

Perl, 16 Zeichen

/$_^/for'.*'x1e9

Dadurch wird eine Zeichenfolge erstellt, die ". *" Milliardenfach wiederholt und dann in einem Regex-Match sowohl als Nadel als auch als Heuhaufen verwendet wird. Dies wiederum veranlasst die Regex-Engine, jede mögliche Partition einer Zeichenfolge mit einer Länge von zwei Milliarden Zeichen zu versuchen. Nach dieser Formel von Wikipedia gibt es etwa 10 35218 solcher Partitionen.

Die obige Lösung ist 16 Zeichen lang, benötigt jedoch nur etwa 2 GB Speicher, was bedeutet, dass sie auf einem echten Computer ausgeführt werden kann. Wenn wir von unendlich viel Speicher und endlicher Registergröße ausgehen (was wahrscheinlich keinen Sinn ergibt), kann dies auf 15 Zeichen verkürzt werden, während die Laufzeit drastisch erhöht wird:

/$_^/for'.*'x~0

(Ich habe es nicht getestet, aber ich denke, es könnte mit einem 32-Bit-Perl funktionieren, das auf einem 64-Bit-Computer mit mindestens 6 GB RAM aufgebaut ist.)

Anmerkungen:

  • x ist der String-Repeat-Operator.
  • Das forist keine echte Schleife. Es wird nur zum Speichern eines Zeichens verwendet (im Vergleich zu$_=".*"x1e9;/$_^/ ).
  • Das Finale ^im regulären Ausdruck stellt sicher, dass nur die leere Zeichenfolge übereinstimmen kann. Da Regex-Quantifizierer standardmäßig gierig sind, ist dies das letzte, was die Engine versucht.
  • Benchmarks auf meinem Computer für Werte (1..13) legen nahe, dass die Laufzeit tatsächlich O (exp (n)) ist, was sogar mehr ist als das O (exp (sqrt (n))) in der Wikipedia-Formel.
Schmutzig
quelle
4

J (12)

(!^:(!!9))9x

Worauf es in Python ankommt (vorausgesetzt, es !funktioniert):

a = 9 
for i in range((9!)!):
    a = a!

BEARBEITEN:

Nun, das Programm kann höchstens dauern, 2 × 10^-1858926 Sekunden pro Zyklus innerhalb der erforderlichen Zeit abgeschlossen ist. Tipp: Dies funktioniert nicht einmal für den ersten Zyklus, egal für den letzten;).

Außerdem: Dieses Programm benötigt möglicherweise mehr Speicher als es Entropie im Universum gibt ...

ɐɔıɐɔuʇǝɥʇs
quelle
3
"Benötigt möglicherweise mehr Speicher, als es Entropie im Universum gibt" - Damit können Sie xrange()
Abstriche machen
1
Funktioniert auch !nicht in Python. Du brauchst import mathund math.factorial().
Daviewales
4

C # 217

Ich bin kein großer Golfer, aber ich konnte Ackermans Funktion nicht widerstehen . Ich weiß auch nicht wirklich, wie man die Laufzeit berechnet, aber es wird definitiv anhalten und es wird definitiv länger als diese Version laufen .

class P{
static void Main(){for(int i=0;i<100;i++){for(int j=0;j<100;j++){Console.WriteLine(ack(i,j));}}}
static int ack(int m,int n){if (m==0) return n+1;if (n ==0) return ack(m-1,1);return ack(m-1,ack(m,n-1));}
}
Badeente
quelle
Sie können 10 Bytes einsparen, indem Sie die ackFunktion in einen Namen mit einem einzelnen Zeichen umbenennen a.
Paprika
4

Erster Versuch am Codegolf aber hier geht's weiter.

VBA - 57 45

x=0
do
if rnd()*rnd()<>0 then x=0
x=x+1
while 1=1

X wird also um eins erhöht, wenn ein 1 in 2 ^ 128-Ereignis auftritt, und zurückgesetzt, wenn es nicht auftritt. Der Code endet, wenn dieses Ereignis 2 ^ 64 + 1 Mal hintereinander auftritt. Ich weiß nicht, wie ich anfangen soll, die Zeit zu berechnen, aber ich schätze, sie ist riesig.

EDIT: Ich habe die Mathematik berechnet und die Wahrscheinlichkeit, dass dies in jeder Schleife passiert, ist 1 zu 2 ^ 128 ^ (1 + 2 ^ 64), was ungefähr 20000 Stellen lang ist. Unter der Annahme von 1000000 Schleifen / Sek. (Ballpark aus dünner Luft) und 30000000 s / Jahr, die 3 * 10 ^ 13 Zyklen pro Jahr und 10 ^ 1000 Jahre übrig sind, sind dies 3 * 10 ^ 1013 Zyklen verbleibende Zeit im Universum. Ich bin froh, dass meine Mathematik meine Intuition stützt.

Myles Horne
quelle
Ich denke, dass die letzte Zeile sein sollte While x=1, oder? (Sonst ist es eine Endlosschleife). Außerdem können Sie aus 12 Zeichen rasieren , wenn Sie ersetzen Dim x As Doublemit x=0(VBA erfordert keine Variablen deklarieren , wenn Sie angeben Option Explicit)
kb_sou
Ich betrachte es nicht als Endlosschleife, da es bricht, wenn x überläuft, was letztendlich der Fall ist.
Myles Horne
Es funktioniert definitiv nicht mit x = 1, da dies im Allgemeinen die Schleife am Laufen hindern würde.
Myles Horne
Wenn das Unterbrechen der Schleife auf diese Weise nicht die Kriterien für "Keine Endlosschleifen" erfüllt, kann sich WHILE 1 = 1 in WHILE ISNUMERIC (X) ändern.
Myles Horne
4

C 30 Zeichen

main(i){++i&&main(i)+main(i);}

Unter der Annahme eines vorzeichenbehafteten Überlaufs von zwei und 32-Bit-Ints wird dies für ungefähr 2 2 32 Funktionsaufrufe ausgeführt, was für das Ende des Universums ausreichend Zeit sein dürfte.

Uristqwerty
quelle
Sie werden jedoch lange vorher keinen Stapel mehr haben.
Sparr
1
@Sparr Eine der Regeln ist die Annahme einer unendlichen Stapel- und Heap-Größe.
Scragar
3

GolfScript, 13 Zeichen

0{).`,9.?<}do

Dieses Programm zählt nur von 0 bis 10 9 9 −1 = 10 387420488 . Unter der optimistischen Annahme, dass der Computer mit 100 GHz arbeitet und jede Iteration des Programms in einem einzigen Zyklus ausführen kann, wird das Programm 10 9 9 - 12 Sekunden oder etwa 3 × 10 9 9 - 20 = 3 × 10 387420469 ausgeführt Jahre.

Um das Programm zu testen, können Sie die ersetzen 9mit ein 2, die wird es bei 10 zu stoppen machen 2 2 -1 = 10 3 = 1000 (unter Verwendung eines 3anstelle eines 2wird es bei 10 stoppen 3 3 -1 = 10 26 , die Selbst mit den oben genannten optimistischen Annahmen wird es noch einige Millionen Jahre dauern.)

Ilmari Karonen
quelle
3

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}
Person93
quelle
3

Haskell, 23

main=interact$take$2^30

Dieses Programm wird beendet, nachdem 1073741824 Zeichen aus gelesen wurden stdin. Wenn es ohne Weiterleitung von Daten ausgeführt wird, stdinmüssen Sie diese Anzahl von Zeichen auf Ihrer Tastatur eingeben. Angenommen, Ihre Tastatur verfügt über 105 Tasten, von denen jede für 100.000 mechanische Zyklen ausgelegt und so programmiert ist, dass sie nicht tote Tastenanschläge erzeugen. Die automatische Wiederholung ist deaktiviert. Der Tastatursockel ermöglicht 100 Verbindungszyklen. Dies entspricht einer maximalen Anzahl von Tastenanschlägen pro Computer mit einer Betriebszeit von 1050000000 nicht genug für das Programm zu beenden.

Daher wird das Programm nur beendet, wenn eine bessere Hardware in Bezug auf die Anzahl der Zyklen verfügbar ist, was in diesem Universum praktisch nie der Fall ist. Vielleicht das nächste Mal, wenn Qualität Vorrang vor Quantität hat. Bis dahin endet dieses Programm im Prinzip, aber nicht in der Praxis.

TheSpanishInquisition
quelle
Was ist, wenn Sie Ihre Tastaturen im laufenden Betrieb austauschen?
Thomas
Dies wird durch die 100 Verbindungszyklen der Tastaturbuchse abgedeckt.
TheSpanishInquisition
Aber der Punkt des Problems ist , dass das Programm nicht beenden, irgendwo nach dem Wärmetod des Universums. Dieses Programm kann niemals beendet werden.
Wenn die
1
Ich bin noch nicht überzeugt. Wenn Sie das Programm remote (oder auf einer VM) ausführen, sind Sie nicht an die Hardwarefunktionen eines einzelnen Computers gebunden, und 1 Milliarde Striche sind wirklich nicht so viel. Außerdem besagt das Problem, dass der Computer aus Unobtainium besteht und die Tastatur daher auch 2 bis 30 Tastenanschläge verarbeiten kann ...
Thomas,
3

~ ATH, 56

In der fiktiven Sprache ~ ATH :

import universe U;
~ATH(U) {
} EXECUTE(NULL);
THIS.DIE()

~ ATH ist eine unerträgliche Sprache, mit der man arbeiten kann. Seine Logik besteht aus nichts als Endlosschleifen oder bestenfalls Schleifen von effektiv endloser Konstruktion.

Was viele ~ ATH-Codierer tun, ist, endliche Konstrukte zu importieren und die Schleifen an ihre Lebensdauer zu binden. Zum Beispiel endet die Hauptschleife hier mit dem Tod des Universums mit der Bezeichnung U. Auf diese Weise müssen Sie nur Milliarden von Jahren warten, bis sie endet, anstatt für immer.

Ich entschuldige mich für die Grenzverletzungen; Ich fand es zu relevant, um darauf zu verzichten.

Wenn jemand davon wirklich amüsiert war, mehr Details: (1) , (2) , (3) , (4)

DBN
quelle
2

Rubin (34)

Die Linie ([0]*9).permutation.each{print}dauert ca. 2,47 Sekunden für 9! druckt auf meinem Computer, während die Linie ([0]*10).permutation.each{print}für 10 etwa 24,7 Sekunden dauert! druckt, also kann ich hier wahrscheinlich extrapolieren und berechnen, (24.7/10!)*470! seconds in yearswas 6,87 * 10 ^ 1040 ist, was die Laufzeit von sein sollte:

([0]*470).permutation.each{print}
Boris
quelle
2

JavaScript 68 62 Zeichen

(function a(m,n){return m==0?n+1:a(m-1,n==0?1:a(m,n-1))})(5,1)

Dies verwendet die Ackermann-Funktion, die als geschrieben werden kann

function ackermann(a, b) {
  if (a == 0) return b + 1;
  if (b == 0) return ackermann(a-1, 1);
  else return ackermann(a-1, ackermann(a, b-1));
}

Die Laufzeit nimmt exponentiell zu und die Berechnung dauert daher sehr lange. Auch wenn es hier nicht englisch ist , können Sie sich einen Überblick über die Rückgabewerte verschaffen. Nach der Tabelle ist ackermann(5,1)gleich, 2↑↑(65533)-3was, wie Sie wissen, sehr groß ist.

henje
quelle
2
Dies kann von einigen der gleichen Optimierungen wie die frühere Implementierung der Perl Ackermann-Funktion profitieren.
Peter Taylor
Ich muss die Perl-Lösung übersehen haben. Vielen Dank für den Hinweis.
Henje
Stattdessen n==0?X:Ykönnen Sie immer tunn?Y:X
Cyoce
2

Befunge '93 - 40 Bytes

(20x2 Programm)

v<<<<<<<<<<<<<<<<<<<
>??????????????????@

Dieses Programm basiert auf Zufallszahlen, um es zu verzögern. Da Befunge-Dolmetscher ziemlich langsam sind, sollte dieses Programm genau das Richtige sein. Und wenn nicht, können wir es immer horizontal erweitern. Ich bin mir nicht ganz sicher, wie ich die erwartete Laufzeit dieses Programms berechnen soll, aber ich weiß, dass jeder? hat eine 50/50-Chance, entweder von vorne anzufangen oder seine horizontale Position um 1 zu ändern. Es gibt 18? Ich denke, es sollte etwas in der Art von (18 ^ 2) sein! Der Google-Rechner sagt "Unendlichkeit".

EDIT: Whoops Ich habe die andere Befunge Antwort nicht bemerkt, das ist mein erster Beitrag hier. Es tut uns leid.

Rodolphito
quelle
Hey, mach dir keine Sorgen um die andere Antwort, oder im Allgemeinen die gleiche Sprache wie jemand anderes. Ich meine, niemand wird das Mathlab schlagen, also geht es bei allen anderen Einsendungen um Spaß. Meins war.
AndoDaan
2

APL, 10

Ich denke nicht, dass dies eine gültige Antwort ist (da sie nicht deterministisch ist), aber trotzdem ......

{?⍨1e9}⍣≡1

Dieses Programm berechnet eine zufällige Permutation von 1e9-Zahlen ( ?⍨1e9) und wiederholt diese, bis zwei aufeinanderfolgende Ausgaben gleich sind ( ⍣≡).

Jedes Mal, wenn eine Permutation berechnet wird, hat sie eine 1 in 1000000000! Kündigungsmöglichkeit. Und 1000000000! ist mindestens 10 10 8 .

Die Zeit, die zur Berechnung einer Permutation benötigt wird, ist durch die Massivität von 1000000000! Irrelevant. Aber einige Tests zeigen, dass dies der O(n)Fall ist, und eine Extrapolation ergibt ungefähr 30 Sekunden.

Mein Interpreter weigert sich jedoch, Eingaben in die Zufallsfunktion zu übernehmen, die größer als 2 31 -1 sind (also habe ich 1e9 verwendet), und das Erzeugen von Permutationen mit 1000000000 Zahlen ergab einen vollständigen Fehler im Arbeitsbereich. Konzeptionell kann dies jedoch mit einem idealen APL-Interpreter mit unbegrenztem Speicher erfolgen.

Dies führt uns zu der Möglichkeit, 2 63 -1 anstelle von 1e9 zu verwenden, um die Laufzeit unter der Annahme einer 64-Bit-Architektur auf mindestens 10 10 20 zu erhöhen .

Aber warten Sie, ist Architektur in einem idealen Interpreter relevant? Zur Hölle, nein, es gibt eigentlich keine Obergrenze für die Laufzeit !!

TwiNight
quelle
2

R, 45 Bytes

(f=function(x)if(x)f(x-1)+f(x-1)else 0)(9999)

Es ist ein alter Thread, aber ich sehe keine R-Antwort, und das können wir nicht haben!

Die Laufzeit für mich war ungefähr 1s, als x 20 war, was eine Laufzeit von 2 ^ 9979 Sekunden nahelegt.

Wenn Sie die Null durch eine Eins ersetzen, ist die Ausgabe 2 ^ x, aber die Ausgabe ist nach heutigem Stand null, unabhängig davon, was x war (vermeidet Überlaufprobleme).

JDL
quelle
1

Javascript, 120 Bytes

a=[0];while(a.length<1e4)(function(){var b=0;while(b<a.length){a[b]=(a[b]+1)%9;if(a[b])return;b++}a.push(1)})();alert(a)

Kann mit minimalem Arbeitsspeicher (wahrscheinlich weniger als ein halbes Megabyte) durchgeführt werden, dauert aber (wahrscheinlich) etwa 10 bis 8.750 Jahre.

Inkrementiert wiederholt eine Little-Endian-Base-9-BigInteger, bis 9 10 4 -1 erreicht sind .

SuperJedi224
quelle
1

Python 3, 191 Bytes

from random import*
r=randint
f=lambda n:2if n<2else f(n-1)
x=9E999
s=x**x
for i in range(f(x)**f(s)):
 while exec(("r(0,f(x**i))+"*int(f(x)))+"r(0,f(x**i))")!=0:
  s=f(x**s)
  print(s)

Erstens ist f eine rekursive Fakultätsfunktion und extrem langsam. Dann gibt es 9 * 10⁹⁹⁹ mit sich selbst, die einen OverflowError generiert, aber das passiert auf diesem Unobtanium-Computer nicht. Die For-Schleife durchläuft 9E999! ^ (9E999 ^ 9E999)! Mal und es geht nur zur nächsten Iteration, wenn 9E999! +1 zufällige Ints zwischen 0 und 9E99 * ^ i! sind alle 0 und in jeder Iteration der while-Schleife wird s auf (9E999 ^ s) gesetzt !. Äh, ich habe vergessen, dass das Drucken von s viel Zeit in Anspruch nimmt ...
Ich weiß, es ist nicht die kürzeste Lösung, aber ich denke, es ist wirklich effektiv. Kann mir jemand bei der Berechnung der Laufzeit helfen?

Mega Man
quelle
1

Turing-Maschine aber viel schlimmer , 167 Bytes

0 0 1 1 2 0 0
1 0 1 0 4 0 0
0 1 1 1 2 0 0
1 1 1 1 5 0 0
0 2 1 0 3 0 0
1 2 0 1 1 0 0
0 3 1 1 4 0 0
1 3 0 0 2 0 0
0 4 1 0 0 0 0
1 4 0 1 3 0 0
0 5 1 0 6 0 1
1 5 1 1 2 0 0

Probieren Sie es online!

Sollte den 2-Symbol-Busy-Beaver mit 6 Zuständen von der Wikipedia-Seite ausführen .

7.412×1036534

MilkyWay90
quelle