Machine de Turing + dilatation temporelle = résoudre le problème d'arrêt?

15

Il existe des temps spatiaux relativistes (par exemple des temps spatiaux MH; voir Hogarth 1994) où une ligne du monde de durée infinie peut être contenue dans le passé d'un observateur fini. Cela signifie qu'un observateur normal peut avoir accès à un nombre infini d'étapes de calcul.

En supposant qu'il est possible pour un ordinateur de fonctionner parfaitement pendant une durée infinie (et je sais que c'est une grande question): on pourrait construire un ordinateur HM qui se déplace le long de cette ligne de monde infinie, calculant le problème d'arrêt pour un M. donné Si M s'arrête , HM envoie un signal à l'observateur fini. Si après un nombre infini de pas l'observateur ne reçoit pas de signal, l'observateur sait que M boucle, résolvant le problème d'arrêt.

Jusqu'à présent, cela me semble bien. Ma question est: si ce que j'ai dit jusqu'à présent est correct, comment cela modifie-t-il la preuve de Turing que le problème d'arrêt est indécidable? Pourquoi sa preuve échoue-t-elle dans ces espaces - temps ?

Marguerite
la source
Peut-être pertinent: researchgate.net/publication/… .
Martín-Blas Pérez Pinilla
1
L'observateur de durée infinie aura-t-il accès à une énergie infinie pour effectuer ses étapes de calcul infinies? (alternativement, un testeur de problème d'arrêt peut-il être formulé de manière réversible? Je ne le pense pas)
user253751
Certainement pertinent: chiark.greenend.org.uk/~sgtatham/infinity.html
Jules
@immibis: Oui, c'est le cas! J'ai étudié cela au collège.
Joshua
Notez que c'est une idée fausse courante qu'une machine de turing qui ne s'arrête pas doit «boucler». Cela implique une sorte d'état répété, ou de faire la même chose encore et encore. En fait, nous pouvons déterminer si une machine a ce comportement ou s'arrête, car elle fait l'un des deux. Les machines gênantes qui nous gâchent ne sont pas celles en boucle, mais plutôt celles qui tournent de manière chaotique de manière presque aléatoire, défiant tout sens de la régularité.
exfret

Réponses:

26

Notez que la preuve de Turing est une des mathématiques, pas de la physique. Dans le modèle d'une machine de Turing définie par Turing, l'indécidabilité du problème d'arrêt a été prouvée et est un fait mathématique. Par conséquent, la preuve de Turing n'échouera pas dans l'espace-temps, elle ne prouvera tout simplement rien sur la relation entre le problème d'arrêt et la dilatation du temps.

Cependant, ce que vous voudrez probablement savoir, c'est si une «machine de Turing à dilatation temporelle» peut résoudre le problème d'arrêt.

Si vous voulez étudier l'influence de la `` dilatation du temps '' sur une machine de Turing, vous devrez spécifier un modèle formel par lequel nous pouvons comprendre formellement ce que signifie pour une machine de Turing d'utiliser la dilatation du temps. Malheureusement, ce format n'est pas adapté pour fournir un modèle aussi formel (sauf si quelqu'un d'autre a écrit un article à ce sujet) car la création du modèle est beaucoup trop large.

Cependant, il n'est pas improbable qu'une certaine formalisation soit effectivement en mesure de résoudre le problème de l'arrêt. Cet article de Scott Aaronson, Mohammad Bavarian et Giulio Gueltrini examine les modèles de calcul en supposant qu'il existe des boucles dites de type fermé et conclut que le problème d'arrêt est en effet calculable dans ce modèle.

Lézard discret
la source
4
Peut-être aussi utile est que le formalisme d'une "machine hyper-turing" comme une machine Turong qui peut faire un nombre infini d'étapes en un temps fini est en effet un formalisme courant. Vous pouvez y trouver beaucoup de matériel utile.
Cort Ammon - Reinstate Monica
10

La machine de Turing est un modèle mathématique formel de calcul, elle ne répond à aucune limitation physique et ne se soucie pas des effets relativistes. Cela signifie que la preuve de Turing n'échoue pas, car la définition standard de la machine de Turing ne contient même pas une notion d '"espace-temps".

Ce que vous pouvez essayer de faire, c'est définir un modèle de calcul différent inspiré de la relativité. Encore une fois, ce ne sera qu'un objet formel, et la question de savoir s'il peut ou non résoudre le problème d'arrêt appartient au domaine des mathématiques et dépend de votre définition spécifique. Cependant, la vraie question est maintenant de savoir si ce nouveau modèle capture correctement les effets relativistes, c'est-à-dire s'il reflète vraiment notre physique et peut être mis en œuvre dans notre monde?

