Simulation of Turing machines with analytic discrete ODEs: Polynomial-time and space over the reals characterised with discrete ordinary differential equations

Abstract

We prove that functions over the reals computable in polynomial time can be characterised using discrete ordinary differential equations (ODE), also known as finite differences. We also provide a characterisation of functions computable in polynomial space over the reals.

While existing characterisations could only cover time complexity or were restricted to functions over the integers, here we deal with real numbers and also cover space complexity.
Furthermore, we prove that no artificial sign or test function is needed even for time complexity.

At a technical level, this is obtained by proving that Turing machines can be simulated with analytic discrete ordinary differential equations. We believe this result opens the way to many applications, as it opens the possibility of programming with ODEs, with an underlying well-understood time and space complexity.