Calculs infinis en temps fini

C'est probablement une idée stupide, mais supposons que nous ayons un ordinateur programmé pour effectuer une séquence infinie de calculs et supposons que le calcul prenne secondes pour terminer. Cet ordinateur peut alors effectuer un nombre infini de calculs en un temps limité. $i^\text{th}$ $1/2^i$

Pourquoi est-ce impossible? Y a-t-il une limite inférieure sur le temps nécessaire pour effectuer un calcul non trivial?

computability computation-models dsaxton
la source

Concept connexe, calculs infinis utilisant l'énergie finie: l'intelligence éternelle de Dyson .

Peter

Réponses:

Ce "genre" d'ordinateur est connu comme une machine Zeno . Son modèle de calcul appartient à une catégorie appelée hyper- calcul . Les modèles hyper-informatiques sont des abstractions mathématiques et, en raison de la manière dont ils sont définis pour fonctionner, ils ne sont pas physiquement possibles.

Prenez votre machine Zeno par exemple. Si nous imaginons que la machine Zeno est une machine à calculer de toute sorte, qu'elle utilise un boulier ou un circuit intégré n'a pas d'importance. Supposons que les données de programme utilisées par la machine lui soient transmises par une bande infiniment longue de symboles (tout comme une machine de Turing).

Bien sûr, nous savons par les mathématiques que:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n$

que nous disons est égal à . Ainsi le calcul devrait se terminer en 1 seconde car la somme converge absolument. $1$

Mais cette convergence dépend, bien sûr, de allant vers (et atteignant) l'infini. Au sens physique, cela signifie qu'à mesure que le temps requis pour chaque calcul diminue, la "tête de lecture" de la machine à calculer devra se faufiler de plus en plus rapidement sur les symboles de la bande. À un certain point, cette vitesse dépassera la vitesse de la lumière. $n$

Donc, pour répondre à votre deuxième question, la limite la plus basse possible d'un calcul serait probablement de l'ordre du temps de Planck, étant donné la vitesse de la lumière comme principal facteur limitant dans les modèles de calcul théoriques, mais physiquement plausibles.

Théorie de tout
la source

Il y a aussi les besoins en énergie pour chaque opération, retourner un peu fois nécessite plusieurs ordres de grandeur de plus d'énergie que dans notre soleil

2^{256}

$2^{256}$

monstre à cliquet

Ce programme: 10: GOTO 10 se termine-t-il sur la machine Zeno?

Cano64

En termes plus simples, les mathématiques présupposent qu'un "calcul" a une portée infiniment divisible. Cependant, ce n'est le cas avec aucune machine physique, car vous atteignez finalement un point où vous avez atteint la plus petite unité de travail que la machine peut effectuer. Il n'est pas possible de continuer à subdiviser le calcul après ce point, même si les mathématiques le permettent. En d'autres termes, la machine craque bien avant que vous ne vous approchiez réellement de la fin de la série infinie de calculs. À un certain moment, le temps par calcul cesse de diminuer et vous finissez par avoir besoin d'un temps infini.

2015

@ Cano64 Je ne pense pas. Je crois que le critère de décidabilité en hyper-calcul est que la somme de temps du calcul converge absolument.

Théorie de tout le

Le temps nécessaire à un calcul primitif est limité par la vitesse de la lumière et la taille des atomes, pour autant que nous comprenions la physique ce même jour, le 15 septembre 2015.

L'unité de calcul doit être construite à partir de quelque chose de taille non nulle (atomes) et pour que le calcul fonctionne, l'électricité ou la lumière devra la traverser, ce qui sera limité par le temps qu'il faut à la lumière pour traverser le non -distance nulle.

Dave Clarke
la source

Un exemple concret dans l'histoire récente de la science repoussant les limites est la magnétorésistance géante , une découverte lauréate d'un prix Nobel qui a permis une densité de données sur des disques durs jusque-là impossible. Il y en a beaucoup, beaucoup plus si vous revenez en arrière; essayez d'expliquer la possibilité d'un "smartphone" à une personne à partir de 1500 après JC. (Ils peuvent simplement vous brûler en tant que sorcière, alors soyez prudent.) Je pense donc que nous ne devrions pas supposer que nos connaissances actuelles en physique induisent des limites strictes sur ce qui est possible.

Raphael

-1

$\Sigma_{n=1}^\infty (\frac{1}{2})^n$ $1$

$\frac{1}{2}$ $\frac{1}{4}$ $\frac{3}{4}$

$c_1$ $c_1$

Edit : Comme l'a noté @aroth, cette analogie suppose que nous pouvons continuer à diviser l'eau pour toujours; qu'il n'y a pas de plus petit atome indivisible. Ce qui soulève le point intéressant (je pense) que nous devons également supposer que le temps est arbitrairement divisible pour que le calcul se termine en temps fini.

epa095
la source

"et tout aussi clairement, vous aurez toujours plus d'eau dans le seau bleu à verser" - Pas nécessairement. Avec un appareil de coulée suffisamment précis, vous finirez par atteindre un point où il y a 2 molécules d'eau dans le seau bleu. Puis 1 molécule. Soit vous versez la dernière molécule, soit vous ne le faites pas. Ou vous le décomposez en ses atomes de base, mais ce n'est plus de l'eau (ou versable à STP). Le fait est que vous arriverez à la dernière molécule d'eau bien avant d'arriver à la fin de la série infinie, donc il n'y aura pas "toujours" d'eau dans le seau bleu.

2015

@aroth: oui, pour que l'analogie fonctionne, vous devez considérer l'eau comme une "densité" satisfaisante, une sorte de "toujours divisibilité". Votre point est intéressant car il met en évidence quelque chose d'important; pour que le calcul se termine en temps fini, le temps doit également être dense / toujours divisible. S'il existe un temps le plus court, une unité de temps atomique non divisible, alors le calcul infini prendra un temps infini (ou chaque calcul ne doit pas prendre de temps chacun après un certain point).

epa095

\sum_{i = 1}^{\infty} 2^{- i}

$\sum_{i=1}^\infty 2^{-i}$

2^{- i}

$2^{-i}$

@ david-richerby: N'est-ce pas reformuler le problème d'une manière différente, donner une manière plus simple d'y penser, exactement ce que c'est que de fournir de l'intuition? Notez également que vous reformulez également le problème, de la durée à la somme des nombres rationnels. Un pas (extrêmement) court oui, mais un rappel tout de même. Si vous connaissez la convergence de sommes de nombres rationnels, ce retraitement le rend plus facile à comprendre, mais pour certains, je suis certain qu'il est plus facile de le comprendre en termes d'eau. C'est du moins ainsi que j'ai compris pour la première fois pourquoi certaines sommes infinies convergeaient et d'autres non.

epa095

@ epa095 Fournir de l'intuition implique d'expliquer une situation inconnue en se référant à une situation familière et d'utiliser la familiarité avec une situation pour aider à comprendre l'autre. Vous ne faites pas cela: vous essayez d'expliquer une situation inconnue (calculer une somme convergente infinie) par une autre (verser des seaux d'eau divisible à l'infini avec une précision parfaite). Les gens qui connaissent la convergence des sommes n'ont pas besoin de l'analogie; pour les personnes qui ne connaissent pas la convergence des sommes, renommer "nombre rationnel" en "quantité d'eau hypothétique" n'aide pas.

David Richerby