Si un programme se termine et que personne ne le voit, s’arrête-t-il?

99

Il est temps de faire face à la vérité: nous ne serons pas ici pour toujours, mais au moins nous pouvons écrire un programme qui survivra à la race humaine même si elle se débat jusqu'à la fin des temps.

Votre tâche consiste à écrire un programme dont la durée d'exécution attendue est supérieure au temps restant jusqu'à la fin de l'univers.

Vous pouvez supposer que:

  • L'univers mourra d'entropie dans 10 000 ans.
  • Ton ordinateur:
    • Survivra à l'univers, car il est fait d' Unobtainium .
    • A une limite infinie de mémoire / pile / récursivité.
    • Son processeur a une vitesse limitée.

Vous devez montrer que votre programme se termine (désolé, pas de boucles infinies) et calculer le temps d'exécution prévu.

Les failles standard s'appliquent.

Il s’agit d’un défi de code-golf, donc le code le plus court qui satisfait aux critères l’emporte.

EDIT :

Malheureusement, il a été constaté (30 minutes plus tard) que le champ d'improbabilité d'Unobtainium interfère avec l'horloge interne de l'ordinateur, le rendant ainsi inutile. Ainsi, les programmes basés sur le temps s’arrêtent immédiatement. (Qui laisserait un programme qui attend son héritage vivant de toute façon?).

Le processeur de l'ordinateur est similaire à celui de l'Intel i7-4578U. Par conséquent, un moyen de mesurer le temps d'exécution est d'exécuter votre programme sur un ordinateur similaire avec une entrée plus petite (j'espère) et d'extrapoler son temps d'exécution.


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 au 31/08

kb_sou
la source
40
J'ai été tenté de créer une balise [code le plus lent] pour cette question. : P
Poignée de porte
5
Un Bogosort ne fonctionnerait pas parce que s'il est infiniment improbable qu'il ne finisse jamais, il peut prendre un temps infini. Cependant, il existe de nombreuses expressions régulières basées sur NFA qui pourraient satisfaire le critère "finiront, mais pas avant que l'univers ne soit mort".
DavidO
49
Votre titre devrait être un tshirt
user-2147482637
4
Belle question, mais ne devrait-il pas s'agir d'un concours de popularité?
IazertyuiopI
12
Je pense que Isaac Asimov a écrit une histoire à ce sujet .
David Conrad

Réponses:

34

CJam, 5 octets

0{)}h

Comment ça fonctionne

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

Ce programme s’arrête lorsque le tas ne peut plus stocker le Big Integer, ce qui ne se produira plus de sitôt sur un ordinateur de bureau moderne.

La taille de segment de mémoire par défaut est 4,179,623,936 octets sur mon ordinateur (Java 8 sur Fedora). Il peut être augmenté à une valeur arbitraire avec -Xmx, de sorte que la seule limite réelle est la mémoire principale disponible.

Moment du décès

En supposant que l'interprète ait besoin de x bits de mémoire pour stocker un grand nombre entier non négatif inférieur à 2 x , nous devons compter jusqu'à 2 8 × 4 179 623 936 = 2 33 436 991 488 . Avec un incrément par cycle d'horloge et mon Core i7-3770 (3,9 GHz avec turbo), il faudra 2 33 436 991 488 ÷ 3 400 000 000> 10 10 065 537 393 secondes, soit plus de 10 10 10 065 537 385 années.

Dennis
la source
14
Je ne pense pas que vous puissiez compter sur des ressources finies, comme le dit la question "Votre ordinateur a une limite infinie de mémoire / pile / récursivité".
Greg Hewgill
4
Mémoire !=infinie types de données infinis. Si j'ai un téraoctet de RAM, un entier de 8 bits non signé ne monte toujours que jusqu'à 255.
wchargin
6
@GregHewgill: avec des ressources illimitées, vous pouvez augmenter la taille maximale du segment de mémoire Java à n'importe quelle valeur arbitraire, mais elle sera toujours finie.
Dennis
2
@Dennis, mais ajoutez ensuite une ligne à chaque fois dans la boucle pour doubler la taille du segment de mémoire. C'est une chose amusante à propos des infinis :-)
Carl Witthoft
9
@CarlWitthoft: Vous ne pouvez pas faire cela depuis le programme.
Dennis
62

JavaScript, 39

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

Explication

Comme JavaScript ne représente pas précisément les grands entiers, la boucle se for(;x!=++x;)termine une fois xatteinte 9007199254740992.

Le corps de la boucle for sera exécuté Fib(9007199254740992) - 1fois, où Fib(n)est le nième nombre fibonacci.

D'après les tests, je sais que mon ordinateur effectuera moins de 150 000 itérations par seconde. En réalité, cela fonctionnerait beaucoup plus lentement car la pile deviendrait très volumineuse.

Ainsi, le programme prendra au moins (Fib(9007199254740992) - 1) / 150000quelques secondes à exécuter. Je n’ai pas pu calculer Fib(9007199254740992)parce que c’est très grand, mais je sais que c’est beaucoup plus que 10 000 * 150 000.

