Quelles sont les limites du calcul dans cet univers?

17

Je comprends que l'exhaustivité de Turing nécessite une mémoire illimitée et un temps illimité.

Cependant, il existe une quantité finie d'atomes dans ce service, ce qui rend la mémoire limitée. Par exemple, même si est irrationnel, il n'y a aucun moyen de stocker plus d'un certain nombre de chiffres même si tous les atomes de l'univers ont été utilisés à cette fin.π

Quelles sont alors les limites de calculabilité d'une machine de Turing implémentée (qui pourrait utiliser toutes les ressources de l'univers mais pas plus) en fonction des limites de l'univers? Quel est le nombre maximum de chiffres de ? Y a-t-il des articles sur ce sujet qui pourraient être intéressants à lire?π

Bonne personne
la source
1
Sujet éventuellement lié: un ordinateur peut-il se simuler dans le cadre d'un monde simulé .
MS Dousti
7
Il y a un essai amusant de Scott Aaronson à ce sujet: scottaaronson.com/writings/finite.html
Artem Kaznatcheev
2
Vous pourriez être intéressé par la discussion autour de cette question . Yarosloav Bulatov a publié un lien vers une version de vulgarisation scientifique du document de Lloyd Peter Shor lié ci-dessous, mais, malheureusement, le lien semble être rompu maintenant. J'ai lu ce papier à l'époque, mais je ne l'ai pas enregistré et je ne me souviens pas du titre exact.
Aaron Sterling

Réponses:

34

Seth Lloyd a un article sur le sujet. Vous avez besoin d'énergie pour calculer, mais si vous mettez trop d'énergie dans une petite région, cela forme un trou noir. Cela ralentit le temps (ce qui rallonge le temps nécessaire au calcul) et tout calcul effectué à l'intérieur d'un trou noir est perdu, car les résultats ne peuvent pas être extraits du trou noir et utilisés. Seth calcule les limites de la quantité de calcul possible et montre que pour certaines mesures de calcul, l'environnement le plus intensif en calcul possible dans l'univers serait celui entourant un trou noir.

Peter Shor
la source
10
@AaronRoth J'étais coincé dans un trou noir. Accepté maintenant.
Bonne personne du