Existe-t-il un lien entre le problème d'arrêt et l'entropie thermodynamique?

31

Alan Turing a proposé un modèle pour une machine (la Turing Machine, TM) qui calcule (nombres, fonctions, etc.) et a démontré le théorème de Halting .

Une MT est un concept abstrait d'une machine (ou d'un moteur si vous le souhaitez). Le théorème de l'arrêt est un résultat impossible. Un moteur Carnot (CE) est un concept abstrait de moteur thermique et Carnot a prouvé le théorème de Carnot , un autre résultat d'impossibilité lié à l'entropie thermodynamique.

Étant donné qu'une MT est physiquement réalisable (au moins autant qu'une CE, ou peut-être pas?), Existe-t-il une cartographie ou une représentation ou "isomorphisme" de la MT ou CE qui pourrait permettre d'unifier ces résultats et en plus de se connecter à l'entropie?

Il existe bien sûr des formulations de TM et du théorème de Halting en termes de théorie algorithmique de l'information (par exemple Chaitin, Kolmogorov etc.) et d'entropie (dans ce contexte). La question demande le concept plus physique d'entropie (si dans le processus d'une réponse potentielle l'entropie algorithmique se pose, c'est bien, mais ce n'est pas ce que la question demande exactement).

On peut aussi vérifier une autre question dans physics.se qui relie l'incertitude quantique à la 2ème loi de la thermodynamique. Voir aussi: une caractérisation algébrique de l'entropie , une caractérisation algorithmique de l'entropie , une revue et des connexions entre les différentes formulations de l'entropie

Nikos M.
la source
1
il y a un sens dans lequel les concepts définis sont exactement opposés . les lois théormodynamiques sur l'augmentation de l'entropie excluent une machine à mouvement perpétuel . une machine non asphalteuse est une machine à mouvement perpétuel .
vzn
ouais je vois, redéfinir la condition sans arrêt comme un mobile perpétuel (du 2ème type?), c'est exactement dans l'esprit de la question, mais est-ce ce que dit le théorème de l'arrêt? Il déclare que nous ne savons pas s'il s'arrête ou non, en raison de la "circularité", gentil
Nikos M.
Une proposition pour ajouter "thermodynamique" et / ou "thermodynamique-calcul" comme nouvelles balises dans CS.se? je ne sais pas si je peux le faire par moi-même (probablement), mais laisse entendre d'autres opinions
Nikos M.

Réponses:

11

Je ne suis pas du tout un expert dans ce domaine, mais je pense que vous serez intéressé par l' informatique réversible . Cela implique, entre autres, l'étude de la relation entre les processus physiquement réversibles et les processus logiquement réversibles. Je pense qu'il serait juste de dire que les "fondateurs" du domaine étaient / sont Ralph Landauer et Charles H Bennett (tous deux de la recherche IBM, je pense.)

Il touche à l'informatique quantique et à la théorie de l'information quantique, mais examine également des questions telles que "quelles sont les limites du calcul en termes de temps, d'espace et d'énergie?" On sait, (si je me souviens bien) que vous pouvez rendre l' énergie nécessaire pour effectuer un calcul réversible arbitrairement petite en lui faisant prendre un temps arbitrairement long. C'est-à-dire que l'énergie temps (= action ) nécessaire pour effectuer un calcul réversible peut devenir une constante. Ce n'est pas le cas pour les calculs non réversibles.×

Beaucoup de personnes qui étudient dans ce domaine travaillent également sur l'informatique quantique et la physique numérique (l'idée que l'univers est un grand automate cellulaire quantique). Les noms des chercheurs qui me viennent à l'esprit sont Ed Fredkin , Tommaso Toffoli et Norm Margolus .

Ces questions sont absolument sur le thème de l'informatique. Pas seulement pour la théorie (qui comprend les mathématiques cool ainsi que la physique cool) mais pour les ingénieurs qui veulent connaître les limites ultimes du calcul. Existe-t-il un volume ou une énergie minimum requis pour stocker un peu d'informations? L' action requise pour effectuer un calcul réversible peut être constante, mais y a-t-il des limites sur ce qu'est cette constante? Ce sont des connaissances essentielles pour les ingénieurs qui tentent de repousser les limites du possible.