EDIT: Comme indiqué dans les commentaires, Fib(9007199254740992)correspond à environ 4,4092 * 10 1882393317509686 , ce qui est effectivement assez grand.

Peter Olson
la source
9
Comme fib(n)on peut approximer par phi^n, on peut utiliser log((sqrt(5) + 1)/2)*9007199254740992pour calculer combien de chiffres fib(9007199254740992)il s’agit 1.8823933*10^15.
Overactor
11
@overactor, Selon Wolfram Alpha, Fib(9007199254740992)(en utilisant une forme continue avec phi) est approximativement 4.4092... * 10^1882393317509686. Calcul
Brian S
1
la pile en croissance ne réduit pas la vitesse du processeur ... sauf si vous tenez compte de la largeur de ligne d'adresse de mémoire limitée / largeur illimitée (dans ce cas, le ralentissement reste linéaire en longueur d'adresse en supposant un codage raisonnable) ou même des limitations physiques en matière de stockage en mémoire et la vitesse de la lumière (dans ce cas , le ralentissement est cbrtic en valeur d'adresse en supposant le stockage spatiale, même des niveaux d'ADN de densité de données éventuellement commencer à ajouter, même si vous parvenez espace efficace à accès aléatoire)
John Dvorak
1
@JamesKhoury Non, la fonction que vous venez d'écrire est équivalente for(x=0;x!=++x;)et ne répète que 9007199254740992 fois.
Peter Olson le
4
@SylvainLeroux une architecture avec une quantité infinie de RAM entrelacerait probablement le tas et la pile et les ferait croître vers le haut.
John Dvorak
47

Python (9)

9**9**1e9

Cela a plus de 10 ** 10000000 bits, donc le calcul devrait nous prendre bien au-delà de la mort par chaleur.

J'ai vérifié que cela prenait de plus en plus de temps pour des valeurs plus grandes mais toujours raisonnables, donc ce n'était pas seulement optimisé par l'interpréteur.

Edit: Golfé deux caractères en supprimant les parens grâce à @ user2357112. TIL que Python traite les exposants successifs comme une tour de contrôle.

Xnor
la source
4
OverflowError: (34, 'Résultat trop important')
apple16
93
@ apple16 Peut-être sur votre ordinateur, mais le mien a une "limite infinie de mémoire / pile / récursivité".
xnor
64
C'est bon, les gars. J'ai lancé le dernier univers et j'ai eu ...82528057365719799011536835265979955007740933949599830498796942400000000009(2,6 * 10 ^ 954242509 chiffres omis pour éviter l'effondrement du trou noir ). Vous devriez vraiment passer à Unobtanium.
xnor
10
L'exponentiation est une association à droite, vous pouvez donc supprimer les parenthèses.
user2357112
10
Il est à noter que la taille 9**9**9e9est tout aussi courte et prend un peu plus de longueurs d'univers à calculer, ainsi qu'une apparence un peu plus jolie.
Abarnert
35

GolfScript ( 12 7 caractères)

9,{\?}*

Ceci calcule et imprime 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Pour l'imprimer (peu importe le calcul) en 10 ^ 1000 ans ~ = 10 ^ 1007,5 secondes, il faut imprimer environ 10 ^ (10 ^ 10 ^ 10 ^ 183230 - 10 ^ 3) chiffres par seconde.

Peter Taylor
la source
22
Mais cela s'arrêtera bien avant cela avec un message "Imprimante épuisée" ...
Floris
1
@ Floris, qui diable utilise un support physique ces jours-ci?
John Dvorak
3
@ JanDvorak, je viens de supposer que Floris et les 7 personnes l'ayant voté appartiennent à la génération de mon grand-père, alors que tout était en sortie.
Peter Taylor
2
@PeterTaylor - peut-être pas si vieux, mais je suis assez vieux pour me souvenir d'avoir soumis des "travaux par lots" à "l'ordinateur" (à l'époque où il n'y avait aucun doute, dans une population étudiante de 20k, l'ordinateur que vous vouliez dire), et ramasser l'impression le lendemain. Vous (et 7 autres personnes) avez supposé correctement qu'il s'agissait d'une tentative d'humour et non d'une critique sérieuse de votre excellent script, ridiculement court.
Floris
35

Marbelous 68 66 octets

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

Marbelous est un langage 8 bits dont les valeurs ne sont représentées que par des billes dans une machine du type Rube Goldberg. Ce n'était donc pas très facile. Cette approche est à peu près équivalente au pseudo-code suivant:

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

puisque la valeur maximale est 256, (représentée par 0 dans le programme Marbleous, qui est traité différemment à différents endroits), recursiveFunction (1) sera appelé un total 256!*512^256égal à environ 10^1200, assez facilement pour survivre à l'univers.

Marbelous n'a pas d'interprète très rapide, il semble pouvoir traiter les 10^11appels de cette fonction chaque année, ce qui signifie que nous avons une durée d'exécution de plusieurs 10^1189années.

Explications supplémentaires sur le tableau de Marbelous

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

