PhD in Computer Science

PhD course on "“Intensionality and extensionality in computational systems”

2-30 July 2020

Series to which this belongs

33° ciclo
34° ciclo
35° ciclo


The main tradition of theory of computation has been concerned with extensional aspects of computation, i.e., with properties of programs reduced to the functions that they implement: Two programs are extensionally equivalent if they produce the same outputs on the same inputs. Theory of computation thus studies extensional properties of programs, which cannot tell apart any pair of extensionally equivalent programs. Much less is known about the intensional properties of programs, which distinguish different algorithms for computing the same function, different descriptions in programming languages, or different executions. The intensional side of computation includes everything that happens after the input data are read, and before the output data are written: All states and state changes, how many steps are made, or how much memory is used or how much energy is consumed. Besides the objective properties such as program complexity, the intensional properties include relations of programs with programmers, such as understandability and quality; or with other programs, such as optimising compilers, static analysers, software debuggers.
The course is intended to present the main (open) problems and results related to the extension of standard computability theory with metrics that estimate the intensional quality of computational artefacts: complexity, SW quality, understandability.


  • pdf   Flyer   (pdf, it, 169 KB, 27/05/20)