Logique errante
la source
Oui, il y a une relation avec la thermodynamique du calcul (Bennett, Landauer et al.), Mais en demandant plus en relation avec le théorème de Halting, et / ou la cartographie entre TM et CE (comme en question), mais belle réponse
Nikos M.
1
Ah, tu as raison. Je sous-vote ma réponse. Les commentaires sous votre question disant que c'était hors sujet m'ont fait voir rouge, et je répondais principalement à cela. En réponse à votre vraie question: regardez la thèse de Church-Turing. En supposant que vous croyiez cela et que les mathématiques peuvent modéliser n'importe quoi dans la nature, le problème de l'arrêt est un théorème d'impossibilité physique.
Wandering Logic
Je pense que la thèse Church-Turing que le calcul physique est efficace de calcul peut être nécessaire en effet, jetez un oeil à cet article aussi
Nikos M.
5

Je ne connais pas le théorème de Carnot, sauf ce que je viens de lire sur Wikipedia, mais même à partir de cette introduction superficielle, il y a un lien dans la structure des preuves, et cela peut vous intéresser, car c'est une technique de preuve qui est applicable dans de nombreux domaines.

Ce sont deux preuves par contradiction pour montrer qu'aucune chose dans une classe donnée n'a de propriété, vous supposez qu'une instance a effectivement cette propriété, puis montrez qu'une contradiction s'ensuit.

Le problème de l'arrêt est intéressant en ce que la contradiction provient d'une certaine auto-interaction concernant l'instance particulière (qui est une machine M qui peut déterminer si une machine arbitraire s'arrêtera avec une entrée donnée). En particulier, vous construisez une nouvelle machine qui inclut M en tant que composant, puis alimentez la nouvelle machine en M.

Quelqu'un avec plus de connaissances sur le théorème de Carnot pourrait en parler (ce que je ne suis pas qualifié pour faire), mais il semble que la contradiction provient du type de moteur thermique que vous pourriez construire si vous aviez une instance avec la propriété à portée de main.

Les deux cas impliquent donc la construction de:

  • Supposons que certains X aient la propriété P.
    • À partir de X, créez le Y associé.
    • Les relations entre X et Y sont contradictoires.
  • Par conséquent, aucun X n'a ​​la propriété P.

Il semble cependant y avoir une différence dans la mesure où la contradiction dans le cas du théorème de Halting est une pure contradiction logique et serait contradictoire dans n'importe quel contexte de la logique classique. Le théorème de Carnot, si je comprends bien, n'est que contradictoire par rapport à la deuxième loi de la thermodynamique. D'un point de vue logique, c'est un axiome, donc si vous preniez une axiomatisation différente dans laquelle la deuxième loi de la thermodynamique ne tenait pas, le théorème de Carnot ne serait pas un théorème, car la contradiction n'existerait pas. (À quoi ressemblerait une formalisation de la thermodynamique sans la seconde loi, c'est le genre de question qui a conduit les géomètres à une géométrie non euclidienne.)