00est un langage littéral (ou une bille), représenté en hexadécimal (donc 0). Cette bille tombe sur le --, ce qui la réduit de 1 (00 s'enroule et se transforme en FF ou 255 en décimal). La bille avec maintenant la valeur FF tombe sur la \\qui la pousse une colonne à droite, sur la partie inférieure @0. Ceci est un portail et téléporte la bille sur l'autre @0appareil. Là, la bille atterrit sur le /\dispositif, qui est une duplicatrice, elle place une copie de la bille sur --sa gauche (cette bille continuera à boucler entre les portails et sera décrémentée sur chaque boucle) et une =0à droite.=0compare la bille à la valeur zéro et laisse la bille tomber si elle est égale et la repoussera à droite sinon. Si la bille a la valeur 0, elle atterrit sur &0un synchoniseur, que j'expliquerai plus tard.

Dans l’ensemble, cela commence simplement par une bille de valeur 0 dans une boucle et la décrémente jusqu’à atteindre 0, puis il met cette bille de valeur 0 dans un synchroniseur et continue à boucler en même temps.

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

}0est un périphérique d'entrée. Initialement, la nième entrée (base 0) de la ligne de commande lors de l'appel du programme est placée dans chaque }npériphérique. Donc, si vous appelez ce programme avec l'entrée de ligne de commande 2, une bille de valeur 02 remplacera ceci }0. Cette bille tombe ensuite dans l’ &0appareil, un autre synchroniseur, les &nsynchroniseurs retenant les billes jusqu’à ce que tous les autres correspondants &nsoient également archivés. La bille est ensuite décrémentée, téléportée et dupliquée à peu près comme dans la boucle précédemment expliquée. La copie de droite est ensuite vérifiée pour l'inégalité avec zéro ( >0) si ce n'est pas 0, elle tombe. Si la valeur est 0, il est poussé à droite et atterrit !!, ce qui termine le tableau.

Jusqu'ici, nous avons une boucle qui compte en continu entre 255 et 0 et laisse une autre boucle similaire (alimentée par l'entrée de la ligne de commande) s'exécuter une fois à chaque fois qu'elle atteint 0. Lorsque cette deuxième boucle a été exécutée n fois (maximum 256 ) le programme se termine. Cela représente donc un maximum de 65 536 exécutions de la boucle. Pas assez pour survivre à l'univers.

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

Cela devrait commencer à paraître familier, l'entrée est décrémentée une fois, puis cette valeur est bouclée et copiée (notez que la bille n'est décrémentée qu'une fois, pas à chaque exécution de la boucle). Il est ensuite vérifié si l'égalité est égale à 0 et si ce n'est pas à zéro, atterrit MB. Ceci est une fonction dans Marbelous, chaque fichier peut contenir plusieurs cartes et chaque carte est une fonction, chaque fonction doit être nommée en précédant la grille par :[name]. Toutes les fonctions sauf la première fonction du fichier, qui porte un nom standard: MB. Ainsi, cette boucle appelle à nouveau la carte principale avec une valeur de n - 1où n est la valeur avec laquelle cette instance de la fonction a été appelée.

Alors pourquoi n*512?

Eh bien, la première boucle s'exécute en 4 ticks (et 256 fois) et la seconde boucle s'exécute n fois avant la fin du forum. Cela signifie que le conseil court environ pour les n*4*256ticks. La dernière boucle (qui appelle la fonction récursive) est compacte et s’exécute en 2 ticks, ce qui signifie qu’elle parvient à appeler la fonction n*4*256/2 = n*512fois.

Quels sont les symboles que vous n'avez pas mentionnés?

\/ est une corbeille qui supprime les billes du tableau, ce qui garantit que les billes découpées ne gênent pas les billes qui tournent en boucle et empêchent le programme de se terminer.

Prime

Étant donné que les billes tombant du bas d'une carte marbelous sont imprimées en sortie sur STDOUT, ce programme imprime une multitude de caractères ASCII pendant son exécution.

suracteur
la source
2
Excellente explication, merci!
Beta Decay
2
Wow, c'est une idée brillante! La langue marbelous est tellement amusante!
rubik
2
+1 Juste ce que je voulais voir. Un langage plus fou que BrainFuck :) Existe-t-il un site avec tutoriel et plus d’informations à ce sujet? (Le lien du titre semble avoir moins de doc que votre réponse)
Sylwester
2
@ Sylwester, je suis heureux que cela vous plaise, Marbelous est encore en développement, mais nous nous attendons à ce qu'il soit dans un état plus stable dans un proche avenir. À ce stade, des tutoriels, une documentation plus complète, des bibliothèques standard et, espérons-le, un interprète en ligne suivre.
overactor
21

Perl, 66 58 caractères

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

Ce qui précède est une implémentation de la fonction Ackermann – Péter . Je n'ai aucune idée de la taille de A (9,9), mais je suis assez certain que l'évaluation prendra beaucoup de temps.

