Les lois physiques sont-elles toutes équivalentes à une machine de Turing?

[invite6c250b59]

Bonjour,

Posté pour éviter de détourner un fil ailleurs.

la thèse de Church-Turing s'applique-t-elle de façon universelle à n'importe quel système physique, ou juste à une partie d'entre eux ?

Non. En gros, s'il faut un in(dé)fini dans un calcul, ça va. S'il en faut plusieurs, c'est de l'hypercomputing: i.e. au delà des capacités d'une MT. Si les boucles temporelles sont physiquement possibles, il est àmha possible que ça rende l'univers non Turing-équivalent.
Plus intéressant, l'invariance de Lorentz en version quantique n'est probablement pas Turing équivalent. Cf ce message de David Berenstein sur le blog de Moshe


There are theorems about Lorentz invariant quantum mechanics: all such systems that are not trivial, must have infinite dimensional Hilbert space representations. This means that such a system can not be described by a finite number of q-bits.

(...)

As Moshe said: all experimental evidence is in favor of Lorentz invariance (even at the Planck scale).

If you seriously mix gravity with quantum mechanics, no one is sure what is the right answer is, but whatever it is, it should be compatible with what we observe. So if anyone believes that the Universe is strictly Lorentz invariant, one needs something more than an ordinary quantum computer with finite numbers of q-bits to simulate it.

If it is not, there’s some explaining to do as to why we have not seen violations of Lorentz invariance yet (spontaneous violation of Lorentz invariance due to matter effects still falls under the Lorentz invariant paradigm at high energies).(...)

[invite6c250b59]

euh..... tu parles de la nature profonde des lois physiques là? moi je te parlais de conditions sur les systèmes physiques usuels, et de leur description macroscopique, pas de la Realité Profonde avec des majuscules !

Un truc comme l'atmosphère terrestre par exemple, c'est équivalent à une machine de Turing? laquelle, et comment la définir? est ce que ça dépend pour toi de la brisure de l'invariance de Lorentz, de l'existence de boucles temporelles ou d'autres horreurs de ce genre?

1) à priori oui, comme tout système dont le comportement peut être décrit par des lois ne faisant pas appel à des multiinfini.
2) en cherchant les lois qui régisse le climat
3) très improbable àmha (mais non prouvé), à moins que le niveau de description macro nécessite absolument la description pico, i.e. que l'approximation qui est faite entre la description "plancher" et la description "plafond" ne soit pas assimilable à introduire du hasard.

[mh34]

Est-ce que quelqu'un aurait l'extrème obligeance de m'expliquer en termes simples ce qu'est une machine de Turing?
Ca fait 20 fois ( au moins!) que je relis la définition de Wiki sans arriver à la comprendre ( et )
Et comme ce concept m'a l'air central dans toutes vos discussions...

[invited9ab8c2f]

...Je suis avec toi dans cette quête...

je "surf" depuis tout à l'heure et ...je me noie!

voici ma "vague" du moment...

http://villemin.gerard.free.fr/Wwwgv...Aintro.htm#top

[A voir en vidéo sur Futura]

[mh34]

voici ma "vague" du moment

Humpfff...j'ai ouvert ta page...et j'ai fui lâchement!

..Je suis avec toi dans cette quête..

Que tous ceux qui ne comprennent pas plus que nous lèvent le doigt... ( on est déjà deux! )

[invite8915d466]

Une machine de Turing est en gros une machine fonctionnant en principe comme un ordinateur parfait, c'est à dire traitant de données numériques par des règles de calcul algorithmiques.

Les citations de Jiav sont écrites par des gens qui , dans l'ensemble, n'ont malheureusement rien compris aux problèmes posés par la Mécanique quantique.... c'est à dire qui confonde un modèle avec la réalité décrite , ce que justement la méca Q interdit de faire !

