In this article, we pursue our investigation of the connections between the theory of computation and hydrodynamics. We prove the existence of stationary solutions of the Euler equations in Euclidean space, of Beltrami type, that can simulate a universal Turing machine. In particular, these solutions possess undecidable trajectories. Heretofore, the known Turing complete constructions of steady Euler flows in dimension 3 or higher were not associated to a prescribed metric. Our solutions do not have finite energy, and their construction makes crucial use of the non-compactness of $\mathbb R^3$, however they can be employed to show that an arbitrary tape-bounded Turing machine can be robustly simulated by a Beltrami flow on $\mathbb T^3$ (with the standard flat metric). This shows that there exist steady solutions to the Euler equations on the flat torus exhibiting dynamical phenomena of (robust) arbitrarily high computational complexity. We also quantify the energetic cost for a Beltrami field on $\mathbb T^3$ to simulate a tape-bounded Turing machine, thus providing additional support for the space-bounded Church-Turing thesis. Another implication of our construction is that a Gaussian random Beltrami field on Euclidean space exhibits arbitrarily high computational complexity with probability $1$. Finally, our proof also yields Turing complete flows and maps on $\mathbb{S}^2$ with zero topological entropy, thus disclosing a certain degree of independence within different hierarchies of complexity.
翻译:在此篇文章中, 我们继续调查计算理论和流体动力学之间的联系。 我们证明在Euclidean空间的Euler 方程式存在固定的解决方案, 可以模拟通用图灵机器。 特别是, 这些解决方案具有不可分的轨迹。 已知的图灵在维度3或以上稳定的尤利尔流的完整构造与一个规定的度量无关。 我们的解决方案没有一定的能量, 其构建也十分关键地利用了 $\mathbb R3$的非复合性, 但是它们可以用来显示 任意粘贴图灵的机器可以由 $\mathbb T%3 的 Beltramier 方程式强有力地模拟。 这显示, 平面上的 Euler 方程式的构造有稳定的解决方案, 展示了完全的复杂度( robrat) 。 我们还量化了 $mathbrb R&R3$, 但它可以用来显示一个任意粘贴的图质的平面机器, 从而模拟了我们高空基的直流的直流。