Greg Hewgill
la source
5
+1 ... J'essayais de trouver une langue avec une fonction Ackermann intégrée, mais je n'ai pas réussi à le faire avant que ma patience ne s'épuise. : D
Martin Ender
3
$n?A($m-1,A($m,$n-1)):A($m-1,1)admet une économie facile de 8 caractères en poussant l'opérateur ternaire.
Peter Taylor
3
Je suis à peu près sûr que le nombre de chiffres dans A (9,9) est supérieur au volume de l'univers observable mesuré en longueurs de Planck cubiques.
Kasperd
6
@ Kasperd C'est un euphémisme assez énorme. Le volume de l'univers observable n'est que de l'ordre de 10 ^ 184 volumes de planck. À titre de comparaison, le nombre décrivant le nombre de chiffres dans A (4,4) est approximativement 10 ^ 19700, ce qui est incompréhensible par rapport à A (9,9).
user19057
3
@ user19057 Cela ressemble à appeler l'affirmation de Kasperd une "sous-estimation massive" est une sous-estimation massive. : P
Nicu Stiurca
20

MATLAB, 58 52 caractères

Nous avons besoin d'au moins une solution arithmétique de précision finie, d'où:

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

x = uns (1 999); y = x; alors que tout (y), y = mod (y + x, nombres premiers (7910)); fin

( avec un merci à @DennisJaheruddin pour avoir éliminé 6 caractères )

Le nombre de cycles à terminer est donné par le produit des 999 premiers nombres premiers. Étant donné que la grande majorité d'entre eux ont bien plus de 10 ans, le temps nécessaire pour réaliser la convergence serait supérieur de plusieurs centaines, voire plusieurs milliers, à des ordres de grandeur supérieurs à la limite minimale.

COTO
la source
+1 Il m'a fallu un certain temps pour voir ce que vous faites là-bas. Agréable!
Point fixe
+1 CRT, n'est-ce pas?
mardi
Bien, je pense que certains caractères peuvent être sauvegardés comme suit: y = uns (1 999), tandis que y * y ', y = mod (y + 1, nombres premiers (7910)); fin
Dennis Jaheruddin
@DennisJaheruddin: raccourcissement brillant. Je mettrai à jour.
COTO
Bien que ce ne soit plus la même solution, cela devrait p=1:9e9;y=p;while+y*y',y=mod(y+1,p),end
quand
19

Mathematica, 25 19 octets

Cette solution a été publiée avant la disqualification des fonctions horaires.

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

TimeUsed[]renvoie les secondes depuis le début de la session et Mathematica utilise des types à précision arbitraire. Il y a quelques 10 7 secondes en un an, donc en attente 10 10000 secondes devrait être suffisant.

Alternative plus courte / plus simple (/ valide):

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

Comptons simplement à la place. Nous devrons compter un peu plus loin, car nous pouvons faire pas mal d’incréments en une seconde, mais la limite supérieure ne coûte pas réellement de caractères.

Techniquement, dans les deux solutions, je pourrais utiliser une limite beaucoup plus basse car le problème ne spécifie pas une vitesse de processeur minimale.

Martin Ender
la source
Aimer! Cette réponse m'a fait rire aux éclats de rire avec un grand sourire.
Todd Lehman
1
Désolé, pour des raisons de créativité, j'ai dû supprimer des solutions basées sur le temps (comme la première). S'il vous plaît ne me déteste pas. :)
kb_sou
5
@kbsou Eh bien, je l'ai battu avec mon autre, alors je m'en fiche. Mais sinon, disqualifier les réponses rétrospectivement pour les changements de règles n'est pas cool cependant. ;)
Martin Ender
1
Mathematica est-il vraiment si lent que l'informatique 9^9^9prend plus que des 10^1000années? J’estime que les calculs 9^9^9sur mon U7300 à 1,3 GHz bcprendraient moins de 6 mois. (Basé sur l'extrapolation du temps 9^2000009^400000
nécessaire
2
@ArtOfCode Mathematica utilise des types à précision arbitraire, il va donc essayer de déterminer la valeur correcte.
Martin Ender
16

Python 3 - 49

Cela fait quelque chose d’utile: calcule Pi avec une précision sans précédent en utilisant la série infinie de Gregory-Leibniz.

Juste au cas où vous vous le demanderiez, ce programme tourne en boucle 10**10**10**2.004302604952323.

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

Précision arbitraire: 78

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

Source de l'image

Le souffle terminal

En raison des énormes calculs en cours, les 1e99**1e99itérations ne prennent que quelques 1e99**1e99années. Maintenant, (1e99**1e99)-1e1000fait à peine une différence. Cela signifie que ce programme durera beaucoup plus longtemps que la mort de notre univers.

Renaissance

Maintenant, les scientifiques proposent que dans 10**10**56 years, l'univers renaisse à cause de fluctuations quantiques ou de tunnels. Donc, si chaque univers est exactement le même, combien d’univers mon programme va-t-il vivre?

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

En supposant que l'univers vivra toujours des 1e10+1e1000années et prendrait ensuite des 10**10**56années pour «redémarrer», mon programme vivra à travers des 1e9701univers. Cela suppose, bien entendu, qu’unobtainium puisse traverser le Big Bang.