Joshua Taylor
la source
ce document fournit beaucoup dans la direction que vous mentionnez, imo. De plus, ce que je pense être très pertinent, c'est la circularité (ou la diagonalisation) des arguments. Il existe des directions de recherche qui relient les transformations logiques irréversibles aux processus thermodynamiques irréversibles (par exemple le principe de Landauers et ses objections). Il y a des objections à certaines déclarations de la 2ème loi mais on peut trouver des formulations qui tiennent toujours (par exemple le travail de Prigogine)
Nikos M.
Pour savoir comment cette connexion pourrait se produire, voir également les commentaires sur la réponse précédente (uniquement à des fins de plausibilité)
Nikos M.
En ce qui concerne les autres formulations de la 2ème loi (encore plus générales et pour les processus hors équilibre), vous pouvez vérifier la déclaration de Caratheodory en termes d'espace de phase et de géométrie, les travaux de Prigogin sur les systèmes hors équilibre et la formulation Hatzopoulos-Gyftopoulos-Beretta (avec d'autres liens avec mécanique quantique)
Nikos M.
Dans un sens , il tant de facettes de l' entropie comme il y a des facettes du théorème de Gödel (s) (comme dans le théorème arrêt de Turing, le théorème de indéfinissable de Tarski , le théorème de Rosser , le théorème d'incomplétude de Chaitin ), il y a même une preuve de catégorie théorique d'un « général Goedel Theorem "englobant tous les précédents qui est basé sur des points fixes
Nikos M.
Même si un lien entre le problème d'arrêt et l'entropie thermodynamique est réalisé sous la forme de si et quand la loi 2md tient alors ... , c'est toujours aussi bon que cette question va (liée à l'objection que la 2ème loi pourrait être comme la 5ème postulat sur les parallèles en géométrie euclidienne)
Nikos M.
4

IANAPhysicist mais je ne vois aucune connexion. Les machines de Turing sont des objets de mathématiques pures et l'indécidabilité du problème d'arrêt est indépendante de toute réalisation physique de quoi que ce soit.

David Richerby
la source
Les résultats de l'impossibilité de la 2e loi ont beaucoup en commun avec les problèmes de logique (mathématique) et les circularités, peut-être un lien là-bas?
Nikos M.
1
Il faudrait donner plus de détails: comme je l'ai dit, je ne suis pas physicien. Mais je ne vois pas comment les lois physiques peuvent avoir un impact sur une construction qui existe indépendamment de la réalité physique.
David Richerby
vous avez un point là-bas, je peux donner de nombreuses raisons épistémologiques pour lesquelles cela est très plausible (par exemple, les mathématiques que nous dépendons du monde que nous vivons , a-la Einstein), mais je veux qch au-delà, si j'avais une réponse prête i publierait probablement un article :)
Nikos M.
2
@vzn Nous utilisons le mot «temps» pour le nombre d'étapes que la machine a exécutées et «espace» pour le nombre de cellules de bande qu'elle a utilisées, mais ces mots ont été choisis pour faire appel à notre intuition physique en tant qu'êtres physiques. Mais le «temps» n'est qu'un index dans une séquence de configations et l'espace n'est qu'un index dans une séquence de symboles. Par exemple, considérons une machine Turing où la tête siffle juste vers la droite. Il utilise un «temps» et un «espace» infinis, mais vous pouvez comprendre cela dans une quantité finie de temps réel et d'espace réel
David Richerby
2
Bien sûr, mais le fait que nous considérions les machines de Turing comme des objets intéressants peut avoir quelque chose à voir avec la physique.
Gilles 'SO- arrête d'être méchant'
1

Cette question plurielle à sujets multiples n'a pas de réponse simple / facile et touche à des domaines actifs de la recherche TCS. cependant c'est une question rare demandant un lien entre physique et TCS qui m'a intéressé au fil des ans. il y a plusieurs directions différentes à suivre. la réponse de base est que c'est une "question ouverte" mais avec des recherches actives / modernes qui y touchent et font allusion aux connexions.

  • il y a quelques problèmes indécidables surprenants / profonds de la physique avancée. par exemple à partir de systèmes dynamiques. cependant, ils n'ont pas vu cela connecté à l'entropie en soi, mais l'entropie est associée à tous les systèmes physiques (par exemple, on peut le voir dans la théorie de la chimie), donc il doit au moins y avoir un lien indirect.

  • l'entropie apparaît en effet dans CS mais plus sous la forme de théorie de l'information et de théorie du codage. la naissance de la théorie du codage a impliqué la définition / analyse de l'entropie associée aux codes de communication par Shannon. essayez cette excellente référence en ligne Entropie et théorie de l'information par Gray

  • l'entropie est également associée parfois associée à la mesure de l'aléatoire dans les PRNG. il existe un lien entre les séparations de classes de complexité (par exemple P =? NP) et les PRNG dans le célèbre article "Natural Proofs" de Razborov / Rudich. il y a des recherches continues sur ce sujet.

  • vous mentionnez la thermodynamique et sa connexion au TCS. il existe un lien profond entre l'aimantation dans les verres de spin en physique et les problèmes NP complets étudiés au point de transition SAT. là (encore) le système physique a une entropie associée mais il a probablement été étudié plus dans un contexte physique que dans un contexte TCS.

