C'est décrit dans cet article récent ! C'est un article qui démontre qu'il n'y a pas besoin de se moucher plusieurs fois, donc le trou dans le mouchoir n'est pas trop gênant.
Plus sérieusement, ça démontre qu'on peut faire un système de tuyau dans lequel passe un fluide qui permet de calculer n'importe quelle fonction partielle récursive, d'ou la référence à Stephen Cole Kleene. Le tout en encodant dans la topologie du système de tuyaux la table de transition de l'automate des états d'une machine de Turing.
On voit d'ailleurs dans les deux figures des papiers que la correspondance automate <-> topologie est claire.
Le flot débute dans un état initial, un disque, sur lequel chaque nombre entier a un point. En entrant dans la machine, ce flot va être modifié jusqu'à atteindre l'état final, si le calcul termine, avec la trajectoire qui arrive à l'endroit ou est codé le nombre résultat sur le disque.
Le codage implique l'ensemble de Cantor, codage des états de la machine de Turing (dont la bande), dans lequel on peut par exemple coder les entiers en base 3 [[Ensemble_de_Cantor#%C3%89criture_en_base_3]]. Et donc d'autres trucs, comme l'état d'une machine de Turing dont sa bande.
Dans les deux cas donc, il y a des "portes logiques" si on peut dire, qui vont modifier le flot pour aller d'un point de l'ensemble de cantor un l'autre, qui va coder pour un état de calcul. Il peut y avoir des boucles ou le flot peut repasser plusieurs fois au même endroit.
Et c'est intéressant en particulier pour montrer que des problèmes fondamentaux de système dynamiques, l'existence ou pas de boucle périodiques, sont tout aussi non calculables que le problème de l'arrêt en informatique !
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par thoasm . En réponse au lien Le billard est Turing complet. Évalué à 4.
C'est décrit dans cet article récent ! C'est un article qui démontre qu'il n'y a pas besoin de se moucher plusieurs fois, donc le trou dans le mouchoir n'est pas trop gênant.
https://arxiv.org/pdf/2503.16100
Plus sérieusement, ça démontre qu'on peut faire un système de tuyau dans lequel passe un fluide qui permet de calculer n'importe quelle fonction partielle récursive, d'ou la référence à Stephen Cole Kleene. Le tout en encodant dans la topologie du système de tuyaux la table de transition de l'automate des états d'une machine de Turing.
On voit d'ailleurs dans les deux figures des papiers que la correspondance automate <-> topologie est claire.
Le flot débute dans un état initial, un disque, sur lequel chaque nombre entier a un point. En entrant dans la machine, ce flot va être modifié jusqu'à atteindre l'état final, si le calcul termine, avec la trajectoire qui arrive à l'endroit ou est codé le nombre résultat sur le disque.
Le codage implique l'ensemble de Cantor, codage des états de la machine de Turing (dont la bande), dans lequel on peut par exemple coder les entiers en base 3 [[Ensemble_de_Cantor#%C3%89criture_en_base_3]]. Et donc d'autres trucs, comme l'état d'une machine de Turing dont sa bande.
Dans les deux cas donc, il y a des "portes logiques" si on peut dire, qui vont modifier le flot pour aller d'un point de l'ensemble de cantor un l'autre, qui va coder pour un état de calcul. Il peut y avoir des boucles ou le flot peut repasser plusieurs fois au même endroit.
Et c'est intéressant en particulier pour montrer que des problèmes fondamentaux de système dynamiques, l'existence ou pas de boucle périodiques, sont tout aussi non calculables que le problème de l'arrêt en informatique !