Beta Decay
la source
3
il se termine lorsqu'il atteint la fin de la plage @Philipp. oui ça finit, finalement.
Malachi
1
1000**1000n'est 1e3000pas 1e2000.
Cornstalks
1
@Cornstalks Merci, je n'avais pas assez de calculatrice pour le trouver, alors j'ai fait une supposition basée sur le fait 100**100=1E200.
Beta Decay
1
@ BetaDecay: Je pourrais suggérer Wolfram | Alpha comme calculateur en ligne . Si vous ne l'avez jamais utilisé, c'est vraiment génial!
Cornstalks
2
@tous les intéressés Ou 1000 ^ 1000 = (10 ^ 3) ^ 1000 = (10 * 10 * 10) * (10 * 10 * 10) * ... * (10 * 10 * 10) [1000 fois] = 10 ^ 3000
IazertyuiopI
12

Python 59 (fonctionne la plupart du temps)

Je n'ai pas pu résister

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

Bien qu'il soit vrai que cela pourrait théoriquement se terminer en moins d'une milliseconde, le temps d'exécution moyen correspond bien à 10^400la durée de vie spécifiée de l'univers. Merci à @BetaDecay, @undergroundmonorail et @DaboRoss pour l'avoir réduite à 17 caractères environ.

KSab
la source
Pour le réduire à 71, vous pouvez le remplacer continueparpass
Beta Decay
@BetaDecay Belle prise
KSab
3
Je pense que puisque la question demande le temps d’ exécution prévu , le fait que cela se termine tôt n’est pas un problème. Le problème plus important est qu'il ne peut pas être prouvé qu'il se termine.
user19057
4
@ user19057 En supposant ce que KSab a dit, la durée d'exécution attendue est finie et le programme se termine avec une probabilité de 100%. Bien sûr, le module aléatoire utilise en réalité un PRNG, qui est cyclique, donc probablement cela ne se terminera jamais.
Jérôme Baum
1
Je pense que vous pouvez supprimer 3 caractères en remplaçant "pass" par "0".
daboross
8

J - 5 caractères, je pense

Notez que tout ce qui suit est en arithmétique de précision arbitraire, car le nombre 9 est toujours un peu à xcôté.

En sept caractères, nous avons !^:!!9x, ce qui est un peu comme courir

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

en arithmétique de précision arbitraire. C'est certainement au-dessus de la limite parce que Synthetica l'a dit , nous avons donc une limite supérieure.

En six caractères, nous pouvons également écrire ^/i.9x, ce qui calcule chaque résultat intermédiaire de 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha dit 2^3^4^5^6^7^8est environ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, ce qui probablement aussi efface l'inspection.

Nous avons aussi cinq ombles !!!9x, qui est juste ((9!)!) !. W | A dit que c'est 10 ^ 10 ^ 10 ^ 6.2695, ce qui devrait encore être assez grand ... C'est comme 1.6097e1859933-ish chiffres, qui est décidément plus grand que 3.154e1016, le nombre de nanosecondes dans l'univers, mais je vais admettre que je ne sais pas comment on pourrait le savoir les temps d'exécution réels de ces choses.

L'impression seule devrait prendre assez de temps pour durer plus longtemps que l'univers, cependant, ça devrait aller.

algorithmeshark
la source
7

C, 63 56 caractères

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

Ceci est basé sur une idée d'un gars nommé Wilhelm. Ma seule contribution est de condenser le code en un morceau court (et illisible).

Prouver que cela se termine est fait par induction.

  • Si x est 0, il se termine immédiatement.
  • S'il se termine pour x-1 et n'importe quel y, il se termine également pour x, cela même peut être montré par induction.

Prouver l'induction étape par induction:

  • Si y est 0, il n'y a qu'un seul appel récursif avec x-1, qui se termine par l'hypothèse d'induction.
  • Si f (x, y-1) se termine, alors f (x, y) se termine également parce que l'appel le plus interne de f est exactement f (x, y-1) et que l'appel le plus externe se termine conformément à l'hypthèse d'induction.

La durée de fonctionnement prévue est de A (9,9) / 11837 secondes. Ce nombre a plus de chiffres que le nombre de quarks dans l'univers observable.

Kasperd
la source
(Ab) utilisez le préprocesseur et définissez m = main, r = retour et z = 99999, puis réécrivez votre programme en tant que, f (x, y) {rx? F (x-1, y? F (x, y- 1): 1): y + 1;} m () {f (z, z);} ce qui prendra un temps incroyablement long :-)
ChuckCottrill
5
@ChuckCottrill Si les règles autorisaient les programmes, qui nécessitent des macros de préprocesseur spécifiques, et que celles-ci ne comptaient pas pour la longueur du programme, toute tâche peut être résolue en un seul caractère.
Kasperd
6

Matlab ( 10 8 caractères)

1:9e1016

