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

[Jiav]

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

[Jiav]

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

[lamorgana]

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

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

[gillesh38]

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

[gillesh38]

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.

[gillesh38]

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,

[lamorgana]

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?