ERCIM News 91
October 2012
Special theme What is Computation - Alain Turing’s Legacy
Guest editors Gilles Dowek (Inria) and Samson Abramsky (University of Oxford)
PDF
of ERCIM News 91
40 pages
- Details
- Category: Special Theme
- Hits: 15150
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.
- Details
- Category: Special Theme
- Hits: 13929
by Jean-Yves Marion
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.
- Details
- Category: Special Theme
- Hits: 12702
by Jos Baeten, Bas Luttik and Paul van Tilburg
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.
- Details
- Category: Special Theme
- Hits: 11678
by Claudio Angione, Pietro Liò and Giuseppe Nicosia
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.
- Details
- Category: Special Theme
- Hits: 12921
by Benjamin Grégoire
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.
- Details
- Category: Special Theme
- Hits: 14307
by Nadia Pisanti
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.
>- Details
- Category: Special Theme
- Hits: 17941
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.