by Gilles Dowek and Samson Abramsky

This Turing centenary marks a point at which we can realize that Alan Turing has become, with the passage of time, a scientific icon whose name is known by people in many countries world-wide, and far beyond the scientific community. This may seem a paradox because the genesis of computability theory, for which Turing is probably best known, was a collective effort, to which the names of Herbrand, Gödel, Church, Post, Kleene, Rosser and Turing are often associated.

Cohen and his supervisor Adleman defined a virus as follows: “A virus is a program that is able to infect other programs by modifying them to include a possibly evolved copy to itself”. This definition seems to be well accepted by the computer security community as a foundational definition. Thus, a virus is a self-replicating program, whose offspring may be a mutation of the original program. Viruses thrive in our computers, which are based on Turing’s model of computation. We discuss the fundamental reasons for this.

At CWI and Eindhoven University of Technology in the Netherlands, we enhanced the notion of a computation in the classical theory of computing with the notion of interaction from concurrency theory. In this way, we adapted a Turing machine as a model of computation to a Reactive Turing Machine that is an abstract model of a computer as it is used nowadays, always interacting with the user and the world.

An enzyme can be thought of as a computational element, i.e. a processing unit able to transform an input into an output signal. Thus, in a biochemical pathway, an enzyme reads the amount of reactants (substrates) and converts them into products. Here we consider the biochemical pathway in unicellular organisms (e.g. bacteria) as a living computer that can be programmed to obtain the desired output. Through an optimal executable code stored in the “memory” of bacteria, we can simultaneously maximize the concentration of two or more metabolites of interest.

Combining program generation and formal proof verification, we are now able to discover new cryptographic systems and prove their resistance to many classes of attacks.

What do a leopard skin and a sunflower head have in common? Very little, should they not both exhibit patterns whose generation is the result of the interaction of components, the morphogens, according to mathematical laws described sixty years ago by Alan Turing.

Anna Gambin, Anna Marciniak-Czochra and Damian Niwinski

Alan Turing’s achievements in the theory of computation led to his recognition as the father of modern computer science. The most prestigious award in the field is named after him. He is also widely recognized in cryptography for his work on “Cryptology bombs” - code-breaking machines that were used by the Allies during the Battle of the Atlantic. Turing’s fascination with the process of thinking has led to the formulation of the definition of an abstract computing machine. By proposing a test to measure the machine’s ability to exhibit human-like cognition and consciousness he initiated the field of artificial intelligence. It is less well known that he spent the last few years of his life developing mathematical theories to describe biological processes.