Vous pouvez voir une telle discussion concernant le calcul quantique. Nous avons une définition formelle des "machines de Turing quantiques", et leur puissance de calcul exacte reste un problème ouvert en mathématiques (même pas proche du problème d'arrêt cependant). Pourtant, vous pouvez affirmer que cette définition ne reflète pas vraiment notre compréhension de la physique quantique, et une meilleure est nécessaire. Il y a arguments qui suggèrent que de telles machines ne peuvent même pas être construites, donc leur puissance exacte n'a aucun effet sur la (forte) thèse de Church-Turing.

Revenons à votre question. Il existe une notion formelle d'une machine de Turing à temps infini , mais pour qu'elle ait un effet sur la thèse de Church-Turing, vous devez qu'elle existe dans la pratique. Vous pourriez être intéressé par l' article de Scott , qui contient une section sur les calculs utilisant des effets relativistes, bien qu'il semble que les arguments naïfs soient sans espoir (dans le sens où ils ne sont pas pratiques, car le coût du temps est remplacé par le coût de l'énergie).

Ariel
la source
1
Ré. "... pour que cela ait un effet sur la thèse de Church-Turing, vous avez besoin qu'elle existe dans la pratique." - les machines de Turing ne sont-elles pas aussi des machines idéalisées qui ne peuvent pas exister en pratique?
marguerite
1
En effet, il ne fait que refléter (ou du moins tente de faire) notre intuition sur ce qu'est une "machine informatique". C'est pourquoi la thèse de Church-Turing est une thèse et non un théorème mathématique. Il prétend seulement de manière informelle que les machines Turing capturent la véritable puissance de calcul qui existe dans notre monde.
Ariel
Mon point est le suivant: pourquoi une machine de Turing à durée infinie doit-elle exister en pratique pour qu'elle ait un effet sur le CTT, alors que les machines de Turing standard n'existent pas non plus en pratique?
marguerite
1
Une formulation de la thèse de Church-Turing est la suivante: chaque modèle de calcul possible réalisable dans notre monde ne dépasse pas la puissance de la machine de Turing. La thèse elle-même est définie par rapport à un modèle au sol (à savoir la machine de Turing).
Ariel
J'ai posé une question de suivi parce que même après avoir parcouru les diapositives publiées, je ne comprends pas vraiment l'affirmation selon laquelle une machine de Turing quantique pratique ne peut pas être construite. (2e fois pour publier ce commentaire, pointe désormais vers QC.SE au lieu de CS.SE)
BurnsBA
7

La preuve de Turing montre qu'aucune machine Turing ne peut résoudre le problème de l'arrêt, quel que soit le temps que vous lui accordez. Si votre vaisseau spatial a utilisé la dilatation du temps pour donner à un ordinateur un milliard d'années de travail, il pourrait ne pas être en mesure de vous dire quelque chose de plus précis que «Pas encore».

Apparemment, (merci, @DiscreteLizard!) Si vous avez un voyage dans le temps qui ne peut pas provoquer de paradoxes, vous pouvez configurer une boucle temporelle qui provoquerait un paradoxe si l'ordinateur ne peut pas prouver si la machine Turing s'arrête. Soit il reçoit la réponse du futur et la retransmet à lui-même, soit il s'exécute pour toujours (et, intelligemment, renvoie une superposition quantique qui se résout en une boucle de temps stable). Mais, avant d'essayer, assurez-vous qu'il est sûr de provoquer un paradoxe de voyage dans le temps.

Davislor
la source
2
"Les données sont encore insuffisantes pour une réponse significative."
Robert Columbia
Notez que la principale raison pour laquelle j'ai mentionné les machines Turing sous des boucles fermées de type temporel est qu'il existe une `` modification physique '' du modèle de machine Turing de telle sorte que le problème d'arrêt est calculable par cette machine. Il semble que d'autres en savent plus que moi sur la dilatation du temps, mais cet exemple me fait au moins hésiter à faire de telles affirmations à moins qu'une formalisation de la dilatation du temps ne soit donnée.
Lézard discret
@Discretelizard C'était une grande contribution à la discussion. Je ne suis pas sûr de bien comprendre l'intention du PO, mais la dilatation temporelle relativiste est un véritable concept en physique moderne, et j'ai répondu en supposant qu'il utilisait la définition standard du terme.
Davislor
@Davislor Bien sûr, la dilatation du temps est bien définie, en physique . Une machine de Turing est un objet mathématique . Pour autant que je sache, le mieux que nous pouvons faire pour combiner les deux est de créer une `` analogie physique '' d'une machine de Turing et de montrer formellement comment cela interagit avec la dilatation du temps. C'est (un exemple de) ce que je veux dire par «formalisation». Je ne pense pas qu'il existe une façon unique de formaliser cela et que les résultats puissent différer, d'où mon hésitation à dire quoi que ce soit de concluant à ce sujet.
Lézard discret
Cela dit, il pourrait être possible que la réponse soit «non» à toute formalisation raisonnable, mais une telle affirmation dépasse au moins mon expertise.
Lézard discret
5

