We show that two-dimensional billiard systems are Turing complete by encoding their dynamics within the framework of Topological Kleene Field Theory. Billiards serve as idealized models of particle motion with elastic reflections and arise naturally as limits of smooth Hamiltonian systems under steep confining potentials. Our results establish the existence of undecidable trajectories in physically natural billiard-type models, including billiard-type models arising in hard-sphere gases and in collision-chain limits of celestial mechanics.
(je ne met pas directement le lien parce que peu de gens savent ce qu'est la théorie topologique des champs de Kleene. Il y en a ici d'ailleurs ?)
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 !
Posté par antistress (site web personnel) .
Évalué à 3 (+0/-0).
Dernière modification le 24 décembre 2025 à 10:53.
En même temps ca ne m'étonne pas ; les taupes devaient bien découvrir un jour que le billard était un jeu de trous. C'est juste qu'elles n'allaient pas dans les cafés jusque ici. La voilà la nouveauté.
# Le lien ArXiv direct « Classical billiards can compute »
Posté par thoasm . Évalué à 5 (+3/-1).
https://arxiv.org/abs/2512.19156
Abstract
(je ne met pas directement le lien parce que peu de gens savent ce qu'est la théorie topologique des champs de Kleene. Il y en a ici d'ailleurs ?)
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par dovik (site web personnel) . Évalué à 10 (+9/-0).
Ne nous sous estime pas : on connaît très bien la théorie de la taupe logique des champs de Kleenex.
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par Benoît Sibaud (site web personnel) . Évalué à 8 (+5/-0).
Foutue taupe qui fait des trous dans les mouchoirs !
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par thoasm . Évalué à 4 (+1/-0).
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 !
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par dovik (site web personnel) . Évalué à 2 (+0/-0).
Foutue taupe.
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par antistress (site web personnel) . Évalué à 3 (+0/-0). Dernière modification le 24 décembre 2025 à 10:53.
En même temps ca ne m'étonne pas ; les taupes devaient bien découvrir un jour que le billard était un jeu de trous. C'est juste qu'elles n'allaient pas dans les cafés jusque ici. La voilà la nouveauté.
[^] # Re: Le lien ArXiv direct « Classical billiards can compute »
Posté par BAud (site web personnel) . Évalué à 2 (+0/-0). Dernière modification le 24 décembre 2025 à 17:48.
eh ! on avait un baby-foot dans notre prépa taupe !
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.