vzn
la source
peut développer certains de ces éléments en détail dans Computer Science Chat
vzn
voir aussi CS defn of entropy stackoverflow
vzn
il est intéressant de pouvoir penser "hors des sentiers battus" (au moins parfois), avez-vous regardé les travaux de Bennet sur la thermodynamique du calcul? La motivation derrière la question est de montrer si le théorème d'arrêt peut être vu comme une conséquence de la thermodynamique (avec un modèle ou une représentation appropriée au moins pour certains cas). je pense que ce serait vraiment intéressant si cela pouvait être réglé de toute façon
Nikos M.
vous avez peut-être déjà vu ces articles, philsci-archive.pitt.edu/313/1/engtot.pdf et cc.gatech.edu/computing/nano/documents/…
Nikos M.
La plupart des concepts d '"entropie" utilisés en informatique se rapportent soit à la théorie de l'information de Shannon, soit à la théorie algorithmique de l'information de Kolmogorov / Chaitin / Solomonov, ceci est déjà mentionné dans la question et il est très important. La seule connexion à l'entropie thermodynamique que je connaisse (qui peut être liée à l'entropie inf.) Est la thermodynamique du calcul. La question est liée à la thermodynamique du calcul mais d'une autre manière
Nikos M.
1

Il existe un problème de pensée simple qui est parfois utilisé comme introduction aux paradigmes informatiques non conventionnels:

Vous avez deux ampoules et leurs interrupteurs marche-arrêt respectifs. Quelqu'un ouvre et ferme les deux lumières l'une après l'autre. Comment déterminez-vous lequel a été fermé en premier et lequel a été fermé en dernier? Déterminez le nombre minimal de fois que vous devrez ouvrir les lumières pour résoudre ce problème.

La plupart des informaticiens essaient généralement de trouver une solution basée sur la logique booléenne. La réponse est (au moins l'une d'entre elles): en touchant les ampoules et en voyant laquelle est plus chaude.

Les paradigmes basés sur la chaleur existent en informatique: le recuit simulé est un algorithme connu (l'ordinateur quantique à ondes D est l'équivalent quantique de l'algorithme).

Y a-t-il maintenant une relation avec le problème de l'arrêt?

Le travail classique de Chaitin et Calude sur le problème Halting via le concept des nombres Omega peut être lié à la formulation probabiliste du problème Halting. C'est le traité le plus récent sur le problème auquel je peux penser ... et pas de relation claire avec l'entropie (thermodynamique). Maintenant, si l'entropie de l'information (au sens de Shannon) vous convient, le nombre Omega code de la manière la plus succincte le problème de l'arrêt, au sens d'une liaison de Shannon.

En bref, un nombre Omega est la probabilité qu'un programme aléatoire s'arrête. La connaissance de la constante permettrait l'énumération de toutes les déclarations mathématiques valides (vérités, axiomes, etc.) et n'est pas calculable. Calude a calculé une version d'Omega en changeant la mesure de probabilité uniforme par une mesure inversement proportionnelle à la longueur d'un programme aléatoire et en utilisant des encodages sans préfixe. On pourrait donc parler d'Omega de Chaitin et d'Oméga de Calude.

user13675
la source
Belle réponse, la partie liée à la chaleur des ampoules est utilisée à plusieurs reprises comme lien entre l'entropie de l'information et l'entropie thermodynamique (est un sens contraire à la vision de Jaynes comme incertitude subjective). ma propre pensée serait de baser le raisonnement sur la circularité des deux constructions et par une cascade (intelligente?) l'une avec l'autre créer une implication (au moins dans un sens)
Nikos M.
Un raisonnement similaire est utilisé avec les piles (au lieu des ampoules) pour déterminer quelles piles sont déchargées ...
Nikos M.
0

Oui !, assez étrangement j'y ai pensé .. Voici l'idée:

Premier pas

Modélisez le démon de Maxwell comme un programme informatique. Ensuite, comment le démon a-t-il connu la vitesse et la position des particules avant d'ouvrir la porte pour la sélection?

Supposons que le démon ne puisse pas mesurer la vitesse à laquelle les particules frappent la porte, pourquoi? parce que cela changerait la vitesse des particules, donc le démon doit comprendre avant de l' ouvrir, sans regarder, sans mesurer. Pour être juste, nous informerons le démon des règles du jeu à l'avance, c'est-à-dire nourrir le démon avec les lois du mouvement, les interactions des particules et les conditions initiales, assez du modèle physique / dynamique.

Deuxième étape

Modélisez maintenant le gaz des particules également comme un programme informatique qui exécute le même code donné au démon pour chaque particule, de sorte que le gaz calcule un résultat à partir de ses conditions initiales, le démon ne sait pas ce résultat jusqu'à ce qu'il s'arrête (si jamais ): à savoir "une particule avec la bonne vitesse est à la porte", la décision oui / non que nous posons au système est "Avoir une particule à la bonne position et suffisamment de vitesse?", si oui, la porte pourrait être ouverte et la particule rapide peut entrer dans le côté haute température de la pièce en définissant de nouvelles conditions initiales (ces problèmes consécutifs auront-ils une réponse? ou se poursuivront-ils pour toujours?)

Il y aura un moment où il n'y aura pas de particule avec une vitesse suffisante pour traverser la frontière, donc, il y aura un moment où le code s'exécutera pour toujours (ne vous arrêtez pas) pour presque n'importe quel seuil donné.

Le démon veut connaître le résultat calculé par le gaz, mais le résultat est en quelque sorte potentiellement impliqué dans le code source des lois des particules plus les conditions initiales .. bien sûr, nous devons exécuter ce programme pour le savoir. Si Demon exécute le même programme en attendant la bonne vitesse à la sortie, le programme pourrait s'arrêter ou il pourrait fonctionner indéfiniment (mais nous supposons également que le démon n'a pas plus de puissance de calcul que le gaz, il ne pourra donc pas décider de la ouverture des portes à temps).

Le démon pourrait essayer de comprendre la sortie du programme (ou s'il s'arrêtera) en regardant la source et les entrées sans l'exécuter, mais c'est comme essayer de résoudre le problème d'arrêt, pourquoi? parce que Demon ne sait pas quelles lois et conditions initiales seront alimentées , Démon devrait être prêt à résoudre tout ensemble de lois et conditions initiales, et nous savons que ce n'est pas possible en général, il aura besoin d'un oracle, s'il le peut, il le fera être suffisant pour construire un démon pour générer de l'énergie à partir de rien. (même en connaissant les lois et la condition initiale, les deux choses sont déjà assez difficiles à savoir)

Cette expérience de pensée peut relier comment une réduction de l'entropie, au moyen d'ordinateurs, pourrait en quelque sorte délimitée par Halting Problem , comme un problème pour anticiper en général les résultats.

(Parfois, toutes les limites semblent être la même limite ..)

En savoir plus sur les lois des particules

Les lois des particules ne sont pas le principal problème de cette expérience de pensée, ces lois pourraient être quantiques ou classiques, mais nous devons tenir compte du fait de la complexité des lois et des conditions initiales, la complexité de l'arrangement des particules n'est pas limitée, et cela pourrait ont beaucoup de complexité supplémentaire (dans un exemple extrême de conditions initiales, vous pouvez même insérer un ordinateur entier tirant des particules selon un code source interne et donner ce code au démon).

Hernan_eche
la source
1
Je ne comprends pas le lien avec le problème d'arrêt. Tout d'abord, vous semblez avoir redéfini ce que signifie l'arrêt d'une machine. Deuxièmement, vous ne semblez avoir qu'un seul programme (le simulateur de particules de gaz). Il est parfaitement possible de prouver qu'un programme fixe s'arrête ou ne s'arrête pas, sans violer l'indécidabilité du problème d'arrêt général .
David Richerby
À propos de l'arrêt, il n'a pas redéfini l'arrêt, ici l'arrêt du programme est, comme toujours, lorsque le programme termine le calcul et que vous obtenez une sortie, alors ici la sortie est définie comme le moment exact où une particule avec la bonne vitesse a frappé la porte , et vous pourriez construire une porte qui le détectera, donc il marquera lorsque le programme s'arrêtera (puis le programme s'exécutera à nouveau à partir de ces conditions initiales pour une autre sortie). Daemon veut savoir quand il s'arrêtera, mais il ne peut pas savoir même s'il s'arrêtera.
Hernan_eche
1
Les machines Turing ne peuvent pas décider du problème d'arrêt des machines Turing. Il semble que vous ayez redéfini le problème d'arrêt comme "Est-ce que l'une de ces molécules de gaz fait X?", Ce qui est un problème complètement différent de "Est-ce que cette machine de Turing s'arrête lorsqu'elle est démarrée avec cette entrée?" La preuve de Turing de l'indécidabilité du problème d'arrêt de la machine de Turing ne dit pas si une machine de Turing pourrait calculer si une molécule de gaz fera jamais X.
David Richerby
Le commentaire de David est correct, tel quel, il n'est pas directement lié au problème de l'arrêt. Cependant c'est un argument qui suit l'esprit de la question
Nikos M.
1
@Gilles, merci de noter que je suis d'accord avec lui, si nécessaire un chat sera créé. je préférerais que ces commentaires soient néanmoins laissés car ils se rapportent à la fois à la question et à la réponse spécifique (telle qu'évoluée)
Nikos M.
-1

