Des problèmes indécidables limitent les théories physiques

L'existence de problèmes indécidables implique-t-elle immédiatement la non-prévisibilité des systèmes physiques? Considérons le problème de l'arrêt, d'abord nous construisons un UTM physique, disons en utilisant la construction basée sur un circuit habituel. Il ne peut alors y avoir aucune théorie physique décidable qui puisse déterminer, compte tenu de n'importe quel réglage d'entrée des circuits, si le circuit s'arrêtera. Cela semble banal, mais cela ne nous donne-t-il pas une sorte d'imprévisibilité faible sans référence à des considérations quantiques ou chaotiques? De plus, nous pouvons renforcer l'argument ci-dessus en notant qu'il n'y a rien de spécial à propos de l'UTM basé sur le circuit, nous avons donc que le comportement d'un système physique est en général indécidable à n'importe quel niveau où une UTM peut être construite.

Edit: comme l'ont souligné Babou et Ben Crowell, ma construction de circuit suggérée n'est qu'un LBA. Comme je l'ai expliqué dans les commentaires, je trouve facile et intuitif d'imaginer une machine qui est physique mais qui n'est pas limitée linéairement. Construisez simplement une machine (robot) qui peut se déplacer mécaniquement de gauche / droite sur une entrée arbitrairement plusieurs fois, et supposez qu'elle a une source d'alimentation finie mais non expirante. Maintenant, nous rencontrons également le problème que l'univers est fini, mais cela nous permet de conclure que l'univers est fini, ou que la conséquence espérée à l'origine doit être vraie (ce serait toujours une conclusion surprenante à tirer de l'argument ci-dessus) .

Cela a été initialement conçu comme un commentaire, car il contourne un peu la question. Mais je pense qu'il répond à sa manière.

Ce qui est connu ou tenté jusqu'à présent montre que la connexion de la théorie du calcul avec la physique peut être une entreprise assez subtile, et je crains que l'approche suggérée dans la question soit probablement un peu trop grossière. Je ne suis pas sûr que ce soit beaucoup mieux que l'argument classique selon lequel, tout étant fini, tout ce dont nous avons besoin est la théorie des automates à états finis, et que l'étude des machines de Turing est une perte de temps. (Pas ma vue des choses)

Pourquoi ces problèmes doivent-ils être traités avec prudence

Je devrais probablement motiver la comparaison ci-dessus avec l'argument des automates finis. Ma perception est que la calculabilité est, peut-être même plus que la complexité, une théorie asymptotique: ce qui compte, c'est ce qui se passe à l'infini. Mais nous ne savons pas si l'univers est fini ou infini. Si elle est finie, alors à quoi bon considérer des calculs infinis. Ce qui suit concerne la physique et je ne suis pas physicien. Je fais de mon mieux pour être précis, mais vous avez été prévenu .

Nous voyons souvent le Big Bang comme un «temps» où l'univers entier était un tout petit quelque chose, avec une très petite taille. Mais si elle avait une taille à un moment donné, comment s'est-elle transformée en quelque chose d'infini plus tard. Je n'essaye pas de dire que c'est impossible ... Je n'en ai pas la moindre idée. Mais il se pourrait que ce soit toujours infini.

