Exploring the Frontiers of Computability

by Jiri Wiedermann and Jan van Leeuwen

Modern networked computers challenge the assumption of classical computability theory: they are always on, interact with each other and their environment, and their functionality can change with time. At the Institute of Computer Science of the Academy of Sciences of the Czech Republic (a member institute of CRCIM) in Prague and the Institute of Information and Computing Sciences at Utrecht University, extensions of computability theory are developed that capture the current ways of information processing in computer networks.

In 1936 A. M. Turing invented a universal model of computation that has served as the basis of computability theory ever since. The principles of operation of a Turing machine capture the way computational tasks are performed by humans as well as by digital computers. The presumed generality of the model is expressed in the so-called Church-Turing Thesis, stating that whatever is computable by an algorithm, in a reasonable sense of the word, is computable by the Turing machine. Note that this thesis cannot be proved as a mathematical theorem, since it does not specify what is a reasonable sense of the word ‘computable’ nor what an algorithm is.

Computations challenging the Church Turing thesis have been studied since Turing’s times. As a rule, the respective computational models were hardly ‘reasonable’ ones: they made use of (physically infeasible) in finite precision real number arithmetic, used auxiliary information from non-computable ‘oracles’ and so on. Nevertheless, as new insights into the nature of computations from physics (cf. quantum computing), biology and contemporary information processing technologies emerge, we are witnessing an upsurge in exploring the limits of computation. More than half a century after its invention, the presumed generality of the Turing machine is at stake.

Modern networked computers challenge the assumptions of the classical computability theory in several ways. For instance, they operate practically uninterruptedly since the moment of their installation. They obtain their inputs via many different channels at unpredictable times, deliver responses continuously, accumulate information over the course of their entire existence and use it across the boundaries of separate ‘runs’. Also, parts of their underlying hardware and software are upgraded whenever an ‘external agent’ decides to do so, without loss of vital data. The most prominent example is the Internet. It can be seen as a wide-area computing infrastructure, a kind of global computer, evolving unpredictably, with unpredictable computing characteristics.

Compared to the classical computing scenario, the changes in modern computing technology can be subsumed under three complementary issues: interactivity, non-uniform evolution (or adaptivity), and non-stop operation ‘ad infinitum’. The systems performing according to these three qualities together constitute what is meant by evolving interactive computing.

Many people, especially in the software engineering community observed that these systems do not not fit the classical Turing machine paradigm. Surprisingly, evolving interactive computing not only arises in current, highly networked computer systems but also in the the information processing in (societies of) living organisms. At the Institutes of Computer Science in Prague (part of CRCIM) and Utrecht, a mathematical theory of computation by ‘lineages’ of machines is being developed to capture the principles of evolving interactive computing. Lineages of machines operate on unbounded (infinite) streams of inputs and have attractive computational properties. Lineages can be shown to be equivalent to ‘interactive’ Turing machines that are extended by an oracle-type mechanism known as advice in the context of computational complexity theory. As these machines are provably computationally more powerful than classical Turing machines, even if the latter are extended so as to work on infinite input streams, it has formally exhibited that evolving interactive computing goes beyond the realm of Church-Turing computability. Presently the theory of lineages of machines is being extended so as to cover further phenomena and complexity-theoretic properties.

The quest for computing beyond Turing machine limits has also gained interest in theoretical physics. It has been recently shown that general relativity theory permits the idea of observing the infinity of certain discrete processes in finite physical time. The idea is based on speculations about effects of strong gravitational fields on time and has lead to the concept of relativistic computing. From the viewpoint of computability theory, relativistic computers can be seen as Turing machines with a suitable oracle, but the fact that these computers are based on apparently realistic ‘thought experiments’ gives them a special status. The consequences for the foundations of computing have begun to occupy philosophers, physicists, and recently also mathematicians and computer scientists.

The study of the computational power of relativistic computations has given rise to an interesting instance of the use of oracle calls as a resource, and several results have been proved for it by the authors. One must bear in mind that, unlike the evolving interactive systems that do exist, the existence of relativistic computing models has not been experimentally verified.
As a result, it appears that classical Turing machine computing not only fails to determine the limits of what is computable, it even fails to capture the computational power of current algorithmic systems. The quest for a better, more efficient, more powerful, and more general realistic model of computing is a highly interesting challenge. No matter how the resulting theory would look like, it is clear that what computers can or cannot compute, and how efficiently they will do what they can, is not only determined by pure mathematics, but also by the laws of physics.

The research reported here was partially supported by GACRgrant No. 201/02/1456 and by EC Contract IST-1999-14186 (Project ALCOM-FT).

Links:
See the recent technical reports by the authors at http://www.cs.cas.cz/ and http://www.cs.uu.nl/

Please contact:
Jirí Wiedermann, CRCIM
Tel: +4202 6605 3520
E-mail: jiri.wiedermann@cs.cas.cz