Understanding Computation. A General Theory of Computational Processes

0520377 - ÚI 2020 NL eng V - Výzkumná zpráva
van Leeuwen, J. - Wiedermann, Jiří
Understanding Computation. A General Theory of Computational Processes.
Utrecht: Utrecht University, 2019. 100 s. Technical Report, UU-CS-2019-012. ISSN 0924-3275
Grant ostatní: AV ČR(CZ) StrategieAV21/1
Program: StrategieAV
Institucionální podpora: RVO:67985807
Klíčová slova: computation * computational processes * dynamical systems * epistemic theory * metric spaces * philosophy of computing * topology
http://www.cs.uu.nl/research/techreps/repo/CS-2019/2019-012.pdf

The notion of computation is well understood, and well formalized, in the classical context of digital information processing. However, the paradigm of computation is increasingly used in the characterization of processes in sciences like physics and biology as well. This seems to recognize computation more broadly as an ‘elementary mechanism of nature’, not limited to the digital domain. What is computation, if it is observed in this broader sense? Without computers as the single defining mechanism, classical abstractions like Turing machines and rewrite systems seem to be unsuited to capture its newer meanings. Following our epistemic approach, we develop a new framework for understanding computation and, as a consequence, for understanding computational processes, based on observed trajectories (curves) of computational activity in suitable metric spaces. With computational processes rather than all sorts of different models of computation as the core abstraction, one can model and characterize many aspects of computation as a mathematical object, from composition to computational and structural complexity. Discrete computations appear as projections of continuous ones, clarifying complex issue from Turing’s 1948 report. We present both the philosophy and a first outline of the implied, machine-independent, general mathematical theory of computation.

Trvalý link: http://hdl.handle.net/11104/0305053