Models of Computation
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- Teaching methods
- Contacts/Info
The course will be self-contained as much as possible. Basic notions and results on algebra and logic, algorithms, grammars and formal languages, finite state automata, Turing Machines, as provided in first courses on Algebra, Algorithms, Formal Languages and Automata, are needed and will be briefly recalled if necessary.
The evaluation procedure consists in an oral discussion.
Final mark (out of 30) depends on the completeness and relevance (70%) and on the clarity of the exposition.
Course Objectives and Expected Outcomes
The course has a definite theoretical character. The main objective is the acquisition of the most fundamental notions regarding models of computation, both sequential and distributed/parallel. The focus of the course is on the development of student’s capability of modelling and analyzing complex systems within a formal mathematical approach. Classical sequential and parallel computation models will be presented, starting from Deterministic, Nondeterministic, Oracle and Alternating Turing Machines. In this context, classical Finite state automata will be considered as the natural description of a finite control of any computation device or program. More recent models for distributed systems/networks based on automata (weighted, timed, probabilistic).will also be considered, both synchronous and asynchronous. These topics are fundamental and indispensable to understand notions, concepts and result that every computer science student should master, as:
• Church- Turing’s Thesis and the existence of undecidable problems
• The notion of simulations among syntactic models and semantic issues
• Complexity analysis of algorithms and problems, in terms of time, space and number of processors. Intractable problems and their classifications (nondeterminism, parallelism, games)
• Communicating strategies in a distributed environment (I/O, synchronous, asynchronous, broadcasting);
• Modelling, analysis and verification of distributed complex systems; safety proprieties and the Combinatorial explosion problem
• The role of a Compositional approach in complex systems specification and verification. Automata with interfaces for modelling open systems.
Notions, concepts and techniques presented are of fundamental importance in dealing with applied problems, even if the course character is essentially theoretical. In particular, a mathematical and rigorous approach is needed when considering problems as: protocols and circuits verification, security issues in networks, planning, , computational learning, , time and probability in critical systems; .complex systems, both hardware and software.
The student is supposed to learn how to use suitable formal tools in different applied contexts, and to motivate adequately their use in specific applications, by confronting them on a solid mathematical ground.
Evaluation procedure
The evaluation procedure consists of an oral discussion.which aims to test the correct comprehension and the acquisition of the scientific material contained in the textbook; at least two questions will be formulated on this material. The student can propose a starting argument for the examination. Historical and interdisciplinary motivations and in particular practical applications for the theoretical material of the course will be questioned (at least two questions). At least one question will be on topics of recent interest presented during the lessons and not contained in the proposed textbooks, but only on the lecture slides. Final mark (out of 30) depends on the completeness and correctness of answers to specific questions (70%), the clarity of the exposition.(10%) and adequate motivation of ideas, results and scientific statements (20%).
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. Also, Oracle Turing Machines introduced the germ of an idea of machines communicating through a channel. A widely accepted formal model for networks of interacting machines and their behavior, that could be used for verification, is still missing, and only partial and unsatisfactory solution are at the present moment possible to this fundamental issue.
Topics indicated with (**) will be discussed during the lectures and are integral part of the exam, topics indicated with (*) will be possibly discussed during the lectures and could be material for individual study
• FSA as control structure of any discrete model of computation/dynamical system, and Deterministic and Oracle Turing Machines as general computing devices. (**)
• Non deterministic and Alternating Turing Machines as general models for parallel computation and their relations with the classes P, NP, PSpace; Complete problems, Games and their complexity. (**)
• Automata based models for distributed systems and their behavior, both synchronous and asynchronous: Cellular Automata, Zielonka’s Asynchronous Automata and Trace languages, (discussing their relation with Petri nets) (**)
• Weighted automata for describing timed,and probabilistic dynamical systems: Rabin automata, Markov chains (*).
• “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. (*)
• We will discuss in detail the importance of a compositional approach to the specification and verification of distributed systems/networks, starting from the fundamental result of Kleene on FSA composition. In order to extend this result, we need the notion of automata with interfaces and new operations of parallel composition, with and without communication, plus operations on communicating channels.(**)
• A mathematical description for reconfigurable networks will be given, using the formalism Span-Cospan(Graph).
• The site http://bertoni.di.unimi.it/ contains most of the material presented during the course lectures, in italian:
Recursive function theory (Calcolabilità),
Complexity and Games theory (Complessità e Teoria dei Giochi )., only partially covered
• R.F.C. Walters, Categories and Computer Science, Cambridge University Press, 1992 (in English)
Note that the course is original and the material innovative, hence, a textbook containing all the topics presented during the lessons does not exists at the present. Slides from the lectures will be collected and posted on the University site of the course; scientific papers will be suggested as possible individual learning percourse.
Lectures in Como and Varese using teleconferencing (alternate days)
Office hours will be defined at the beginning of the course and communicated to the Secretary’ s Office. It will always be possible to contact directly the professor via email in order to obtain an appointment at different hours.
Professors
Borrowers
-
Degree course in:
-
Degree course in: MATHEMATICS
-
Degree course in: MATHEMATICS