Universality and NP-Completeness in the Railways
(General Interest: First 25 minutes)

In 1994, Ian Stewart devised a railway circuit with only three kinds of switching points that is able to mimic the computation of a Turing machine. We give here a new proof of that universality result using a somewhat simpler circuit with the same kinds of switches. Both circuits, Stewart's and the author's are infinite. In finite circuits, we indicate a problem which is in NP-complete, using the same kind of switches. This explains why in today's life unexpected things sometimes happen with trains...

(Break: Second 10 minutes)

A Frontier Result on Molecular Computations
(Researcher's Interest: Last 25 minutes)

We shall first recall what molecular computations are. Then we explain what we mean by "frontier". We give an example of such a frontier result: time-varying distributed H-systems, TVDH, were devised to closer mimic natural processes that are performed according periodical cycles of operations. The degree of a TVDH is the number of operations in a cycle. The author and Yurii Rogozhin proved that starting from degree 2, it is always possible to devise TVDH's which generate any recursively enumerable language and consequently, have an unpredictable behavior, but for degree 1 this is not possible because TVDH of degree 1 generate regular languages, and so their behavior can be completely predicted.