New Challenges for the Church-Turing Thesis

Society & HLRS
New Challenges for the Church-Turing Thesis

Dr. Florian Steinberg / TU Darmstadt

Abstract
One of the interpretations of the Church-Turing Thesis is that an operation is computable if and only if it can be computed by a physical device.Traditionally the "operations" are functions on the natural numbers,computability is defined via Turing machines and the "physical devices"are digital computers.Many applications from engineering and mathematics require to talk about functions on continuous structures like the real numbers.Computable analysis provides a realistic and well accepted model for computations on continuous structures.This opens new perspectives on the Church-Turing Thesis as formulated above:Using computable analysis it is possible to ask whether or not the operation of solving a partial differential equation is computable.Solutions of partial differential equations describe the behavior of real world systems; these systems can be used as devices to carry out computations.Thus, under the assumption that the Church-Turing Thesis remains true in this extended setting, the solution operators of those differential equations that describe real world processes should be computable.It came as a big surprise when in 1983 Pour-El and Richards provided computable initial conditions for the three dimensional wave equation such that the solution after one time-step is not computable.The resolution of this paradox is folklore in the community of computable analysis and has been discussed in detail in a publication of Weihrauch and Zhong from 2002.The talk introduces the necessary tools to understand the paradox,presents its resolution and discusses some of the consequences which this paradox and its resolution have for modern developments in the field.