Question très captivante en effet, et nous verrons que votre pensée EST correcte .

Voyons d'abord ce que dit le deuxième principe de la thermodynamique.

La fonction d'entropie est utilisée dans la 2ème loi de la thermodynamique. Il découle du théorème de Carnot selon lequel les processus se déroulant dans les machines à vapeur ont un rendement inférieur ou au mieux égal à la machine "réversible" correspondante (qui semble d'ailleurs être un concept instable au cours des 150 ans de thermodynamique). Carnot n'a pas inventé lui-même la fonction d'entropie, mais avec Clausius, voici ce qu'ils disent:

Comme il n'y a pas de machine perpétuelle, alors nous pouvons construire une fonction S appelée entropie qui contraint les mesures thermodynamiques macroscopiques dans une certaine équation, à savoir que S (V, T, P, etc.) = 0

Notez que cette équation n'est rien d'autre que l'équation d'une hyper-surface dans l'espace des mesures thermodynamiques.

Entre dans Carathéodory.

Carathéodory est un mathématicien allemand et, comme tous les mathématiciens, il veut extraire du raisonnement de Carnot et de Clausius quelques axiomes qui lui permettraient de clarifier en quoi consiste réellement la seconde loi . Autrement dit, il veut purifier la thermodynamique pour savoir exactement ce qu'est l'entropie.

