Heidelberg Lecture: Joseph Sifakis, recipient of the ACM A.M. Turing Award 2007

On the Nature of Computing

Category: Lectures

Date: 28 June 2017

Duration: 59 min

Quality: HD MD SD

Heidelberg Lecture: Joseph Sifakis, recipient of the ACM A.M. Turing Award 2007 (2017) - On the Nature of Computing


Computing is a domain of knowledge. Knowledge is truthful information that embedded into the right network of conceptual interrelations can be used to understand a subject or solve a problem. According to this definition, Physics, Biology but also Mathematics, Engineering, Social Sciences and Cooking are all domains of knowledge. This definition encompasses both, scientific knowledge about physical phenomena and engineering knowledge applied to design and build artefacts. For all domains of knowledge, Mathematics and Logic provide the models and their underlying laws; they formalize a priori knowledge which is independent of experience. Computing with Physics and Biology is a basic domain of knowledge. In contrast to the other basic domains, it is rooted in a priori knowledge and deals with the study of information processing – both what can be computed and how to compute it.

To understand and master the world, domains of knowledge share two common methodological principles. They use abstraction hierarchies to cope with scale problems. To cope with complexity, they use modularity. We point out similarities and differences in the application of these two methodological principles and discuss inherent limitations common to all domains.
In particular, we attempt a comparison between natural systems and computing systems by addressing two issues: 1) Linking physicality and computation; 2) Linking natural and artificial intelligence.

Computing and Physical Sciences share a common objective: the study of dynamic systems. A big difference is that physical systems are inherently synchronous. They cannot be studied without reference to time-space while models of computation ignore physical time and resources. Physical systems are driven by uniform laws while computing systems are driven by laws enforced by their designers. Another important difference lies in the discrete nature of Computing that limits its ability to fully capture physical phenomena. Linking physicality and computation is at the core of the emerging Cyber physical systems discipline. We discuss limitations in bridging the gap between physical and discrete computational phenomena, stemming from the identified differences.

Living organisms intimately combine intertwined physical and computational phenomena that have a deep impact on their development and evolution. They share common characteristics with computing systems such as the use of memory and languages. Compared to conscious thinking, computers are much faster and more precise. This confers computers the ability to successfully compete with humans in solving problems that involve the exploration of large spaces of solutions or the combination of predefined knowledge e.g. AlphaGo's recent winning performance. We consider that Intelligence is the ability to formalize human knowledge and create knowledge by applying rules of reasoning. Under this definition, a first limitation stems from our apparent inability to formalize natural languages and create models for reasoning about the world. A second limitation comes from the fact that computers cannot discover induction hypotheses as a consequence of Gödel's incompleteness theorems.

We conclude by arguing that Computing drastically contributes to the development of knowledge through cross-fertilization with other domains as well as enhanced predictability and designability. In particular, it complements and enriches our understanding of the world with a constructive and computational view different from the declarative and analytic adopted by physical sciences.