(leur argument étant, pour simplifier : ah ben puisqu'on a des lois physiques pour tout, et qu'on peut calculer ces lois avec autant de précision qu'on veut par un ordinateur, alors tout est équivalent à un ordinateur).

[mh34]

Merci beaucoup Gilles..
Excuse-moi, je crois que je vais abuser encore un peu...
En quoi un ordinateur ( celui dont je me sers par exemple et qui s'est éteint tout seul à l'instant, sale bête...) est-il différent d'une machine de Turing?


je précise ; je demande ça puisque tu as parlé d'ordinateur parfait, ce qui sous-entend que les ordinateurs usuels ne le sont pas...

[invite8915d466]

ben, il peut avoir des petits bugs, un cosmique qui fait "sauter" une case mémoire, une fluctuation de courant , etc;. qui fait que matériellement il peut s'écarter du fonctionnement idéal (quand il chauffe un peu trop par exemple - justement si il s'est éteint tout seul il a pas bien réagi comme une MT il n'aurait pas du faire ça . Mais en principe, il est équivalent à une machine de Turing parce qu'il existe des variables MESURABLES (les tensions et les champs magnétiques des mémoires) qui PAR CONSTRUCTION évoluent de manière déterministes, par un algorithme (qui est codé dans les circuits du processeur).

En revanche il n'y a rien de tel dans un cerveau, c'est à dire qu'il n'y a aucun ensemble fini de quantités MESURABLES (potentiel neuronaux, concentrations chimiques) qui évoluent de manière DETERMINISTE (c'est à dire dont on puisse dire donnez moi la liste (finie) de telles et telles variables et je peux vous prédire les valeurs de telles et telles après un temps T).

Ca n'existe simplement pas.

Et le truc de passer par des états quantiques à la base des particules du cerveau, comme j'explique sur l'autre fil, c'est idiot - à commencer par le fait qu'un état quantique n'est PAS mesurable complètement, à cause de limitations fondamentales de la méca Q.

[invite1fb4554e]

ben, il peut avoir des petits bugs, un cosmique qui fait "sauter" une case mémoire, une fluctuation de courant , etc;. qui fait que matériellement il peut s'écarter du fonctionnement idéal (quand il chauffe un peu trop par exemple - justement si il s'est éteint tout seul il a pas bien réagi comme une MT il n'aurait pas du faire ça .

Plus prosaïquement aussi, une machine de Turing a une mémoire infinie, contrairement aux ordinateurs !

Pour en revenir au sujet, le tout est de savoir si les lois physiques qui nous intéressent sont calculables (au sens de la théorie de la calculabilité) ou non. A savoir, peut-on coder les lois physiques sous forme d'algorithme (programme informatique) ?
Certains problèmes ne sont pas résolubles par un algorithme. L'exemple le plus célèbre étant le fameux problème de l'arrêt : à savoir, il est impossible d'écrire un programme qui, pour tout programme passé en entrée, écrira sur la sortie si oui ou non ce programme se termine bien ou boucle à l'infini.
Cependant, je n'ai pas de connaissances assez poussées en physique pour répondre à cette question !

[Philou67]

Est-il nécessaire de comparer une machine du Turing au cerveau pour répondre à la question initiale (ou bien même à la question de mh34) ?
Je ne le pense pas. Merci donc de rester concentré sur le sujet initial, et de ne pas ramener ici, des discussions traitées par ailleurs.
Philou67 pour la modération.

[invite8915d466]

parler de calculabilité des lois physiques est à mon avis un faux problème, puisque les lois physiques sont justement la manière dont nous décrivons la réalité de manière calculable, donc elles le sont forcément ! le vrai problème n'est pas là : il est plutot de savoir si les lois physiques que nous utilisons (et si nous utilisons , elles sont forcément calculables !) représentent VRAIMENT la réalité. Et là, il y a de bonnes raisons pour répondre : NON. Et donc que la réalité n'est , dans nos connaissances actuelles, pas descriptible par une MT.

Cdt

Gilles

[invité576543]

Et donc que la réalité n'est , dans nos connaissances actuelles, pas descriptible par une MT.

Et en particulier un ordinateur n'est, dans nos connaissances actuelles, pas descriptible par une MT.

Une fois présenté comme cela, la question est : que veulent dire exactement ceux qui décrivent un ordinateur par une MT?

Manifestement, ils n'emploient pas les mots "description", "descriptible", "décrire", dans le même sens que dans la phrase de Gilles.

Cordialement,

PS: A mon sens, la phrase de Gilles est tout aussi intéressante, profonde, élucidante et pédagogique que dire "Et donc que la réalité n'est , dans nos connaissances actuelles, pas descriptible par une machine thermique suivant le cycle Beau de Rochas." Eut-il utilisé cela, j'aurais demandé "que veulent dire exactement ceux qui décrivent un moteur à essence comme une ..."

[invite8915d466]

Et en particulier un ordinateur n'est, dans nos connaissances actuelles, pas descriptible par une MT.

pour moi, si, dans le sens où comme tu l'as dit, un ordinateur (au moins idéal) peut etre représenté (de manière incomplète, mais suffisante pour les applications qu'on en fait) par un ensemble de grandeurs dont l'évolution est exactement prédictible par un modèle de MT. Ce qui n'est pas vrai de la réalité physique en général.

Pour moi, il y a donc une condition restrictive aux objets dont le fonctionnement idéal peut etre équivalent à une MT, ce qui sert à définir cette classe : et cette classe, c'est justement ça qu'on appelle "un ordinateur". Il serait d'ailleurs paradoxal que tu parles de "un ordinateur" , en lui assignant des propriétés , sans jamais définir ce que tu appelles exactement "un ordinateur" !!! (question que j'avais posée dans un autre débat, on m'a répondu que c'etait inutile , trompeur, ou je sais plus quoi, alors que je pense toujours que c'est INDISPENSABLE de se mettre d'accord dessus).


