Search

Can every physical system simulate any Turing machine? This is a classical problem that is intimately connected with the undecidability of certain physical phenomena. Concerning fluid flows, Moore [C. Moore, Nonlinearity 4, 199 (1991)] asked if hydrodynamics is capable of performing computations. More recently, Tao launched a program 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 to quantum-field theories. To the best of our knowledge, the existence of undecidable particle paths of threedimensional fluid flows has remained an elusive open problem since Moore's works in the early 1990s. In this article, we construct a Turing complete stationary Euler flow on a Riemannian S3 and speculate on its implications concerning Tao's approach to the blow-up problem in the Navier-Stokes equations. [ABSTRACT FROM AUTHOR]

The quantum-dot cellular automata (QCA) computing paradigm is used to implement Rule 110, a unique one-dimensional cellular automata (CA) that has been proven to be Turing complete. A Turing complete architecture is capable of universal computing, which means that it could be used to implement any arbitrary computation. The optimized design of a single Rule 110 cell is presented, first using Boolean algebra and then by the use of QCA cells. This is followed by simulations to verify the correct behavior of the device and a method for efficiently filling a two-dimensional region with a one-dimensional CA device. [ABSTRACT FROM AUTHOR]

In this short paper, we show that the game description language (GDL) is Turing complete. In particular, we show how to simulate a Turing machine (TM) as a single-player game described in GDL. Positions in the game correspond to configurations of the machine, and the TM accepts its input exactly when the agent has a winning strategy from the initial position. As direct consequences of the Turing completeness of GDL, we show that well formedness as well as some other properties of a GDL description are undecidable. We propose to strengthen the recursion restriction of the original GDL specification into a general recursion restriction. The restricted language is not Turing complete, and the aforementioned properties become decidable. Checking whether a game description satisfies the suggested restriction is as easy as checking that the game is syntactically correct. Finally, we argue that practical expressivity is not affected as all syntactically correct games in a collection of more than 500 games having appeared in previous general game playing (GGP) competitions belong to the proposed GDL fragment. [ABSTRACT FROM PUBLISHER]