Non-Classical Turing Machines: Extending the Notion of Computation

Authors: Jiří Wiedermann, J. van Leeuwen
Publication year: 2017
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Ninth Workshop on Non-Classical Models of Automata and Applications
Bibliographic citation: WIEDERMANN, Jiří, VAN LEEUWEN, J. Non-Classical Turing Machines: Extending the Notion of Computation. In: FREUND, R., MRÁZ, F., PRŮŠA, D., eds. Ninth Workshop on Non-Classical Models of Automata and Applications. Wien: Österreichische Computer Gesellschaft, 2017, S. 29-40. ISBN 978-3-903035-18-8.
ID: 477257

Abstract

The goal of this paper is to broaden our understanding of computations based on the classical paradigm of Turing machines. To this end we will point to models of non-classical Turing machines that capture computational behavior of contemporary or emerging computing technologies and that have been designed and studied by the authors. The guiding design principles of such machines have been the currently existing or foreseeable technologies such as interactivity, non-uniform evolution, unbounded time behavior, process cooperation, and relativistic time-space effects. The computational behavior of these models and the fact that they mirror key aspects of present or envisaged technologies jointly offer compelling reasons for modifying the traditional and persisting view of computation. This change is quite a profound one: computations should no longer be seen as finite processes whose parameters are fixed before the start of processing. Rather, computations are potentially infinite evolutionary processes whose parameters can change during the processing in an unpredictable way in interaction with their environment.