IMHO, la plupart des entrées essaient trop en calculant de grandes choses compliquées. Ce code initialisera simplement un tableau de 9 x 10 1016 à double compter de 1, ce qui prend 7,2 x 10 ^ 1017 octets. Sur un processeur moderne avec une bande passante mémoire maximale de 21 Go / s ou 6,63x10 ^ 17 octets / an , il faudra au moins 1,09x10 1 000 ans pour initialiser le tableau, sans parler d'essayer de l'imprimer car je ne me suis pas ennuyé. supprimer la sortie avec un point-virgule de fin. (;


ancienne solution

nan(3e508)

Alternativement

inf(3e508)

Ce code créera simplement une matrice carrée de NaNs / infinis de taille 3e508x 3e508 = 9e1016doubles ou 7.2e1017octets de 8 octets.

Nicu Stiurca
la source
1
Qu'est-ce que c'est? 1016? Cela doit être 9999! (Ou ai-je mal compris quelque chose?)
Mega Man
@MegaMan L'invite du problème demande une limite inférieure d'exécution de 10 ^ 1000 ans. Étant donné que je jouais au golf, je ne voulais pas gaspiller et calculer trop longtemps, alors j’essayai de le faire arrêter le plus tôt possible après avoir atteint le seuil. :)
Nicu Stiurca
ah, ok, je ne connaissais pas cette règle
Mega Man
5

Perl, 16 caractères

/$_^/for'.*'x1e9

Cela crée une chaîne répétant ". *" Un milliard de fois, puis l’utilise à la fois comme aiguille et meule de foin dans une correspondance regex. Ceci, à son tour, force le moteur regex à essayer toutes les partitions possibles d'une chaîne de deux milliards de caractères. Selon cette formule de Wikipedia , il existe environ 10 35218 partitions de ce type.

La solution ci-dessus comporte 16 caractères, mais nécessite seulement environ 2 Go de mémoire, ce qui signifie qu’elle peut être exécutée sur un ordinateur réel. Si nous supposons une mémoire infinie et une taille de registre finie (ce qui n’a probablement aucun sens), elle peut être réduite à 15 caractères tout en augmentant considérablement le temps d’exécution:

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

(Je ne l'ai pas testé, mais je pense que cela pourrait fonctionner avec un Perl 32 bits construit sur une machine 64 bits avec au moins 6 Go de RAM.)

Remarques:

  • x est l'opérateur de répétition de chaîne.
  • le forn'est pas une boucle réelle; il n’est utilisé que pour sauvegarder un caractère (comparé à $_=".*"x1e9;/$_^/).
  • la finale ^dans l'expression régulière assure que seule la chaîne vide peut correspondre; comme les quantificateurs de regex sont gourmands par défaut, c'est la dernière chose que le moteur va essayer.
  • Les points de repère sur mon ordinateur pour les valeurs (1..13) suggèrent que le temps d'exécution est en fait O (exp (n)), ce qui est même supérieur à O (exp (sqrt (n))) dans la formule de Wikipedia.
Crasseux
la source
4

J (12)

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

Qu'est-ce que cela revient à en Python (en supposant que ça !marche):

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

MODIFIER:

Eh bien, le programme peut prendre, au maximum, 2 × 10^-1858926quelques secondes par cycle, pour se terminer dans le délai requis. Astuce: cela ne fonctionnera même pas pour le premier cycle, peu importe le dernier;).

Aussi: ce programme pourrait avoir besoin de plus de mémoire que d'entropie dans l'univers ...

ıʇǝɥʇuʎs
la source
3
"pourrait avoir besoin de plus de mémoire que d'entropie dans l'univers" - Vous pouvez réduire cela avec xrange();)
Stefan Majewsky
1
En outre, !ne fonctionne pas en Python. Vous avez besoin import mathet math.factorial().
daviewales
4

C # 217

Je ne suis pas un grand golfeur, mais je ne pouvais pas résister à la fonction d'Ackerman . Je ne sais pas non plus comment calculer le temps d’exécution, mais il s’arrêtera définitivement et durera plus longtemps que cette version .

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));}
}
Canard en caoutchouc
la source
Vous pouvez enregistrer 10 octets en renommant la ackfonction en un nom à caractère unique, tel que a.
pppery
4

Première tentative de code de golf, mais voilà.

VBA - 57 45

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

Ainsi, X augmentera de un si un événement 1 in 2 ^ 128 se produit et se réinitialisera s'il ne se produit pas. Le code se termine lorsque cet événement se produit 2 ^ 64 + 1 fois de suite. Je ne sais pas comment commencer à calculer le temps, mais j'imagine que c'est énorme.

EDIT: J'ai calculé le calcul et la probabilité que cela se produise dans chaque boucle est de 1 sur 2 ^ 128 ^ (1 + 2 ^ 64), ce qui correspond à environ 20000 chiffres. En supposant que 1 000 tours / seconde (nombre approximatif de boucles) et 30000000 s / an correspondent à 3 * 10 ^ 13 cycles par an, il reste 10 ^ 1000 ans à 3 * 10 ^ 1013 cycles, ce qui devrait durer environ 20 fois plus de le temps restant dans l'univers. Je suis content que mes calculs sauvegardent mon intuition.

