Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstructing Turing complete Euler flows in dimension $3$
163
0
0.0
(
0
)
Added by
Eva Miranda
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Can every physical system simulate any Turing machine? This is a classical problem which is intimately connected with the undecidability of certain physical phenomena. Concerning fluid flows, Moore asked in [15] if hydrodynamics is capable of performing computations. More recently, Tao launched a programme based on the Turing completeness of the Euler equations to address the blow up problem in the Navier-Stokes equations. In this direction, the undecidability of some physical systems has been studied in recent years, from the quantum gap problem [7] to quantum field theories [11]. To the best of our knowledge, the existence of undecidable particle paths of 3D fluid flows has remained an elusive open problem since Moores works in the early 1990s. In this article we construct a Turing complete stationary Euler flow on a Riemannian $S^3$ and speculate on its implications concerning Taos approach to the blow up problem in the Navier-Stokes equations.
rate research
Read More
Neuromorphic computing is a non-von Neumann computing paradigm that performs computation by emulating the human brain. Neuromorphic systems are extremely energy-efficient and known to consume thousands of times less power than CPUs and GPUs. They have the potential to drive critical use cases such as autonomous vehicles, edge computing and internet of things in the future. For this reason, they are sought to be an indispensable part of the future computing landscape. Neuromorphic systems are mainly used for spike-based machine learning applications, although there are some non-machine learning applications in graph theory, differential equations, and spike-based simulations. These applications suggest that neuromorphic computing might be capable of general-purpose computing. However, general-purpose computability of neuromorphic computing has not been established yet. In this work, we prove that neuromorphic computing is Turing-complete and therefore capable of general-purpose computing. Specifically, we present a model of neuromorphic computing, with just two neuron parameters (threshold and leak), and two synaptic parameters (weight and delay). We devise neuromorphic circuits for computing all the {mu}-recursive functions (i.e., constant, successor and projection functions) and all the {mu}-recursive operators (i.e., composition, primitive recursion and minimization operators). Given that the {mu}-recursive functions and operators are precisely the ones that can be computed using a Turing machine, this work establishes the Turing-completeness of neuromorphic computing.
The dynamics of an inviscid and incompressible fluid flow on a Riemannian manifold is governed by the Euler equations. Recently, Tao [35,36] launched a programme to address the global existence problem for the Euler and Navier Stokes equations based on the concept of universality. In this article we prove that the Euler equations exhibit universality features. More precisely, we show that any non-autonomous flow on a compact manifold can be extended to a smooth solution of the Euler equations on some Riemannian manifold of possibly higher dimension. The solutions we construct are stationary of Beltrami type, so they exist for all time. Using this result, we establish the Turing completeness of the Euler flows, i.e. that there exist solutions that encode a universal Turing machine and, in particular, these solutions have undecidable trajectories. Our proofs deepen the correspondence between contact topology and hydrodynamics, which is key to establish the universality of the Reeb flows and their Beltrami counterparts. An essential ingredient in the proofs is a novel flexibility theorem for embeddings in Reeb dynamics in terms of an $h$-principle in contact geometry, which unveils the flexible behavior of the steady Euler flows.
We show that a topologically mixing $C^infty$ Anosov flow on a 3 dimensional compact manifold is exponential mixing with respect to any equilibrium measure with Holder potential.
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k greater than or equal to 4 is QMA1-complete. Quantum 3-SAT was known to be contained in QMA1, but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.
We study stability of unidirectional flows for the linearized 2D $alpha$-Euler equations on the torus. The unidirectional flows are steady states whose vorticity is given by Fourier modes corresponding to a vector $mathbf p in mathbb Z^{2}$. We linearize the $alpha$-Euler equation and write the linearized operator $L_{B} $ in $ell^{2}(mathbb Z^{2})$ as a direct sum of one-dimensional difference operators $L_{B,mathbf q}$ in $ell^{2}(mathbb Z)$ parametrized by some vectors $mathbf qinmathbb Z^2$ such that the set ${mathbf q +n mathbf p:n in mathbb Z}$ covers the entire grid $mathbb Z^{2}$. The set ${mathbf q +n mathbf p:n in mathbb Z}$ can have zero, one, or two points inside the disk of radius $|mathbf p|$. We consider the case where the set ${mathbf q +n mathbf p:n in mathbb Z}$ has exactly one point in the open disc of radius $mathbf p$. We show that unidirectional flows that satisfy this condition are linearly unstable. Our main result is an instability theorem that provides a necessary and sufficient condition for the existence of a positive eigenvalue to the operator $L_{B,mathbf q}$ in terms of equations involving certain continued fractions. Moreover, we are also able to provide a complete characterization of the corresponding eigenvector. The proof is based on the use of continued fractions techniques expanding upon the ideas of Friedlander and Howard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
