Computability in Europe 2006
Logical Approaches to Computational Barriers

Invited Plenary Talk:
How We Think of Computing Today

Speaker: Jan van Leeuwen and Jiří Wiedermann
Author(s): Jan van Leeuwen and Jiří Wiedermann


Classical models of computation no longer correspond to our increasingly broadened notion of computing in modern systems. At the same time many systems in the sciences are now being viewed as systems that compute. Can one devise computational models that capture their behavior and that could play the same role for our contemporary ideas on computing as classical Turing machines once did? In an appraisal of various recent approaches we propose two models that capture key mechanisms of current systems in both artificial and natural environments: evolving automata and interactive Turing machines with advice. The two models represent relevant adjustments in our apprehension of computing: the shift from finite computations to potentially non-terminating interactive ones, the shift from rigid computing systems towards systems whose hardware and/or software can change over time, and a shift from uniform machines to computing systems that evolve in an unpredictable, non-uniform way. The two models are shown to be equivalent and demonstrate that, in principle, the `new computing' is more powerful than classical computing as both are provably computationally more powerful models than those covered by the old paradigm. The models also enable a natural extension of classical complexity theory, using the computational resources that come with the paradigm shifts. Naturally, the additional computational power of the models cannot in general be meaningfully exploited in concrete goal-oriented computations.

websites: Arnold Beckmann 2007-12-04