phénomènes physiques et algorithmes

[spi100]

Connaissons-nous des phénomènes physiques impossible à modéliser sous forme algorithmique ?

Si un phénomène physique non programmable (au sens de Turing) est découvert, comment s'en rendre compte et le prouver ?
-----

[Jeanpaul]

La turbulence est un exemple très connu : qu'il s'agisse d'écoulements de fleuves, de flammes, de plasmas, on ne sait pas prédire le comportement de ces objets.
On arrive bien-sûr à faire des moyennes et à modéliser des comportements moyens mais l'instabilité naturelle fait qu'il reste une part non prédictible.

[spi100]

Est - ce que tu as une référence qui détaille ça ? Je n'ai rien trouvé sur le web. La seule chose que j'ai trouvé est que les automates cellulaires presentent des propriétés chaotiques ... et pourtant ils sont bien décrits par un algorithme.

[Jeanpaul]

En tapant turbulence + chaos sur Google, on trouve plein de trucs. Par exemple, voici un site qui explique simplement les choses, mais il y en a plein d'autres.
http://www.e-scio.net/mecaflu/turbulence.php3

Il existe effectivement des automates cellulaires, comme le jeu de la vie, qui modélisent une certaine réalité au moyen d'algorithmes. Par exemple, on met des molécules dans des cases et on les regarde bouger. La première exigence de ce genre de modèle est qu'il faut respecter la conservation des grandeurs physiques (masse, énergie, quantité de mouvement, moment cinétique). Ensuite il faut trouver des lois physiques qui modélisent les interactions.
Un intéressant modèle de turbulence est la circulation automobile : il existe une relation entre la vitesse moyenne des véhicules et le débit (maximum : 2500 véhicules par heure et par file). Question : comment le comportement de chaque conducteur influence-t-il le flux ? On sait bien que plus on va vite, plus on laisse de place mais encore ?

[A voir en vidéo sur Futura]

[spi100]

Oui je connais un peu la théorie de la turbulence et un peu mieux celle du chaos (surtout dissipatif). Mais est-ce que ca a bien un rapport avec la "computabilité" au sens de turing ?
Par exemple, le comportement du jeu de la vie est "computable", mais très difficilement prévisible. On peut peut-être en dire autant des systèmes chaotiques, algorithmiquement simples mais comportementalement complexes.
Quand je parle de phénomènes qui ne soient pas "computables", je pense plutot à des problèmes du type :

1/ Trouver un algo qui est capable de dire si n'importe quel algo s'arrete ou pas ?
2/ Calculer le nombre de Chaitin.

Deux exemples de problèmes qui sont absolument impossibles à mettre sous forme algorithmique et ce n'est pas une question de complexité.

[Seb299792]

Il n'y a qu'a voir les modèles de prévisions météorologique.
C'est un bon exemple.
On fait des prédictions mais on est jamais certain.

[spi100]

Il n'y a qu'a voir les modèles de prévisions météorologique.
C'est un bon exemple.
On fait des prédictions mais on est jamais certain.

Oui, un modèle très simple comme celui de Lorentz est computable mais donne un comportement chaotique i.e. hyper-sensible aux erreurs sur les conditions initiales.

[spi100]

Ca y est, j'ai une ref qui va bien dans le sens de ce que propose Jean-Paul.

http://fgc.math.ist.utl.pt/workshop/ribeiro.pdf

The undecidability in Natural Sciences arise from the fact that maps for chaotic behaviours are non invertible (Baker and Gollub, 1990, p. 90) “that is, it is always possible to predict from but there is ambiguity in trying to retrodict from “, when x is the variable and n refers to successive time intervals. So Nature decides by solving the direct problem but the knower must solve the indirect problem: an input produces unique input but the input cannot be predicted unambiguously from the output

Si je comprends bien, dans l'impossibilité d'inverser la transformation du boulanger, on a quelchose de similaire au 'halting problem' de turing.
La donnée de correspond à la donnée du programme P, et la détermination de à la détermination de la valeur de HALT(P). L'impossiblité de trouver une procédure systématique pour déduire de correspond à l'impossibilité de trouver une fonction générale telle que HALT(P).

[Seb299792]

Oui, un modèle très simple comme celui de Lorentz est computable mais donne un comportement chaotique i.e. hyper-sensible aux erreurs sur les conditions initiales.

Mais effectivement, la non capacité à la modélisation vient plus de la complexité, du nombre d'intéractions et de paramètres que des lois de bases.