Unconventional Models of Computation

Prof. Alberto Leporati, Prof. Alberto Dennunzio

University of Milano-Bicocca, Milano, Italy

The course will cover three “unconventional” models of computation, inspired from Nature: membrane systems, cellular automata, and quantum computers. We will be interested in studying their computational properties (i.e., computational power and computational efficiency), using techniques from Theory of Computing and Computational Complexity.

Membrane Systems, also called P systems, are a distributed, parallel, synchronized model of computation inspired from the functioning of living cells. After exposing the operation of some variants of P systems, I will address two kinds of problems:

  • computability problems: is the model under examination equivalent in power to Turing machines? If not, what can be computed (and what cannot be computed) by this model? What are the computational features that make this model Turing-complete (and that, removed, make it less powerful than Turing machines)? We will answer these questions mainly through simulations: simulation of Turing machines, simulation of register machines, simulation of Petri nets (or place/transition nets);
  • efficiency problems: is this model able to solve in polynomial time NP-complete or NP-hard or PSPACE-complete (or even more difficult) problems? What kinds of problems can be solved using a polynomial/logarithmic/constant amount of space?

Cellular automata are another Nature-inspired parallel model of computation. In this case, after giving the basic notions and definitions, I will show some applications of cellular automata to cryptography: in particular, the design of secure pseudo-random number generators, and the design of secret sharing schemes.

Finally, I will give an introduction to Quantum Computing (in particular, quantum circuits), a discipline that investigates models of computation inspired from the laws of Physics. After giving some basic notions, I will explain how quantum superposition and entanglement can be used to solve in an efficient way problems that cannot be solved efficiently by classical computers. I will then present the “killer applications” of quantum computers, namely, Shor’s algorithms for the factorization of integer numbers and for computing discrete logarithms.

All the required notions will be explained/recalled during the course: Turing machines, register machines, complexity classes, basic notions of cryptography, etc.

The exam will consist in a written report or in a presentation (with PowerPoint or PDF slides) concerning a topic agreed with me. At your will, exploration of new research problems will also be possible.


Tuesday, 30 May 2017, from 10:00 to 12:00, U14, first floor, room 1030
Thursday, 1 June 2017, from 10:00 to 12:00, U14, first floor, room 1030
from Wednesday 7 to Friday 9 June 2017: Selected lectures from the conference Automata 2017 (proposed: 4 hours, see below)
Tuesday, 20 June 2017, from 10:00 to 12:00, U14, first floor, room 1030
Friday, 23 June 2017, from 10:00 to 12:00, U14, first floor, room 1030
Tuesday, 27 June 2017, from 10:00 to 12:00, U14, first floor, Meeting room (next to Seminar room)
Thursday, 29 June 2017, from 10:00 to 12:00, U14, first floor, U14, first floor, room 1030
Tuesday, 4 July 2017, from 10:00 to 12:00, U14, first floor, U14, first floor, room 1030
Thursday, 6 July 2017, from 10:00 to 12:00, U14, first floor, U14, first floor, room 1030

The eligible lectures from the Automata 2017 conference (https://automata2017.disco.unimib.it/) are the following (and you are requested to attend at least 4 hours, by choosing among the talks at your will):

Wednesday 7/6
9:30 — 10:30: Invited Talk 1 (Eric Goles): Two Dimensional Cellular Automata and Computational Complexity

14:00 — 15:30: Full papers session
14:00 — 14:30: Eric Goles, Diego Maldonado, Pedro Montealegre and Nicolas Ollinger: On the computational complexity of the freezing non-strict majority automata
14:30 — 15:00: Nazim Fatès: A note on phase transitions and symmetry breakings in stochastic mixtures of two Elementary Cellular Automata
15:00 — 15:30: Tatsuya Yamashita, Teijiro Isokawa, Ferdinand Peper, Ibuki Kawamata and Masami Hagiya: Turing-Completeness of Asynchronous Non-Camouflage Cellular Automata

Thursday 8/6
9:30 — 10:30: Invited Talk 2 (Adrien Richard): Fixed points in Boolean networks

14:00 — 15:00: Full papers session
14:00 — 14:30: Luca Mariot, Enrico Formenti and Alberto Leporati: Enumerating Orthogonal Latin Squares Generated by Bipermutive Cellular Automata
14:30 — 15:00: Alonso Castillo-Ramirez and Maximilien Gadouleau: Von Neumann Regular Cellular Automata

Friday 9/6
9:30 — 10:30: Invited Talk 3 (Ville Salo): Strict asymptotic nilpotency in cellular automata