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) which is suitable for modeling of physical (intrinsic) computation.

In the historical perspective, the development of the concept of computation on the practical level related to operations performed by people and physical objects used as computing devices, while on the theoretical level computation was represented by abstract models and processes.

Variety of current approaches to the concept of computation shows remarkable complexity that makes communication of related results and ideas increasingly difficult. We explicated present diversity of concepts and models in (Burgin & Dodig-Crnkovic, 2013) to highlight the necessity of establishing relationships and common understanding. The analysis of the present state of the art allowed us to discover basic structures inherent for computation and to develop a multifaceted typology of computations. We presented the structural framework of information processing and computation with triadic relationships between (information processing (computation), algorithm and device/agent); (data, context/environment and function/goal); (structure, physical and mental/cognitive); (program, device and data), etc. Those are combined to form action computation pyramid with ((data, device/agent, program) and information processing/computation). An effective methodology of our approach is to find essential features of computation with the goal to explicate its nature and to build adequate models for research and technology. Our conclusion is that different models of computation may have their specific uses and applications, and it is necessary to understand their mutual relationships and the assumptions under which they apply in order to be able to consistently use them.

We underline several topics of importance for the development of new understanding of computing and its role: natural computation and the relationship between the model and physical implementation, interactivity as fundamental for computational modeling of concurrent information processing systems such as living organisms and their networks, and the new developments in modeling needed to support this generalized framework.

In such a way, we achieve better understanding of computation as information processing than we had before. As there is no information without (physical) representation (Landauer, 1996), the dynamics of information in nature is implemented on different levels of granularity by different physical processes, including the level of computation performed by computing machines (designed computation), as well as by living organisms (intrinsic computation) (Dodig-Crnkovic, 2014).

There are still many open problems related to the nature of information and computation, as well as to their relationships. How is information dynamics implemented/represented in computational systems, in machines, as well as in living organisms? Are computers processing only data or information or can they be made to process knowledge as well? What do we know of computational processes in machines and living organisms and how these processes are related? What can we learn from natural computational processes that can be useful for the development of information systems and knowledge management?

Our aim is to contribute to the future development by the exposition and delimitation of possibilities of the unified concept of computation understood as information processing (information transformation).

References and Notes

Abramsky, S. (2008). Information, Processes and Games. In J. Benthem van & P. Adriaans (Eds.), Philosophy of Information (pp. 483–549). Amsterdam, The Netherlands: North Holland.

Burgin, M. (1987). The Notion of Algorithm and the Turing-Church Thesis. In Proc. of the VIII International Congress on Logic, Methodology and Philosophy of Science, v.5 part 1 (pp. 138–140).

Burgin, M. (2005). Super-Recursive Algorithms. New York: Springer-Verlag New York Inc.

Burgin, M., & Dodig-Crnkovic, G. (2011). Information and Computation – Omnipresent and Pervasive. In Information and Computation (pp. vii –xxxii). New York/London/Singapore: World Scientific Pub Co Inc.

Burgin, M., & Dodig-Crnkovic, G. (2013). Typologies of Computation and Computational Models. Arxiv.org, arXiv:1312.

Cooper, S. B. (2012). The Mathematician’s Bias - and the Return to Embodied Computation. In H. Zenil (Ed.), A Computable Universe: Understanding and Exploring Nature as Computation. World Scientific Pub Co Inc.

Cooper, S. B., & Leeuwen, J. van. (2013). Alan Turing. His work and impact. Elsevier Science.

Copeland, B. J. (1996). What is computation? Synthese, 108(3), 335–359.

Denning, P. (2010). What is computation?: Editor’s Introduction. Ubiquity, (October), 1–2.

Denning, P. (2014). Structure and Organization of Computing. In J. Tucker, A., Gonzalez, T., Topi, H. and Diaz-Herrera (Ed.), Computing Handbook. Computer Science and Software Engineering. Chapman & Hall/CRC.

Dodig-Crnkovic, G. (2011). Dynamics of Information as Natural Computation. Information, 2(3), 460–477.

Dodig-Crnkovic, G. (2014). Modeling Life as Cognitive Info-Computation. In A. Beckmann, E. Csuhaj-Varjú, & K. Meer (Eds.), Computability in Europe 2014. LNCS (pp. 153–162). Berlin Heidelberg: Springer.

Dodig-Crnkovic, G., & Giovagnoli, R. (2013). Computing Nature. Berlin Heidelberg: Springer.

Hewitt, C. (2012). What is computation? Actor Model versus Turing’s Model. In H. Zenil (Ed.), A Computable Universe, Understanding Computation & Exploring Nature As Computation. World Scientific Publishing Company/Imperial College Press.

Kolmogorov, A. N. (1953). On the Concept of Algorithm. Russian Mathematical Surveys, 8(4), 175–176.

Landauer, R. (1996). The Physical Nature of Information. Physics Letter A, 217, 188.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungs problem. Proceedings of the London Mathematical Society, 42(42), 230–265. doi:10.1112/plms/s2-42.1.23

Zenil, H. (2012). A Computable Universe. Understanding Computation & Exploring Nature As Computation. (H. Zenil, Ed.). Singapore: World Scientific Publishing Company/Imperial College Press.