Machine de Turing : Démonstration

Déjà il faut préciser dans quel sens "le jeu de la vie est une machine Turing" : comment spécifie-t-on la machine de Turing, comment convertir les données sur la bande en format "jeu de la vie"... C'est je pense le plus compliqué. Une fois cette correspondance établie, je pense que ce n'est pas trop dur de voir que le jeu de la vie peut simuler n'importe quelle machine de Turing.

Et pour ta question de "trouver empiriquement", c'est comme ça pour tous les théorèmes en fait. On connaît un certain nombres de théorèmes T1, T2, T3,.... T500 et on cherche à montrer un nouveau théorème T501. Ce que font les chercheurs c'est d'essayer d'imbriquer les différents théorèmes T1,... T500 jusqu'à trouver une construction correcte permettant de déduire T501. Bien sûr on ne le fait pas totalement "au hasard", l'intuition et la compréhension peut donner des idées pour imbriquer les choses mais le processus est fondamentalement "empirique" (pour reprendre tes mots).

C'est d'ailleurs pour ça que la recherche fondamentale avance si lentement : il faut tester toutes les combinaisons possibles de théorèmes pour voir si ça produit quelque chose d'intéressant. S'il y avait une méthode toute faite permettant de démontrer tous les théorèmes, le métier de chercheur n'existerait pas (heureusement, certains théorèmes nous laissent à pense qu'une telle méthode ne peut pas exister ).

Je me suis peut-être mal exprimé, quand je parlais d'empirique, je ne parlais pas de démontrer un théorème ! Mais de démontrer si "tel système avec telles lois (ex. jeu de la vie) peut abriter une machine de Turing" ceci n'est pas un théorème, c'est une verification dans un cas particulier.

Eh bien si c'est un théorème. Tout comme "$((1, 2), (1,3))$ est une famille libre de $\R^2$" ou "toute suite géométrique est de la forme $(aq^n)_n$ avec $a,q\in\R$" ou encore "un entier possède toujours un unique successeur" (c'est un théorème particulier, il s'agit d'un axiome).

Et non je ne vois pas comment tu peux automatiser ce genre ce choses : tu as un truc qui a priori n'a rien à voir avec une machine de Turing (le jeu de la vie), il faut donc comprendre assez en profondeur les mécanismes du jeu de la vie pour espérer établir une correspondance entre les deux.

Il faut voir que les "exos" du type "montrer que telle famille est libre" n'en sont pas vraiment : tu as juste à appliquer mécaniquement la méthode du cours et tu obtiens le résultat (si tu ne t'es pas trompé dans les calculs). Je ne dis pas que c'est inutile de faire de tels exos, mais il ne s'agit que de "gammes" fabriquées de toutes pièces pour s'exercer car une méthode existe.

Ce qui est plus intéressant c'est de montrer que cette méthode fonctionnera à tous les coups ou encore mieux, trouver tout seul cette méthode. Et pour montrer ça, point de "méthode toute faite" : il faut comprendre en profondeur ce qu'est une famille libre et la relation avec les systèmes.

Ai-je été clair ?

Une machine de Von Neumann a supplanté la machine de Turing comme abstraction de l'ordinateur. Elle était universelle, du moins jusqu'à l'arrivée de l'ordinateur quantique. Ce n'est pas parce qu'un thème n'est pas rebattu par la presse qu'il est clos...