Computation as Information Transformation

Abstract

Future progress of new information processing devices capable of dealing with problems such as big data, Internet of things, semantic web, cognitive robotics, neuroinformatics and similar, depends on the adequate and efficient models of computation. We argue that defining computation as information transformation, and given that there is no information without representation, the dynamics of information on the fundamental level is physical/ intrinsic/ natural computation (Dodig-Crnkovic, 2011) (Dodig-Crnkovic, 2014). Intrinsic natural computation occurs on variety of levels of physical processes, such as the levels of computation of living organisms as well as designed computational devices. The present article is building on our typology of models of computation as information processing (Burgin & Dodig-Crnkovic, 2013). It is indicating future paths for the advancement of the field, expected both as a result of the development of new computational models and learning from nature how to better compute using information transformation mechanisms of intrinsic computation. Complexity of the Concept of Computation and Information Transformation In a variety of fields, researchers have been searching for a common definition of computation, from (Turing, 1936)(Kolmogorov, 1953)(Copeland, 1996)(Burgin, 2005) to (Denning, 2010)(Denning, 2014)(Burgin & Dodig-Crnkovic, 2011) and (Hector Zenil, 2012)(Dodig-Crnkovic & Giovagnoli, 2013). Some of these studies of computation are done in an informal setting based on hands-on and research practice, as well as on philosophical and methodological considerations. Yet other research approaches strive to build exact mathematical models to comprehensively describe computation (Denning, 2014). When the Turing machine (or Logical Computing Machine as Turing originally named his logical device) was constructed and accepted as an universal computational model, it was considered as a complete and exact definition of computation (Church-Turing thesis) (Burgin, 1987). However, the absolute nature of the Turing machine was questioned by contemporary research (Cooper, 2012) (Cooper & Leeuwen, 2013) and challenged by adopting a more general formal definition of algorithm (Burgin, 2005). Nevertheless, in spite of all efforts, the conception of computation remains too vague and ambiguous. This vagueness of the foundations of computing has resulted in a variety of approaches, including approaches that contradict each other. Abramsky summarizes the process of successive change of models of computation and their future perspectives as follows: “Traditionally, the dynamics of computing systems, their unfolding behavior in space and time has been a mere means to the end of computing the function which specifies the algorithmic problem which the system is solving. In much of contemporary computing, the situation is reversed: the purpose of the computing system is to exhibit certain behaviour. (…) We need a theory of the dynamics of informatic processes, of interaction, and information flow, as a basis for answering such fundamental questions as: What is computed? What is a process? What are the analogues to Turing completeness and universality when we are concerned with processes and their behaviours, rather than the functions which they compute? (Abramsky, 2008) Abramsky emphasizes that there is the need for second-generation models of computation, and in particular process models. The first generation models of computation originated from problems of formalization of mathematics and logic, while processes or agents, interaction, and information flow are results of recent developments of computers and computing. In the second-generation models of computation, previously isolated systems are replaced by processes and agents for which the interactions with each other and with the environment are fundamental. Hewitt too advocates an agent-type, Actor model of computation (Hewitt, 2012) whi