New Limit to the Church-Turing Thesis Accounts for Noisy Systems

by Lisa Zyga,  Phys.org

It has previously seemed physical systems could violate the Church-Turing Thesis–a hypothesis developed by computer scientists Alonzo Church and Alan Turing in the 1930s and that in a sense defines what can be a computer–but new research from Princeton University and National University in Santiago, Chile suggests this is not the case.

The presence of noise in a physical system can lead to unpredictable behaviors that seem incomputable, and would therefore violate the Church-Turing Thesis. “The physical interpretation of the 1930s Church-Turing thesis asserts that a physical system cannot be harnessed to perform computations that cannot be performed (in principle) by a standard computer,” the researchers write in a new study.

However, in their study, the researchers found computing the behavior of noisy systems is relatively straightforward. They did so by presenting a new limitation on the ability of physical systems to perform computation in the form of their memory. Using their new definition of memory to formulate what they call the “space-bounded Church-Turing thesis,” they found the limit to a computer simulating a physical system is that they must share about the same amount of working memory. The finding could have implications for the development of so-called “hypercomputers,” devices with computational capabilities well beyond those of existing computers.  Article

DCL: I find this to be a very confused article. Turing and Church (also S.C. Kleene and E. L. Post) were concerned with defining the meaning of a computable number. For this they introduced (independently and more or less concurrently)  different models of computabilty – e.g., Turing machines, Church’s Lambda Calculus, Kleene Recursion equations, and Post production systems. All models of computability were later shown to be equivalent – i.e., anything computable in one formalism was also computable in any of the others. They certainly were not addressing the capabilities of systems that exhibit random behavior – such as “noise”.  See for example, the section on “misunderstandings” in “The Church-Turing Thesis“.