Pour moi, un ordinateur est un objet matériel dont le fonctionnement correct est modélisable exactement, sans approximation, par une MT, ce qui suppose de le construire soigneusement pour ça (tout écart au fonctionnement MT étant considéré comme un bug). En fait la notion même d'ordinateur suppose justement que l'ordinateur "marche" INDEPENDAMMENT de la réalité physique sous-jacente : l'électronique marche quelle que soit la réalité quantique, les supercordes, ou la gravité à boucle. C'est donc exactement l'inverse de la discussion sur le cerveau, où on est obligé de faire des suppositions sur la réalité quantique pour le rendre équivalent à une MT. Ce qui est exactement l'inverse de la condition pour être appelé "un ordinateur" (ne pas dépendre de cette réalité ultime). Si on adopte cette définition d'ordinateur (qui colle exactement en pratique à celle employée dans la vie de tous les jours), c'est à dire, pour bien mettre les choses au point : "objet réel dont l'état peut etre décrit à un niveau fini par un nombre fini de variables physiques, évoluant idéalement de façon équivalente à une MT, indépendamment de la réalité physique ultime sous-jacente", alors le cerveau N'EST PAS un ordinateur. CQFD.

PS: A mon sens, la phrase de Gilles est tout aussi intéressante, profonde, élucidante et pédagogique que dire "Et donc que la réalité n'est , dans nos connaissances actuelles, pas descriptible par une machine thermique suivant le cycle Beau de Rochas." Eut-il utilisé cela, j'aurais demandé "que veulent dire exactement ceux qui décrivent un moteur à essence comme une ..."

je pense qu'il faut que tu adresses cette phrase à ceux qui défendent l'hypothèse computationnaliste tels que cités par Jiav.

Cdt

Gilles

[invité576543]

En quoi un ordinateur est-il différent d'une machine de Turing?

je précise ; je demande ça puisque tu as parlé d'ordinateur parfait, ce qui sous-entend que les ordinateurs usuels ne le sont pas...

Une machine de Turing est un modèle mathématique. Aucun objet physique n'est un modèle mathématique.

Confondre un ordinateur et une machine de Turing, c'est confondre un objet et un modèle.