$r$$r$en raison de l'expansion est égale à la vitesse de la lumière. D'après ce que nous savons actuellement, sans une variation future de la vitesse d'expansion, rien en dehors de cette sphère ne nous préoccupera jamais. Donc, l'univers est fini pour nous à toutes fins pratiques. En fait, les choses sont encore pires si vous considérez le contenu de cet univers pertinent: il rétrécit (à moins qu'il y ait un processus de création). La raison en est que la sphère s'étend au-delà de son propre diamètre, emportant avec elle une partie de son contenu qui devient également hors de propos. Remarque: cette sphère n'est pas ce qu'on appelle l'univers observable (qui dépend de l'âge de l'univers), elle est beaucoup plus grande.

Ainsi, non seulement «notre» univers est fini, mais ses ressources pourraient diminuer. Il est possible que dans tant de milliards d'années, seule notre galaxie soit toujours pertinente pour nous (en supposant que nous existons toujours), avec la galaxie d'Andromède qui frappera la Voie lactée avant cette date.

Eh bien, je ne sais pas ce qui est considéré comme établi à l'heure actuelle, mais cela montre au moins que supposer l'infini est une grande hypothèse.

Cependant, est-ce le cas que les limitations physiques nous empêchent d'utiliser la théorie de la calculabilité. Tout ce qui peut être conclu à partir de ce qui précède est qu'il peut être déraisonnable de tirer des conclusions physiques des travaux théoriques sur les machines de Turing et le problème d'arrêt.

Cependant, les techniques concernées peuvent également donner des résultats utiles lorsqu'elles sont appliquées à des dispositifs ou formalismes qui ne sont pas complets de Turing. Je n'essaierais pas d'entrer dans les détails, ne serait-ce que parce que la complexité algorithmique n'est pas mon domaine, mais je suppose que, si la structure de l'univers est discrète, la complexité pourrait être sous une forme ou une autre pertinente pour le comportement de certains phénomènes. Bien sûr, ce n'est qu'une spéculation sauvage de ma part. Certaines des recherches auxquelles je fais référence ci-dessous sont liées à ces problèmes de discrétion.

Quelques exemples de travaux concernant la physique et la théorie des calculs

Il existe un corpus important de travaux visant à lier le calcul et la physique, dont je connais à peine la plupart. Donc, s'il vous plaît, ne vous fiez pas à quoi que ce soit que je pourrais dire , mais prenez-le simplement comme pointeurs pour rechercher des travaux potentiellement pertinents.

Une bonne partie de ce travail concerne les aspects thermodynamiques, comme la possibilité de calcul réversible sans coût énergétique. Je pense que cela est lié à la programmation fonctionnelle car ce sont les effets secondaires qui coûtent de l'énergie (mais ne me faites pas confiance). Vous pouvez prendre wikipedia comme introduction, mais Google fournira de nombreuses références .

Il y a aussi du travail qui essaie de lier la thèse de Church-Turing et la physique, impliquant la densité de l'information entre autres. Voir par exemple:

• La thèse de Church-Turing physique et les principes de la théorie quantique

• Autour de la thèse de Church-Turing physique: les automates cellulaires, les langages formels et les principes de la théorie quantique ,

• Thèse de physique et de Church-Turing .

Je me souviens vaguement d'avoir vu d'autres prises de vue intéressantes à ce sujet, mais cela m'échappe en ce moment.

Ensuite, vous avez le travail de Lamport sur la synchronisation et la relativité des horloges dans les systèmes distribués .

Et, bien sûr, vous avez l'informatique quantique qui modifie apparemment certaines complexités temporelles (réalisables), bien qu'elle n'affecte pas la calculabilité.

Une autre prise est le travail de Wolfram sur la modélisation des lois physiques avec des automates cellulaires , bien que les avantages réels de ce travail semblent contestés.

Je pense qu'essayer de comprendre tout ce travail pourrait vous rapprocher de la façon dont vous pouvez lier certaines connaissances en calculabilité avec (comme impliquant) les limitations théoriques du monde physique, bien que la tendance jusqu'à présent soit davantage de lier les limitations de calculabilité (en tant que conséquences). des) propriétés de l'univers physique.

Un problème possible dans tout cela est l'auto-intégration de toutes nos théories (mathématiques, calcul, physique, ...) dans les limites de concepts syntaxiquement exprimables (c'est-à-dire par un langage) qui pourraient fixer une limite au pouvoir expressif de notre science. Mais je ne sais pas si la phrase précédente a un sens ... désolé, c'est le mieux que je puisse faire pour exprimer un doute tenace.

En guise de déception personnelle , j'ajouterais que les physiciens (au moins sur http://physics.stackexchange.com ) ne sont pas très amicaux pour discuter de ce que d'autres sciences pourraient avoir à dire sur les problèmes physiques (bien qu'ils soient tout à fait disposés à discuter ce que la physique peut avoir à dire sur les autres sciences).

La question porte en partie sur la non- prévisibilité des systèmes physiques . L'indécidabilité apparaît dans quelques problèmes de physique. Wolfram, Undecidability and Intractability in Theoretical Physics (ou ici ) en est un premier aperçu, et ce domaine continue de s'étendre. Cependant, une meilleure façon de comprendre l'imprévisibilité inhérente physique est davantage via ce que l'on appelle la "dépendance sensible aux conditions initiales" alias l' effet papillon . Cela peut être étudié en utilisant l' attracteur de Lorentz comme modèle semi-jouet.

La question est intéressante (vous voudrez peut-être vérifier une question connexe "Y a-t-il un lien entre le problème d'arrêt et l'entropie thermodynamique?" )

Le cœur du problème est ce qui vient en premier des mathématiques ou de la physique? Eh bien, la physique est la réponse . Une citation d'Einstein dit: " le genre de mathématiques que nous faisons, dépend du monde dans lequel nous vivons " (si je ne me trompe pas, c'est dans "Einstein, philosophe-scientifique") (et un autre connexe, et légèrement paraphrasé "La nature fait ne se soucient pas de nos difficultés mathématiques. Il intègre empiriquement " ). Ainsi, dans ce sens, certaines caractéristiques physiques se reflètent dans le symbolisme et la procédure mathématiques. Mais on peut également considérer que les mathématiques définissent la physique (une opinion assez populaire dans certains cercles).

