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

This time we are honored to present a lecture by Prof. Joseph Sifakis, who 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. Prof. Sifakis´ talk is titled On the Nature of Computing and it is open to everyone. This lecture is organized jointly with FIB as part of the FIB 40th anniversary program.

Date: 16/Mar/2017 Time: 11:00

Primary tabs

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.


Joseph Sifakis is Emeritus Senior CNRS Researcher at Verimag. His current research interests cover fundamental and applied aspects of embedded systems design. The main focus of his work is on the formalization of system design as a process leading from given requirements to
trustworthy, optimized and correct-by-construction implementations.
Joseph Sifakis has been a full professor at Ecole Polytechnique Fédérale de Lausanne (EPFL) for the period 2011-2016. He is the founder of the Verimag laboratory in Grenoble, which he directed for 13 years. Verimag is a leading research laboratory in the area of embedded systems, internationally known for the development of the Lustre synchronous language used by the SCADE tool for the design of safety-critical avionics and space applications.
In 2007, Joseph Sifakis has received the Turing Award for his contribution to the theory and application of model checking, the most widely used system verification technique today. Joseph Sifakis has had numerous administrative and managerial responsibilities both at French and European level. He has actively worked to reinvigorate European research in embedded systems as the scientific coordinator of the « ARTIST » European Networks of Excellence, for ten years. He has participated in many major industrial projects led by companies such as Airbus, EADS, France Telecom, Astrium, and STMicroelectronics. Joseph Sifakis is a member of the French Academy of Sciences, a member of the French National Academy of Engineering, a member of Academia Europea, a member of the American Academy of Arts and Sciences, and a member of the National Academy of Engineering. He is a Grand Officer of the French National Order of Merit, a Commander of the French Legion of Honor. He has received the Leonardo da Vinci Medal in 2012. Joseph Sifakis has received in 2009 the Award of the Hellenic Parliament Foundation for Parliamentarism and Democracy. He is a commander of the Greek Order of the Phoenix. He has been the President of the Greek Council for Research and Technology for the period February 2014 – April 2016.