Nou article a PNAS d'Eva Miranda: els billars bidimensionals poden simular qualsevol màquina de Turing

Els billars són un dels models més clàssics de moviment determinista: una partícula es desplaça lliurement i rebota de manera especular contra unes parets rígides. Els autors demostren que, fins i tot en dues dimensions, les trajectòries d'un billar poden simular màquines de Turing arbitràries. El resultat resol un problema obert plantejat per Cristopher Moore. Moore havia suggerit que els billars de dimensió prou alta, sobretot els tridimensionals, podien suportar computació universal, però que els sistemes de baixa dimensió podien quedar per sota del llindar d'universalitat.

La conseqüència és profunda. Com que el problema de l'aturada de Turing és indecidible, apareixen trajectòries indecidibles en models de billar físicament naturals: hi ha preguntes sobre el moviment de la bola que cap algorisme no pot respondre. Això és rellevant perquè els billars sorgeixen com a límits de sistemes hamiltonians llisos amb potencials de confinament molt pronunciats, i com a reformulació exacta de la dinàmica de gasos d'esferes dures. L'article també explora una connexió amb els límits de cadenes de col·lisions en mecànica celeste. L'article es va escriure durant l'estada d'Eva Miranda a Zúric com a Nachdiplom lecturer a l'FIM de l'ETH durant el semestre de tardor de 2025.

Aquest treball se suma a l'article Turing complete Navier-Stokes steady states via cosymplectic geometry, publicat el maig de 2026 a PNAS Nexus per Søren Dyhr, doctorand d'Eva Miranda, juntament amb Ángel González-Prieto, Eva Miranda i Daniel Peralta-Salas. Aquest article estén la capacitat de computació universal als estats estacionaris de les equacions de Navier-Stokes, és a dir, a fluids viscosos, mitjançant geometria cosimplèctica. Tots dos treballs continuen la línia iniciada amb Constructing Turing complete Euler flows in dimension 3, publicat a PNAS el 2021. Aquella recerca va demostrar que els fluids ideals en dimensió 3 poden ser Turing complets.

E. Miranda i I. Ramos, Two-dimensional billiards are Turing complete, Proc. Natl. Acad. Sci. U.S.A. 123 (37), e2614500123 (2026).