Construyendo fluidos de Euler Turing-completos en dimensión tres

Autores: Robert Cardona, Eva Miranda, Daniel Peralta-Salas (ICMAT-CSIC) and Francisco Presas (ICMAT-CSIC)

Fuente: Proceedings of the National Academy of Sciences vol. 118, no. 19

Fecha de publicación: 11 de mayo de 2021

Link

Resumen:

Una máquina de Turing es un dispositivo teórico capaz de manipular un conjunto de símbolos impresos sobre una cinta, siguiendo ciertas reglas. Lo interesante es que cualquier algoritmo se puede describir empleando máquinas de Turing. Además, el poder computacional de los sistemas físicos se puede medir en función de su capacidad para simular una máquina de Turing universal. Durante las últimas décadas, se ha mostrado que varios procesos físicos se pueden simular con máquinas de Turing –lo que se denomina completitud Turing–: desde problemas de trazado de rayos en sistemas ópticos 3D hasta redes neuronales o teorías de campos topológicos no abelianos. Por otro lado, la completitud Turing de un sistema físico se relaciona con la indecibilidad de su evolución, que puede entenderse como una emergencia de complejidad totalmente distinta al comportamiento caótico

Hasta el momento, se sabe muy poco del poder computacional de la dinámica de fluidos. En 1991, Chris Moore preguntó: ¿es posible que un fluido simule una máquina de Turing universal? Esta pregunta ha sido recientemente considerada por Terence Tao, en relación con el estudio de la regularidad de las ecuaciones de Euler y de Navier-Stokes. En concreto, Tao especula con la relación entre un posible estallido de las ecuaciones de Navier-Stokes, la completitud Turing y la computación fluida.

En el artículo reseñado los autores construyen un flujo de fluido incomprensible y estacionario sobre una esfera riemanniana de dimensión tres, que es Turing-completo. Esto significa que no existe un algoritmo capaz de garantizar que cualquier partícula del fluido vaya a pasar por cierta región del espacio en tiempo finito. Esta incapacidad de predicción puede verse como una nueva manifestación del comportamiento turbulento de los fluidos.

Para construir el flujo Turing-completo, los autores emplean la relación profunda que existe entre las máquinas de Turing y la dinámica simbólica. La máquina de Turing recibe, como datos de entrada, una secuencia de ceros y uno y, después de un número de pasos, ofrece un resultado, también formado por ceros y unos. Si podemos simular cualquier máquina de este tipo con un sistema dinámico sobre M, como por ejemplo, un flujo de Euler, entonces el sistema dinámico es Turing-completo. Esto quiere decir que la parada de cualquier máquina de Turing con un cierto input es equivalente a cierta trayectoria acotada de la dinámica dentro de un conjunto abierto en M. Esto se puede entender como un ordenador fluido: toma como dato de entrada un punto en el espacio, lo procesa –siguiendo la trayectoria del fluido en ese punto– y ofrece como resultado la siguiente región a la que el fluido se ha movido.

Los autores son capaces de construir un tipo de función que es Turing-completo, en concreto un difeomorfismo del disco, que conserva el área. Para ello, emplean la teoría desarrollada por Moore al comienzo de la década de 1990. En concreto, la restricción de esta función al conjunto cuadrado de Cantor es conjugado a la función de transición de una máquina de Turing universal (usando una asignación canónica entre las configuraciones de una máquina de Turing y los puntos del conjunto cuadrado de Cantor).