ACM Turing Laureate Lecture Prof. Joseph Sifakis reflects "On the nature of Computing"

16 March 2017

Prof. Josep Sifakis has offered today the talk “On the nature of computing” which has been attended by around 130 people. Sifakis was recognized with the prestigious Turing award in 2007 together with Edmund M. Clarke and E. Allen Emerson for their roles in developing model checking into a highly effective verification technology, widely adopted in the hardware and software industries. This lecture has been organized jointly with FIB as part of the FIB 40th anniversary program.

In his talk, Sifakis reflects on the nature of computing analysing the following concepts that are developed below: what is information, what is computing, domain of knowledge, linking physicality of computation, and linking natural and artificial intelligence.
Computing is a domain of knowledge. Knowledge is 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; 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 systematically 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.