Ce n'est pas (seulement) une question de perfection, mais aussi une question de "niveau de description". Modéliser un ordinateur comme une machine de Turing demande d'ignorer les détails de sa constitution physique, les atomes, les champs électriques, etc. et ne modéliser que le traitement de l'information.

En particulier le modèle de Turing est totalement discrétisé, en temps (changement d'états selon un "temps" discrétisé), en positions spatiales (cases mémoires, registres, etc.) et en valeurs (nombre fini de possibilités par "case" spatiale). Ce sont des simplifications extrêmes de la réalité d'une machine physique.

Le modèle simplifié marche pour certaines applications pratiques (FSPP ), comme la programmation des ordinateurs, parce que les ordinateurs sont conçus pour cela. Tout est fait pour "masquer" le substrat physique, pour en restreindre l'impact à quelque chose de modélisable comme une machine de Turing. Cela n'en fait pas une "machine de Turing", qui reste un modèle, mais cela l'en approche tellement que la confusion est courante et sans grand dommage, sauf dans les discussions "philosophiques" comme celle-ci.

Cordialement,

[invité576543]

Est-ce que quelqu'un aurait l'extrème obligeance de m'expliquer en termes simples ce qu'est une machine de Turing?

Je vais essayer autrement...

On peut partir de la notion de calcul symbolique. Un calcul symbolique porte sur des symboles (des lettres, des chiffres, des bits), dont le nombre de types est fini (26 lettres, 10 chiffres, 2 symboles binaires), mais dont on manipule de nombreuses instances, par exemple sous forme de chaînes de symboles (un mot est une chaîne de lettre, un nombre comme 13244 est représenté par une suite de chiffres.)

Quand on fait une addition sur papier, genre

  123
+ 456
-----
  579

on fait un calcul symbolique.

Turing a proposé un modèle générique de dispositif capable de faire des calculs symboliques, et il a été montré que tout dispositif capable de calcul symbolique était, dans sa fonction de calculateur symbolique, équivalent à une machine de Turing, au sens où on peut concevoir une machine de Turing faisant les mêmes calculs.

Une machine de Turing est devenue l'archétype de la notion de dispositif de calcul symbolique.

Tous les ordinateurs (numériques, les usuels) sont conçus pour faire des calculs symboliques, et sont équivalents, pour leur fonction de calcul symbolique, au modèle de Turing. (Mais il ne le sont pas pour ce qui est le réchauffement de la pièce où ils se trouvent, point non couvert par le modèle de Turing.)

De manière très simplifiée, le modèle de Turing demande

1) des cases "spatiales" (des endroits pour écrire des symboles) en pratique en nombre fini

2) un jeu discret de symboles, de valeurs que peuvent prendre les cases (deux valeurs, dans les ordinateurs "usuels")

4) au moins une "case" externe ("entrée") dont la valeur change par influence de l'extérieur

3) un dispositif qui change les valeurs des cases internes périodiquement (discrétisation du temps) en fonction des valeurs de toutes les cases (internes et entrée) et d'un "programme" qui dicte le calcul symbolique.

Pour un ordinateur usuel :

1) = mémoire vive, registres, disques dur, ...

2) = clavier, souris, réseau, ...

3) = CPU avec le programme

Cordialement,

[invité576543]

Turing a proposé un modèle générique de dispositif capable de faire des calculs symboliques, et il a été montré que tout dispositif capable de calcul symbolique était

correction : toute une classe de dispositifs capables de...

(Cela ne semble pas être le cas pour le "calcul quantique"...)

Cordialement,

[invited9ab8c2f]

Bonjour,

LA Machine de Turing ne peut pas exister, il n'y a que des machines utilisant un processus sur le modèle de cette machine? Cette question pour vérifier que j'ai bien compris!

De plus, sur un site dont j'ai donné un lien dessus, dans l'explication il est utilisé le mode binaire 0,1, pour la machine de Turing, c'était donc à titre d'exemple?

[invité576543]