Myles Horne
la source
Je pense que la dernière ligne devrait être While x=1, non? (sinon c'est une boucle infinie). En outre, vous pouvez éliminer 12 caractères si vous remplacez Dim x As Doublepar x=0(VBA n'a pas besoin de déclarer des variables, sauf indication contraire de votre part Option Explicit)
kb_sou
Je ne la considère pas comme une boucle infinie car elle se rompt lorsque x déborde, ce qui est finalement.
Myles Horne
Cela ne fonctionnera certainement pas avec while x = 1 car cela empêcherait généralement la boucle de s'exécuter.
Myles Horne
Si interrompre la boucle de cette manière ne satisfait pas le critère "pas de boucles infinies", WHILE 1 = 1 peut devenir WHILE ISNUMERIC (X).
Myles Horne
4

C, 30 caractères

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

En supposant un dépassement de capacité signé de deux compliments et une entrée de 32 bits, cette opération s'exécutera pendant environ 2 2 32 appels de fonctions, ce qui devrait laisser beaucoup de temps à l'univers pour se terminer.

Uristqwerty
la source
Vous serez à court de pile bien avant cela, cependant.
Sparr
1
@Sparr L'une des règles consiste à supposer une pile et une taille de pile infinies.
Scragar
3

GolfScript, 13 caractères

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

Ce programme ne fait que compter de 0 à 10 9 9 −1 = 10 387420488 . En supposant avec optimisme que l'ordinateur fonctionne à 100 GHz et puisse exécuter chaque itération du programme en un seul cycle, le programme s'exécutera pendant 10 9 9 −12 secondes, soit environ 3 × 10 9 9 −20 = 3 × 10 387420469. années.

Pour tester le programme, vous pouvez remplacer le 9avec a 2, ce qui le fera s'arrêter à 10 2 2 −1 = 10 3 = 1000. (Utiliser a 3au lieu de a 2le fera arrêter à 10 3 3 −1 = 10 26 , , même avec les hypothèses optimistes ci-dessus, il ne sera pas atteint avant au moins quelques millions d'années.)

Ilmari Karonen
la source
3

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}
Personne93
la source
3

Haskell, 23 ans

main=interact$take$2^30

Ce programme se termine après la lecture de 1073741824 caractères stdin. S'il est exécuté sans canaliser aucune donnée vers stdin, vous devrez taper ce nombre de caractères sur votre clavier. En supposant que votre clavier dispose de 105 touches, évaluées chacune pour 100 000 cycles mécaniques et programmées pour générer des frappes au clavier non mortes, la répétition automatique est désactivée et votre prise de clavier permet 100 cycles de connexion, ce qui donne un nombre maximal de frappes par ordinateur de 1050000000, pas assez pour que le programme se termine.

Par conséquent, le programme ne se terminera que lorsque le meilleur matériel sera disponible en termes de nombre de cycles, ce qui n'est en réalité jamais dans cet univers en cours d'exécution. Peut-être la prochaine fois, lorsque la qualité sera prioritaire sur la quantité. Jusque-là, ce programme se termine en principe mais pas dans la pratique.

TheEspagnolInquisition
la source
Et si vous échangez des claviers à chaud au fur et à mesure?
Thomas
Cela est couvert par les 100 cycles de connexion de la prise clavier.
TheSpanishInquisition
Mais le point du problème est que le programme ne se terminent, quelque part après la mort thermique de l'univers. Ce programme ne peut éventuellement jamais se terminer; une fois l'entropie suffisamment élevée, vous n'aurez plus jamais de clavier à brancher.
abarnert
1
Je ne suis toujours pas convaincu. Si vous exécutez le programme à distance (ou dans une machine virtuelle), vous n'êtes pas limité par les capacités matérielles d'un seul ordinateur. Un milliard de coups, ce n'est vraiment pas si grave. De plus, le problème dit que l'ordinateur est en Unobtainium, et que le clavier devrait donc l'être également. Il peut donc gérer 2 à 30 frappes ...
Thomas
3

~ ATH, 56

Dans la langue fictive ~ ATH :

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

~ ATH est une langue insupportable pour travailler. Sa logique n’est composée que de boucles infinies, ou au mieux de boucles de construction interminable.

Beaucoup de codeurs ATH importent des constructions finies et lient les boucles à leur durée de vie. Par exemple, la boucle principale ici se terminera à la mort de l'univers, elle sera étiquetée U. De cette façon, vous ne devrez attendre que des milliards d'années pour qu'elle se termine au lieu de toujours.

Je m'excuse pour les violations des échappatoires limites; Je pensais que c'était trop pertinent pour le laisser passer.

Si cela a vraiment amusé quelqu'un, plus de détails: (1) , (2) , (3) , (4)

DBN
la source
2

Rubis (34)

La ligne ([0]*9).permutation.each{print}prend environ 2,47 secondes pour 9! imprime sur ma machine, alors que la ligne ([0]*10).permutation.each{print}prend environ 24,7 secondes pour 10! Je suppose que je peux extrapoler ici et calculer (24.7/10!)*470! seconds in yearsce qui est 6,87 * 10 ^ 1040, ce qui devrait être le temps d’exécution de:

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

JavaScript 68 62 caractères

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

Ceci utilise la fonction Ackermann qui peut être écrite en tant que

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

