New limit to the Church-Turing thesis accounts for noisy systems

(Phys.org)—The question of what a computer is capable of, and what it is not, has intrigued computer scientists since the 1930s, when Alonzo Church and Alan Turing began investigating the capabilities and limits of computers. In a new study, researchers have explored the computing abilities of noisy physical systems, which are those that are disturbed by random fluctuations.

While previously it has seemed that physical systems may violate the Church-Turing thesis—a conjecture that in a sense defines a computer—here the researchers show that this is not the case for noisy systems due to a new computing limit. The results could have implications for designing super-Turing computers, or "hypercomputers," which are hypothetical devices that outperform all existing computers.

The researchers, Professor Mark Braverman and graduate student Jonathan Schneider at Princeton University, along with Assistant Professor Cristóbal Rojas at the Andrés Bello National University in Santiago, Chile, have published a paper on noise in computing in a recent issue of Physical Review Letters.

"The greatest significance of the study is introducing a new quantitative way of thinking about noise as it affects a dynamical system when the dynamical system is being viewed or used as a computer," Braverman told Phys.org.

As the researchers explain, the presence of noise in a physical system can lead to unpredictable behavior that seems to be incomputable. If this is the case, it would 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 scientists explained. "Yet, it is well-known that even basic physical laws can give rise to chaotic and unpredictable behavior. In some cases, the long-term or steady-state features of such systems can be mathematically proven to not be computable. This seemingly defies the Church-Turing thesis, which implies that all physically realizable systems can be simulated by a computer."

In the new study, however, the researchers show that computing the behavior of noisy systems is actually relatively straightforward, and therefore noisy systems are not capable of performing very complex computations.

"In this paper, we show that the introduction of a small amount of noise into physical systems allows their equilibrium behavior not only to be computed, but even computed relatively efficiently," the scientists wrote.

To explain why this works, the researchers presented a new limitation on the ability of physical systems to perform computation: their memory. To formulate this so-called "space-bounded Church-Turing thesis" (SBCT), the researchers presented a new definition of memory for physical systems as "the maximum amount of information the evolving system can preserve per time step." Using this definition, they showed that a noisy physical system with a given amount of memory can be simulated by a computer that is limited to roughly the same amount of working memory as that of the physical system.

The researchers also showed that the SBCT holds even if a computer has an infinite amount of time to try to solve a problem. The new limitation is not the first variation of the original Church-Turing thesis, but it is different from most other variations in that time is not a limiting factor.

The memory-based limit is of course not the only limit on computing ability—for instance, the complexity of a system is another limit, and often a more stringent one than memory. One advantage of the memory-based limit, however, is that it is generally much easier to estimate a system's amount of memory than other properties, such as complexity.

"The main usefulness of the results is in giving us a relatively simple estimate on the computational power of systems," Braverman said. "Such an estimate is useful when thinking about proposals for super-Turing computation devices."

Super-Turing computation devices, also called "hypercomputers," are hypothetical devices that compute functions that a Turing machine—or any computer available today—cannot. Since these functions are considered incomputable in the Church-Turing sense, super-Turing devices would either need to have an unbounded memory or otherwise circumvent the thesis.

Along with exploring super-Turing computers, the researchers also plan to further investigate the SBCT at a deeper level.

"The most interesting direction is further refining and understanding the notion of 'memory' of a general dynamical system," Braverman said. "Another obvious direction is finding further evidence for or against the SBCT. Evidence against would be particularly exciting, since it would point at devices that can overcome their apparent information-theoretic limitations."

© 2015 Phys.org