Simulación de máquinas de Turing con {O,P}DEs.

Question

Qiaochu Yuan en su respuesta a esta pregunta recuerda un entrada del blog (concretamente, el comentario 16) de Terry Tao:

Por ejemplo, no se puede esperar encontrar un algoritmo para determinar la existencia de soluciones suaves a ecuaciones diferenciales parciales no lineales arbitrarias, porque es posible simular una máquina de Turing utilizando las leyes de la física clásica, que a su vez pueden modelarse utilizando (un sistema moderadamente complicado de) EDP no lineales

• ¿Es este "es posible" una aplicación de un Tesis de Newton como el habitual Tesis de Church-Turing Si algo es imaginable en la vida real, se puede simular con las ecuaciones habituales de la física", o ¿se ha realizado realmente la simulación?

• ¿Se necesitan EDP para simular máquinas de Turing, o bastan las EDP?

Answer 1

Las ODEs son lo suficientemente buenas. Tu comentario me hizo empezar a indagar.

Answer 2

Creo que la referencia es al trabajo seminal de Pour-El y Richards donde miden el contenido computacional de varios tipos de sistemas clásicos de ecuaciones diferenciales parciales. Tienen una serie de trabajos donde realizan esto; creo que gran parte de ellos se pueden encontrar en su libro Computabilidad en análisis y física (Perspectivas en lógica matemática, Springer-Verlag, 1989). Hay otros enfoques al respecto, pero todos llegan esencialmente a las mismas conclusiones. Pour-El y Richards tienen la ventaja de que se concentran en sistemas específicos que surgen realmente en la física, como la ecuación de onda.