Son temps d'exécution augmente exponentiellement et son calcul est donc très long. Même si ce n'est pas l'anglais , vous pouvez avoir un aperçu de ses valeurs de retour. Selon le tableau, cela ackermann(5,1)équivaut à 2↑↑(65533)-3ce qui est, vous savez, très gros.

henje
la source
2
Certaines des mêmes optimisations que l’implémentation antérieure de la fonction Perl Ackermann peuvent en tirer parti.
Peter Taylor
J'ai dû oublier la solution Perl. Merci d'avoir fait remarquer cela.
henje
au lieu de n==0?X:Y, vous pouvez toujours le fairen?Y:X
Cyoce
2

Befunge '93 - 40 octets

(Programme 20x2)

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

Ce programme s'appuie sur des nombres aléatoires pour lui donner du retard. Les interprètes Befunge étant assez lents, ce programme devrait convenir. Et si ce n’est pas le cas, nous pouvons toujours l’agrandir horizontalement. Je ne sais pas exactement comment calculer le temps d'exécution prévu de ce programme, mais je sais que chacun? a une chance sur 50 de recommencer ou de changer sa position horizontale de 1. Il y a 18? Je pense que cela devrait être quelque chose dans les lignes de (18 ^ 2) !, dont Google dit qu'il est "Infinity"

EDIT: Oups je n'ai pas remarqué l'autre réponse Befunge, ceci est mon premier post ici. Pardon.

Rodolphito
la source
Hé, ne vous inquiétez pas de l’autre réponse trompeuse, ou, en général, du même langage que celui de quelqu'un d’autre. Je veux dire, personne ne va battre le mathlab, alors toutes les autres soumissions sont amusantes. Le mien était.
AndoDaan
2

APL, 10

Je ne pense pas que ce soit une réponse valable (car non déterministe), mais quoi qu'il en soit ......

{?⍨1e9}⍣≡1

Ce programme calcule une permutation aléatoire de 1e9 nombres ( ?⍨1e9) et se répète jusqu'à ce que deux sorties consécutives soient égales ( ⍣≡)

Donc, chaque fois qu'une permutation est calculée, elle a un 1 sur 1000000000! chance de se terminer. Et 1000000000! est au moins 10 10 8 .

Le temps nécessaire pour calculer une permutation est rendu inutile par la massivité de 1000000000! Mais certains tests montrent que c'est le cas O(n)et l'extrapolation donne environ 30 secondes.

Cependant, mon interprète refuse de prendre des entrées dans la fonction aléatoire supérieures à 2 31 -1 (j'ai donc utilisé 1e9), et la génération de permutations de 1 000 000 numéros a généré une erreur complète d'espace de travail. Cependant, conceptuellement, cela peut être fait avec un interpréteur APL idéal avec une mémoire infinie.

Cela nous amène à la possibilité d'utiliser 2 63 -1 à la place de 1e9 pour augmenter la durée d'exécution jusqu'à au moins 10 10 20 , en supposant une architecture 64 bits.

Mais attendez, l’architecture est-elle pertinente dans un interprète idéal? Hell no donc il n'y a pas de limite supérieure sur le temps d'exécution !!

TwiNight
la source
2

R, 45 octets

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

C'est un vieux fil, mais je ne vois pas de réponse R, et on ne peut pas en avoir!

Le temps d’exécution pour moi était d’environ 1s quand x avait 20 ans, ce qui laisse supposer un temps d’exécution de 2 ^ 9979 secondes.

Si vous remplacez le zéro par un 1, la sortie sera alors 2 ^ x, mais dans l’état actuel, la sortie est nulle quel que soit x (évite les problèmes de débordement).

JDL
la source
1

Javascript, 120 octets

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)

Peut être fait avec un minimum de mémoire (probablement moins d'un demi-mégaoctet) mais prend (probablement) environ 10 8.750 ans pour s'arrêter.

Incrémente à plusieurs reprises un BigInteger base-9 little-endian jusqu'à atteindre 9 10 4 -1 .

SuperJedi224
la source
1

Python 3, 191 octets

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)

Tout d'abord, f est une fonction factorielle récursive et ultra lente. Ensuite, il y a 9 * 10⁹⁹⁹ avec lui-même, ce qui génère une erreur OverflowError, mais cela ne se produit pas sur cet ordinateur Unobtanium. La boucle For Itération 9E999! ^ (9E999 ^ 9E999)! fois et il ne passe qu'à la prochaine itération, si 9E999! +1 ints aléatoires entre 0 et 9E99 * ^ i! sont tous égaux à 0 et à chaque itération de la boucle while, sa valeur est définie sur (9E999 ^ s) !. Euh, j'ai oublié que l'impression de s prend beaucoup de temps ...
Je sais que ce n'est pas la solution la plus courte, mais je pense que c'est vraiment efficace. Quelqu'un peut-il m'aider à calculer le temps d'exécution?

Mega Man
la source
1

La machine de Turing mais tant pis , 167 octets

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

Essayez-le en ligne!

Devrait exécuter le Busy Beaver à 6 symboles à 2 états à partir de la page Wikipedia .

7,412×dix36534

MilkyWay90
la source