LA Machine de Turing ne peut pas exister, il n'y a que des machines utilisant un processus sur le modèle de cette machine? Cette question pour vérifier que j'ai bien compris!

C'est à peu près ça. Comme le gaz parfait en physique : c'est un modèle, cela ne se trouve pas en pratique, mais c'est un bon modèle dans de nombreux cas.

De plus, sur un site dont j'ai donné un lien dessus, dans l'explication il est utilisé le mode binaire 0,1, pour la machine de Turing, c'était donc à titre d'exemple?

Le modèle de Turing est explicitement à symboles binaires, mais un modèle avec n'importe quel nombre (fini) de types de symboles serait strictement équivalent.

Cordialement,

[invited9ab8c2f]

...Et est ce que "l'histoire du battement d'aile du papillon qui déclenche un ouragan" peut elle être sur ce modèle?

[invité576543]

...Et est ce que "l'histoire du battement d'aile du papillon qui déclenche un ouragan" peut elle être sur ce modèle?

Sur quel modèle?

Une machine de Turing est un modèle de dispositif de calcul symbolique. Quel est le "dispositif" dont il serait question dans le cas d'un ouragan?

(Du coup, la machine thermique serait un meilleur choix )

Cordialement,

[invited9ab8c2f]

...Lorsque l'on comprend quelque chose on a l'impression de tout comprendre...pendant 1 minute, après on revient sur terre

J'imaginais que cet effet papillon pouvait se mettre sous forme symbolique: A donne B qui donne C et D qui....donc qui pouvait donner

Une machine de Turing est un modèle de dispositif de calcul symbolique

et je n'ai même pas lu "la machine thermique" car cela va faire trop d'un seul coup!

[invite6c250b59]

Est-ce que quelqu'un aurait l'extrème obligeance de m'expliquer en termes simples ce qu'est une machine de Turing?

C'est un modèle de calcul.

Est-ce que quelqu'un aurait l'extrème obligeance de m'expliquer en termes simples ce qu'est un modèle de calcul?

Un ensemble de ressources et des règles qui déterminent l'évolution de celles-ci.

Construisons un pour l'exemple, avec comme ressources
-deux nombres entiers M1 et M2
-un ruban de taille finie comportant une série de case, chacune comportant une de quatre instructions possibles (M1=M1+1; M1=M1-1; M2=M2+1; M2=M2-1)
-une tête de lecture positionnée sur une case du ruban

et comme règles
-Si M1 est positif, la tête de lecture se déplace de 1 vers la droite et exécute l'instruction qu'elle y trouve
-Si M1 est négatif, la tête de lecture se déplace de 1 vers la gauche et exécute l'instruction qu'elle y trouve
-Si M2 vaut 0, M1 revient à 0
-Si la tête de lecture arrive au bout du ruban, la machine s'arrête

Rien de sorcier là-dedans, et tu peux t'amuser à inventer de nouveaux modèles en prenant soin de spécifier la nature des ressources et les règles.

Ce que dit la thèse de Church-Turing, c'est que tous les modèles utilisant des ressources suffisamment raisonnables pour être construits physiquement sont équivalents à une machine de Turing (ou inférieur si on est balourd). Symétriquement, cela veut dire que tout système physique mesurable est simulable par une machine de Turing. C'est une thèse, c'est-à-dire que ce n'est pas prouvé.

Qu'est-ce qu'une ressource raisonnable? Il a été prouvé que le bruit, de même que l'analogique non parfait, de même que l'intrication dans les ordinateurs quantiques, n'améliorent en rien la calculabilité des MT (en revanche, ça peut augmenter leur vitesse -mais en fait les ordinateurs actuels sont aussi plus rapides que les MT pour des raisons un peu subtiles à expliquer, bref). C'était pas évident à la base (dans les années 30), mais c'est du solide (depuis lors).