Une objection est que vous avez défini un processus qui peut produire une entropie infinie dans une région compacte et qui semble le faire dans un segment fini du passé de l'observateur. Cela signifie quelques choses

  • L'entropie de calcul dans la région compacte dépasse le Bekensteinlié à l'entropie (laquelle limite est proportionnelle à la surface de la région), de sorte qu'il s'effondre dans un trou noir (instantanément) et aucun signal ne peut jamais vous atteindre depuis son intérieur. (La métrique de Kerr décrit un espace-temps MH. Le processus infini ne s'achève que lorsque l'observateur passe dans l'horizon interne des événements. Sans tenir compte de l'incertitude actuelle sur la physique d'un tel passage, aucun observateur distant n'a jamais accès au résultat du calcul. - seul l'observateur qui a disparu dans le trou noir a le résultat. Ce n'est pas une description d'un processus de calcul utile. Pour paraphraser: "Nous avons un oracle qui produit la bonne réponse à toute question que vous posez en temps constant dans un tel une manière que la réponse n'existe qu'au moment où elle est détruite en la jetant dans un trou noir. ")
  • Une machine de Turing détruit des informations chaque fois qu'elle écrase un symbole sur une bande, donc selon le principe de Landauer , un calcul fini sur une ligne de monde infinie compressé en un segment fini dans le cône de lumière du passé doit être observé pour nécessiter une puissance infinie et émettre chaleur infinie pendant le temps infinitésimal observé. Autrement dit, étant donné qu'un arrêt est réalisé en temps fini, il est obtenu instantanément du point de vue de l'observateur externe, de sorte que toute l'énergie est consommée instantanément et toute la chaleur est dégagée instantanément. Alternativement, si le calcul ne s'arrête pas, la région compacte consomme en continu une puissance infinie et émet une chaleur infinie. Résultat net: encore un trou noir.
  • Alternativement, le principe Landauer ne s'applique pas à l' informatique réversible et il existe des machines de Turing réversibles ( universelles ) . Cependant, une telle machine de Turing nécessite la capacité de représenter tout l'espace des états de calcul potentiels, qui est exponentiel dans la taille de la quantité de bande utilisée, se heurte donc rapidement à la limite de Bekenstein. Nous finissons par pouvoir éviter le problème de la chaleur uniquement en nous limitant aux bandes de longueur limitée. De manière équivalente, nous avons une limite supérieure sur la longueur de bande utilisable contrôlée par la surface de la région qui a une ligne du monde infinie. Si vous ne tenez pas compte de cela et que votre calcul utilise trop de bande, vous obtenez à nouveau un trou noir.

C'est une question ouverte intéressante si et comment ces contraintes s'appliquent aux ordinateurs quantiques. Il se pourrait bien que la complexité d'un calcul réalisable par un ordinateur quantique soit limitée par la surface de l'ordinateur. Il nous faudra donc peut-être doubler la surface d'un ordinateur quantique extrême pour obtenir un qubit de calcul utilisable de plus. Cela conduit rapidement à des ordinateurs peu volumineux.

Eric Towers
la source
1

Citation de Bangs, Crunches, Whimpers et Shrieks:

Lampes Thomson, super πles machines et les ordinateurs platoniciens sont des jouets de philosophes; ils ne peuvent survivre que dans l'atmosphère de serre des revues de philosophie. En fin de compte, les espaces-temps M — H et les supertâches qu'ils souscrivent peuvent également se révéler être des fictions récréatives pour les relativistes généraux sans rien de mieux à faire. Mais pour arriver à cette dernière position, il faut d'abord résoudre certains des problèmes de fondation les plus profonds de la relativité générale classique, y compris la nature des singularités et le sort de la censure cosmique. C'est ce lien avec les problèmes réels de la physique qui les rend dignes de discussion.
Il existe également des liens avec la philosophie des mathématiques et la théorie de la calculabilité. En raison de scrupules finitistes, certains philosophes ont douté qu'il soit significatif d'attribuer une valeur de vérité à une formule d'arithmétique de la forme(X1)(X2)(Xn)F(Xl,X2,,Xn). Il me semble peu attrayant de faire dépendre la vérité des énoncés mathématiques des contingences de la structure de l'espace-temps. Les types d'arrangements examinés ci-dessus peuvent être utilisés pour décider de la valeur de vérité des affirmations de l'arithmétique avec une forme normale prénex qui est purement existentielle ou purement universelle. (Le dernier théorème de Fermat, par exemple, a une forme purement universelle.) Pour une telle assertionγ1 est prêt à fonctionner pour vérifier la liste (infiniment infinie) de n-des couples de nombres à la recherche d'un falsificateur ou d'un vérificateur selon que l'assertion à tester est universelle ou existentielle, et γ1tire de ces travaux une connaissance de la valeur de vérité de l'assertion. Mais dès que des quantificateurs mixtes sont impliqués, la méthode échoue. Cependant, Hogarth (1994) a montré comment des arrangements plus compliqués dans les espaces-temps relativistes généraux peuvent en principe être utilisés pour vérifier la valeur de vérité de toute assertion arithmétique de complexité quantifiée arbitraire. Dans un tel espace-temps, il est difficile de voir comment maintenir l'attitude selon laquelle nous n'avons pas une notion claire de la vérité en arithmétique.
Martín-Blas Pérez Pinilla
la source