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 ⁰⁰⁰ 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}

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.

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 ⁰⁰⁰ * 150 000.

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

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.

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.

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.

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.

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.

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 ⁷ secondes en un an, donc en attente 10 ¹⁰⁰⁰⁰ 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.

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.

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.

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.

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.

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 ^ ¹⁰¹⁷ octets. Sur un processeur moderne avec une bande passante mémoire maximale de 21 Go / s ou 6,63x10 ^ ¹⁷ 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.

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 ³⁵²¹⁸ 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.

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

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

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.

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.

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 ³ = 1000. (Utiliser a 3au lieu de a 2le fera arrêter à 10 ^{3 3 −1} = 10 ²⁶ , , même avec les hypothèses optimistes ci-dessus, il ne sera pas atteint avant au moins quelques millions d'années.)

Autohotkey 37

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

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.

~ 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)

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}

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.

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.

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 ³¹ -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 ⁶³ -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 !!

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).

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} .

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?

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 \times 10^{36534}$