Any algorithm is given through the description of its control structure and the data structure on which instruction operates. Hence, corner stones of classical computer science are the notion of Finite state automaton (FSA), describing precisely the control structure of any sequential program or, more generally, of any state/ transition discrete dynamical system, and of Turing Machine ( Finite state automaton enriched by the capability of modifying data), considered the general model of computation (according to the Curch-Turing Thesis). Both these models are very natural with respect to sequential computations, but they represent non sequential systems and parallel or distributed computations, where more machines interact during their computation, only by considering a (weaker) notion of nondeterminism.
Surprisingly, since the beginning FSA have been associated with networks, where a single node is a classical automaton: the seminal paper of McCulloch and Pitts introduced FSA as a formal model of neurons, aiming at modeling neuron networks. Von Neumann extended these approach by introducing Cellular automata in order to model synchronous networks with fixed topology. A widely accepted formal model for networks of interacting machines and their behavior, that could be used for verification, is still missing.
Topics indicated with (*) will be discussed during the lectures and are integral part of the exam, topics indicated with (**) may be discussed during the lectures and could be material for individual study.
In details (the hours are indicative):
- Preliminaries: strings, languages, operations, free monoid, languages/characteristic functions/sets (3h) (*)
- Finite representation of languages, Cantor's results, Hilbert and undecidability (3h) (*)
- Deterministic and Oracle Turing Machines as general computing devices. (3h) (*)
- Universal T.M., interpreter, compiler, Halting Problem (4h) (*)
- Recursive and recursively enumerable sets , examples, software correctness, discussion (4h) (*)
- Non deterministic and Alternating T. M. as general models for parallel computation, simulations, examples and classical problems (3h) (*)
- Time and space complexity for algorithms, problems, T.M (3h) (*)
- Complexity theory, classes P, NP, P Space, NC; Complete problems, Cook's theorem, examples of complete problems , applications (8h) (*)
- Games and their complexity. (2h)(**)
- Other classical formalisms: Ram language, While language, compilers, Partially Recursive Functions, Turing equivalence, Church Turing Thesis (8h) (*)
- Smn, Recursion , Rice Theorems (4h) (*)
- Beyond the Church-Turing thesis: discussion (2h) (**)
- Grammars and the Chomsky Hierarchy, regular and context free languages, applications (4h) (*)
- Membership problem for classes of problems with application to parsing (4h) (*)
- Finite state automata and their role in modeling discrete sequential systems, basic properties and examples (3h) (*)
- Compositionality and Kleene's theorem. (4h) (*)
- Nerode's Theorem (2h) (*)
- Automata based models for distributed systems and their behavior, both synchronous and asynchronous: Cellular Automata, Zielonka’s Asynchronous Automata and Trace languages, Petri nets (12h) (*)
- Weighted automata for describing timed,and probabilistic dynamical systems: Rabin automata, Markov chains (2h) (**).
- “Concurrent”and biological system models based on term rewriting and regular expressions: Lindenmayer systems, Milner ‘s CCS and various process algebras. Statecharts as hierarchical systems. (6h) (**)
- Span-Cospan: a compositional approach to the specification and verification of distributed systems/networks (2h)(**)