Après avoir énuméré un certain nombre d'axiomes, il parvient à formuler SA deuxième loi, qui dit (plus ou moins):

Il existe des processus adiabatiques. Ou plus prosaïquement, si vous voulez revenir, parfois travailler seul ne suffit pas. Vous avez besoin d'un peu de chaleur.

Maintenant, cela semble TRÈS différent de la formulation de Clausius! Mais en fait ce n'est pas le cas. Carathéodory n'a fait que changer l'ordre des mots, un peu comme les mathématiciens ont joué avec le 5ème axiome d'Euclide pendant 2000 ans et ont produit de nombreux mots différents pour cet axiome. Et si vous reculez, vous ne devriez pas être trop surpris par la déclaration de Carathéodory sur la deuxième loi. En fait, Carathéodory conduit à exactement la même fonction d'entropie et l'équation hyper-surface S (V, T, P, etc.) = 0

Réfléchissez bien au théorème de Carnot. En tant que mathématicien, vous ne devriez pas être trop satisfait de la façon dont Carnot admet que les machines perpétuum n'existent pas. En fait, en tant que mathématicien, vous préféreriez voir quelque chose comme ceci:

Il existe une fonction entropique S qui contraint les mesures macroscopiques SI ET SEULEMENT SI il n'y a pas de machines perpétuelles ".