Ce qui m'amène à faire une parenthèse sur une confusion de Gilles et possiblement de Michel (ça varie selon les posts). La thèse de Church (et donc la question du fil que vous pouvez lire en haut de chaque message) n'est pas que tout phénomène physique se décrit physiquement comme une machine de Turing avec un ensemble de symbole et un ruban de papier. Même si vous prouviez que tel ou tel système ne peut se décrire que comme de l'analogique bruité, ou avec des intrications, cela ne changerait rien à sa calculabilité (ce qui est l'objet de la thèse CT).

Exemple de ressources déraisonnables: l'analogique parfait avec une précision infini, un oracle résolvant le problème de l'arrêt, une quantité infini de symboles, un ruban mémoire infini. Si on précise que le problème de l'arrêt est calculable par une MT disposant d'une ressource infini, tu vois que les seuls exemples (que je connais) sont en réalité tous basés sur un infini quelque part.

C'est la où l'intervention de David Berenstein est très intéressante: il indique que 1) l'invariance de Lorentz est très solide expérimentalement 2) il y a des démonstrations que cette propriété ne peut être obtenue qu'avec un nombre de qbits infini. Qui dit infini dit probablement pas Turing équivalent.

Alors la question finale, qu'est-ce que ça impliquerait si DB a raison? Ce serait... fantastique. Cela voudrait dire que on peut utiliser l'univers physique pour faire des calculs impossibles à une MT, c'est-à-dire faire de l'hypercalcul.

euh et pourquoi c'est fantastique?

Pour donner une idée: tous les problèmes mathématiques listés ici peuvent se mettre sous la forme d'un programme dont l'arrêt décide si le problème est vrai, faux, ou indécidable. Or l'hypercalcul permettrait de décider si un programme s'arrête. On pourrait alors demander à un hyperordinateur des trucs comme "P=NP?". A côté de ça, les progrès attendus par l'ordinateur quantique c'est de l'excrément de charançon.

Bed time, bon we

[mh34]

On pourrait alors demander à un hyperordinateur des trucs comme "P=NP?".

Ca fait partie des problèmes listés par l'institut Clay, je suppose...

Est-ce que Perelman n'en a pas résolu un récemment, de problème? Ce qui signifierait que le modèle de fonctionnement de son cerveau n'est pas équivalent d'un modèle à états finis, non?

Là je sens que je vais peut-être faire un hors sujet, mais...comment ma réponse à ta question dans le fil sur les robots humains t'a-t-elle conduit à évoquer la thèse de Church Turing??
Tu as manifestement fait un raccourci que je n'ai pas saisi...

[invite8915d466]

Ce qui m'amène à faire une parenthèse sur une confusion de Gilles et possiblement de Michel (ça varie selon les posts). La thèse de Church (et donc la question du fil que vous pouvez lire en haut de chaque message) n'est pas que tout phénomène physique se décrit physiquement comme une machine de Turing avec un ensemble de symbole et un ruban de papier. Même si vous prouviez que tel ou tel système ne peut se décrire que comme de l'analogique bruité, ou avec des intrications, cela ne changerait rien à sa calculabilité (ce qui est l'objet de la thèse CT).

comme j'ai dit, je pense que ces réflexions ignorent le fond du problème posé par la Méca Q : elles font comme si il y avait identité entre les variables mesurables et les variables d'état du système, c'est à dire comme si les variables dont on pouvait calculer l'évolution étaient les mêmes que celles qu'on pouvait mesurer physiquement. C'est vrai en méca classique, c'est faux en méca Q. Les observables (quantités physiquement mesurables) n'obeissent pas à des lois déterministes , et les variables décrivant l'état, qui obeissent à des équations déterministes, ne sont pas en elles mêmes mesurables (les valeurs des champs quantiques).

par ailleurs, la conclusion que la possibilité réelle de fabriquer un robot pensant, ou même un ordinateur quantique, dépende de la nature profonde de la réalité et de la violation ou non de l'invariance de Lorentz est manifestement absurde. Il est bien évident que l'électronique marche indépendamment de l'interprétation profonde de la Meca Q.

Cdt

Gilles