Il y a un passage dans l'introduction du livre "Linear Algebra" de J B. Fraleigh, R A. Beauregard (un bon livre sur le sujet et un point que je voulais aborder si l'occasion se présentait )

Les nombres n'existent que dans nos esprits. Il n'y a aucune entité physique qui est le numéro 1. S'il y en avait un, je serais à la place d'honneur dans un grand musée des sciences, et au-delà, il déposerait un flot constant de mathématiciens regardant 1 avec émerveillement et admiration.

Pourtant ce n'est pas vrai , il y a bien quelque chose que nous expérimentons et qui est un (littéralement) , le soleil (attention pas aux étoiles la nuit ni à la lune qui n'est pas perçue comme une en toutes circonstances, le soleil, le seul et le seul visible chose dans le ciel à la lumière du jour). (Et en effet, il a été historiquement un objet d'honneur et de crainte de l'humanité). On peut continuer et discuter d'autres choses que nous ressentons comme deux ou trois et quatre ( deux mains, cinq doigts et ainsi de suite), mais le point principal a été donné (pour plus d'informations, recherchez " pré-histoire et histoire des systèmes de numérotation" ")

Disons une minute qu'un résultat mathématique énoncerait quelque chose mais alors une théorie physique fournirait une procédure pour réaliser l'opposé (en fait une preuve constructive de l'opposé). Ensuite, quelque chose ne va pas, ils sont liés en particulier lorsqu'ils utilisent exactement le même formalisme. Il est intuitif que ceux-ci soient liés d'une manière ou d'une autre.

Par exemple, un résultat d'impossibilité mathématique limiterait la description mathématique d'une théorie physique qui aurait besoin d'un tel résultat et ainsi de suite. Un exemple que je peux utiliser en ce moment est la soi-disant "théorie de tout". Il est censé décrire sous forme mathématique toutes les interactions physiques qui ont lieu, donc en fait tout décrire. Cependant, selon le théorème de Goedel, on sait qu'une telle description serait incomplète dans un sens ou dans un autre. Cela signifie-t-il quelque chose sur le monde dans lequel nous vivons? Le plus probable.

Mais les résultats d'impossibilité sont connus en termes purement physiques et la plupart d'entre eux sont liés à la thermodynamique. Par exemple "La chaleur passe du chaud au froid". C'est un résultat impossible. Mais cela limite également tout résultat mathématique qui impliquerait (lorsqu'il est appliqué dans le contexte approprié) que la chaleur passe du froid au chaud , cela ne se produit pas. Les mathématiques peuvent donc être limitées par des termes physiques . La vraie question est de savoir quel est le lien exact (le cas échéant) entre ces deux et c'est une question très intéressante avec des résultats intéressants et de grande portée. Par exemple, vous pouvez vérifier le travail de G. Chaitin qui concerne la théorie de l'information, les théorèmes de Goedel et les systèmes bio-physiquespour un début. Certaines autres connexions ont déjà été mentionnées, comme l'informatique réversible, l'informatique quantique, etc.

Enfin, n'oubliez pas que la physique s'appuie sur l'expérience pour formuler et vérifier des choses et non sur des preuves symboliques . (A) La description mathématique d'une théorie physique est importante en termes de calculs, donc une mathématique problématique peut limiter ou poser des problèmes dans la puissance de calcul de la théorie, l'expérience reste néanmoins. Et rappelez-vous que les physiciens sont généralement parmi les créateurs de nouvelles mathématiques selon les besoins (par exemple, calcul et équations différentielles, probabilités, analyse des tenseurs, procédure de renormalisation en mécanique quantique, régularisation analytique, etc.)

En ce qui concerne votre exemple de connexion d'imprévisibilité avec une MT, la connexion peut être effectuée et cela peut nécessiter une bande illimitée à condition que la machine doive calculer avec une précision infinie (c'est-à-dire des nombres irrationnels / transcendantaux qui ne sont en aucun cas exclus d'un physique système). Ensuite, une machine LBA ne sera pas assez puissante pour calculer un système physique donné et on entre dans la bande UTM infinie qui a un problème d'arrêt. La question de savoir si l'imprévisibilité peut être attribuée aux conditions initiales (la définition formelle enseignée du comportement chaotique) ou au calcul lui-même n'est pas essentielle, car elle ne fait que déplacer le problème à un autre endroit au lieu de l'adresser.

