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

[invite73192618]

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).(...)

-----

[invite73192618]

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! )

[GillesH38a]

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...

[GillesH38a]

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.

[Gunman]

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.

[GillesH38a]

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]

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,

[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 ..."

[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!

[GillesH38a]

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]

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.

Tu ergotes.

Toute la physique consiste au contraire à "représenter de manière incomplète mais suffisante pour les applications qu'on en fait" la réalité.

Le côté "exactement prédictible" n'est pas pertinent à mon avis. En l'ajoutant tu escamotes le point principal, qui est qu'une "description" est toujours une "représentation incomplète mais suffisantes pour les applications qu'on en fait".

Qu'il y ait des modèles déterministes et d'autres non n'a pas grand chose à voir dans l'histoire. (Et dans mon métier, les modèles des machines sont non déterministes, parce que si on avait oublié les erreurs aléatoires, ton portable ne marcherait pas.)

Cordialement,

[invité576543]

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

A tout le monde.

Jiav représente de travers l'hypothèse computationnaliste, mais c'est aussi la représentation que tu présentes, non?

Cdlt,

[GillesH38a]

Qu'il y ait des modèles déterministes et d'autres non n'a pas grand chose à voir dans l'histoire. (Et dans mon métier, les modèles des machines sont non déterministes, parce que si on avait oublié les erreurs aléatoires, ton portable ne marcherait pas.)

Cordialement,

comme les CD sont redondants pour corriger des erreurs toujours possibles; ça n'empeche pas des CD d'etre fondamentalement des objets codant de l'information numérique. Tes modèles de machine restent néanmoins numériques justement par le fait que tu considères que les écarts au fonctionnement numériques sont des "erreurs" qu'il convient de corriger, mais le PRINCIPE de fonctionnement reste digital- ce qui n'est pas le cas du cerveau, meme "en principe". Un cerveau "parfait" , à supposer qu'on sache définir ce que c'est, ne serait pas plus "numérique" qu'un cerveau bruité.

Cdt

Gilles

[GillesH38a]

A tout le monde.

Jiav représente de travers l'hypothèse computationnaliste, mais c'est aussi la représentation que tu présentes, non?

Cdlt,

je n'ai jamais dit et jamais pensé que Jiav présentait de travers l'hypothèse computationnaliste, ce qu'il dit correspond à ce que j'en ai lu par ailleurs. Je considère juste que cette hypothèse n'est pas fondée, c'est tout.

[GillesH38a]

Un cerveau "parfait" , à supposer qu'on sache définir ce que c'est, ne serait pas plus "numérique" qu'un cerveau bruité.

Cdt

Gilles

pour préciser : si tu défends l'idée que les objets numériques réels (les vrais téléphones portables, lecteurs CD, etc...) deviennent trop complexes pour etre assimilés à une MT , ça ne me gêne absolument pas. Ca veut dire, comme le cerveau, que leur fonctionnement effectif dépend d'autre chose que de l'algorithme numérique, mais aussi de la façon dont ils sont construits, de l'épaisseur de cuivre dans les contacts, de la protection électromagnétique, etc.... Dans ce cas, tout comme le cerveau, ils deviennent "non remplaçables" par un algorithme équivalent fonctionnant sur une plateforme matériellement différente (par exemple on ne peut simplement pas construire un réseau de téléphonie mobile avec du bois et de la ficelle- ni d'ailleurs avec des protéines et de l'ADN). Des qu'on sort du cadre "MT strict", on n'a plus rien qui autorise à penser que deux structures matériellement très différentes "puissent faire la meme chose". Je ne dis rien de plus pour le cerveau.

Cdt

Gilles

[invité576543]

je n'ai jamais dit et jamais pensé que Jiav

Toujours aussi agaçant comme réponse.

C'est moi qui ait dit que Jiav la présente de travers, et c'est moi qui ait dit que tu la présentes de la même manière.

Suffit de lire mon message, c'était assez clair.

Cordialement,

[GillesH38a]

et moi ma réponse signifie que je suis en désaccord avc toi sur ce point, je pense qu'il présente bien la position computationnaliste, telle qu'elle est défendue par un certain nombre de gens (parfois brillamment intellectuellement d'ailleurs). Ce n'est peut etre pas ta position, mais elle existe ailleurs. Et je pense que c'est bien à celle-là qu'il pensait en ouvrant ce fil.

Cdt

Gilles

[invité576543]

et moi ma réponse signifie que je suis en désaccord avc toi sur ce point (...)la position computationnaliste, telle qu'elle est défendue par un certain nombre de gens (parfois brillamment intellectuellement d'ailleurs).

Aurais-tu une référence précise d'une école de pensée importante, d'auteurs, affirmant que le cerveau (ou l'univers) est un automate à états finis? Je connais le cas de Wolfram, est-ce à ce genre d'approche que Jiav réfère dans son message #1?

Parce que c'est bien une manière dont on peut comprendre votre présentation de la thèse.

Notons encore qu'un ordinateur pourrait être vu comme automate à états finis à deux échelles distinctes si on acceptait la thèse de Wolfram : l'échelle de Planck (ou autre...) et l'échelle de l'automate conçu par les humains. On ne peut pas traiter les deux de la même manière.

C'est le mot "équivalent" (dans la formulation de Jiav) qui rend cette présentation "de travers". C'est un mot trop approximatif pour une discussion sérieuse du sujet.

Cordialement,

[GillesH38a]

ça dépend de ce que tu appelles importante, mais le courant de pensée de la "physique discrète" (digital physics) existe indéniablement

http://en.wikipedia.org/wiki/Digital_physics