MAINTENANT, vous avez un théorème. Et que dit-il? Que tant qu'il n'y a pas de système mécanique isolé qui produit une quantité infinie d'énergie et pourrait donc vous conduire à n'importe quel état que vous souhaitez, alors vous trouverez une fonction d'entropie. Un système mécanique isolé est un processus adiabatique. D'où la formulation de Carathéodory: aucun système adiabatique ne peut vous conduire nulle part. Parfois, vous aurez besoin de chaleur.

Donc non seulement nous sommes sûrs que Carathéodory est correct, mais aussi que sa formulation est assez simple.

Maintenant, où avez-vous l'impression que la deuxième loi à la Carathéodory ressemble au problème de l'arrêt?

Prenez du recul sur la déclaration de Carathéodory. Tout ce qu'il dit, c'est qu'une fois que vous avez un système mécanique isolé avec lequel vous arrêtez de vous mêler, vous ne pouvez pas atteindre l'état que vous voulez.

Cela ne sonne-t-il PAS PRÉCISÉMENT comme le problème d'arrêt? C'est-à-dire qu'une fois que vous aurez écrit tous les axiomes de votre théorie et établi toutes les transitions possibles, il y aura des problèmes que vous ne pourrez pas résoudre. Parfois, vous devrez ajouter plus d'axiomes.

En fait, si vous voulez aller vraiment en profondeur et coder la formulation de Carathéodory, cela se traduira par le même code que le problème d'arrêt des processus adiabatiques au lieu des machines de Turing et des états au lieu de problèmes.

Qu'est-ce que tu penses?

REMARQUE: j'ai modifié ma réponse presque entièrement afin que les commentaires ci-dessous ne correspondent pas à ce qu'elle contient maintenant.

Jérôme
la source
1
"Rice déclare qu'aucune machine de Turing ne peut indéfiniment produire une propriété non triviale." Ce n'est pas une paraphrase de Rice que je reconnais. Que voulez-vous dire?
David Richerby
1
Qu'entendez-vous par «produire à l'infini une propriété non triviale»?
David Richerby
Un peu tordu. Rice dit qu'il ne peut pas être prouvé qu'une MT implémente une fonction donnée. Maintenant, si un TM A produit indéfiniment une propriété non triviale (N-TP), cela signifie qu'il produit un N-TP pour N'IMPORTE QUELLE entrée. Comment cela peut-il être vrai dans la pratique? Eh bien, il semble que le seul moyen pour que cela soit vrai est de considérer une entrée e non définie et de montrer que son A (e) a un N-TP. À son tour, cela signifierait que nous parviendrions à prouver que la machine produit un N-TP. Et nous savons que ce n'est pas possible. Donc en fait je postule qu'il est équivalent de dire "A produit indéfiniment un N-TP" et "JE PEUX MONTRER que A produit un N-TP"
Jerome
"Produire à l'infini une propriété non triviale" signifie que vous pouvez lancer un nombre infini d'entrées distinctes dans la MT. Et toutes les sorties auront le NT-P
Jerome
1
D'ACCORD. Je pense que votre réponse serait beaucoup plus claire si vous utilisiez simplement des termes standard, au lieu d'inventer des choses comme «produire à l'infini une propriété non triviale» pour signifier «pouvoir traiter un nombre infini d'entrées». Il serait également utile d'expliquer quel aspect de votre "vraie" machine Turing est incapable de traiter un nombre infini d'entrées. Est-ce que la bande est finie, par exemple?
David Richerby