Babou,

C'est en effet une question très intéressante mais comme dit plus haut beaucoup de littérature a été produite sur le sujet. Le moins que vous puissiez dire une fois que vous avez lu tout cela, c'est que le mappage de l'UTM sur des systèmes physiques est loin d'être simple - même si l'idée est séduisante.

Personnellement, j'aime partir du concept de calcul réversible introduit par Landauer et mentionné dans les réponses précédentes. Il semble y avoir un lien conceptuel entre l'entropie et l'UTM.

Pensez-y de cette façon: imaginez que vous voulez marcher du point A au point B (géographiquement distinct) en utilisant un plan déterministe (c'est-à-dire un certain nombre d'étapes qui peuvent être écrites à l'avance comme un UTM: marchez tout droit sur 100 m, tournez à droite à la boulangerie, marchez 50m etc.). Vous pouvez marcher une fois sur la distance. Deux fois. Trois fois. Combien de fois pouvez-vous le faire? À moins d'inclure un stock infini de nourriture et d'eau dans votre plan, vous devrez vous arrêter après un nombre limité de voyages. Mais bien qu'une bande UTM soit infinie, le nombre d'étapes de la MT elle-même doit être écrit en un nombre fini de caractères. Par conséquent, votre plan ne peut pas inclure une quantité infinie de nourriture et d'eau.

Maintenant, l'énergie est une quantité conservatrice. On pourrait donc penser qu'un nombre limité de dispositions devrait suffire. Mais ce n'est clairement pas votre problème ici. Même si vous voyagez très lentement entre A et B, votre corps transformera votre nourriture en quelque chose que vous ne pourrez plus consommer. Notez que si vous essayez d'échapper à ce problème et d'aller INFINIMENT lentement (quasi-statiquement entre A et B), vous ne pouvez plus écrire votre "plan" avec un nombre fini de caractères. C'est donc l'augmentation de l'entropie thermodynamique (dégradation des aliments et de l'eau par le traitement de votre corps) qui semble limiter le nombre de voyages que vous pouvez effectuer tout en respectant un plan déterministe (c'est-à-dire une UTM).

Si c'est le cas, l'imprévisibilité de la MT doit être associée à l'augmentation de l'entropie thermodynamique.Remarquez comment cela semble assez contre-intuitif (comme dit précédemment ce type de cartographie est loin d'être trivial): à l'infini l'augmentation de l'entropie thermodynamique conduit à un équilibre c'est-à-dire quelque chose de stable; mais la même limite infinie de l'UTM correspondante conduit à un comportement aléatoire (c'est-à-dire que nous ne savons pas quel type de sortie). C'est encore plus frappant avec une balle roulant sur une courbe convexe avec des frottements: l'entropie thermodynamique fait que la balle s'arrête au bas de la courbe, ce qui est assez facile à prévoir; mais l'UTM équivalent vous dira que "quelque chose de aléatoire" se produit à la fin qui ne peut pas être prédit. Est-ce que nous devons faire correspondre cette imprévisibilité au mouvement aléatoire des atomes créé par la dissipation thermique du mouvement de la balle contre la surface de la courbe? Cette'

J'espère que cela pourra aider!

Je pense qu'un bon modèle pour cela est le jeu de la vie de Conway.

Depuis que nous avons inventé les règles, nous les connaissons parfaitement. Ceci est analogue à une théorie physique.

Pourtant, malgré la simplicité des règles et le fait que nous les connaissions, la vie est indécidable .

De même, même si nous avons appris toutes les lois de la physique, il se pourrait qu'elles soient également indécidables.

Il n'y a vraiment rien à y faire. Une chose à garder à l'esprit est que vous pouvez prédire le jeu de la vie de Conway pour un nombre fini d'étapes . Cela pourrait s'avérer être le même pour la physique.

L'existence de problèmes indécidables implique-t-elle immédiatement la non-prévisibilité des systèmes physiques?

Non.

nous construisons d'abord un UTM physique, disons en utilisant la construction basée sur un circuit habituel.

Une machine de Turing universelle est une machine de Turing. Une machine Turing a une bande infinie (ou extensible à l'infini). Par conséquent, vous ne pouvez pas en construire un à partir de circuits. Ce que vous pouvez construire est un automate borné linéaire (LBA).

Il ne peut alors y avoir aucune théorie physique décidable qui puisse déterminer, compte tenu de n'importe quel réglage d'entrée des circuits, si le circuit s'arrêtera.

Le problème d'arrêt est décidable pour un LBA, donc votre argument échoue.