Università Roma Tre

1) Computability, complexity and representability:

- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of an alphabet, the notion of a formal language. Decidability and semi-decidability of a set. Deterministic, finitary and discrete computations. Formal algorithms: formal definition of algorithm, configurations of input, output, transition function. Example of formalization of an algorithm. Decidability for finished automata. Representation of the automata by matrices. Free Monoid of words. Formal semi-rings. Non-deterministic finite automata. Regular Languages. Equivalence between deterministic and non-deterministic automata.

- Turing machines: definition, decidability for Turing machine, stopping time, stopping space. Cost of computation. Complexity: worst case and average case. Independence of decision time from a finite number of input configurations. Complexity functions, complexity classes DTIME and DSPACE (deterministic time and space). Inclusion DTIME (T (n)) ⊂ DSPACE (T (n)) ⊂ DTIME (2 ^ {cT (n)}). Pumping Lemma. Simulation of algorithms, simulation of the half tape Turing machine, simulation of a multi-tape machine. Special Turing machines. Linear Speedup theorem for Turing machines with an extended alphabet. Evaluation of acceleration coefficient in relation to alphabets. Decisions of natural number sets. Independence from representation. Considerations concerning complexity.

- Turing computability: definition of Turing computable function, characteristic functions of Turing decidable sets, the class of Turing computable functions is closed by composition, concatenation, primitive recursion and minimization. Examples of Turing computable functions. Recursive Functions: equivalence between Turing computability and recursive functions. Ackermann function ([1] chapter 1,2,3,4,5 and [4] chapter 1).

- Time-constructible functions. The notion of T-clock. Examples of some time constructible function. Closure by composition.

- Non-deterministic Turing machines: characterization through the decidability of projection sets. Definition of the class of polynomial non-deterministic functions. NP-complete problems.

2) Lambda calculus and functional programming:

- Declarative programming: historical outline on the lambda calculus, basic definitions, the terms of the lambda calculus, the simple substitution. Relations on the lambda terms. Congruences, transition to the context. α-equivalence. alpha-equivalence passes to the context. Transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms with respect to alpha-equivalence.

- Definition of beta-reduction and beta-equivalence. Church-Rosser's theorem for beta-reduction. Normal forms for beta-reduction. Beta-reduction strategies. Normalizing strategy: left reduction (left most-outer most). Head reduction. Soluble Terms. Head Normal Forms. Solvability characterization theorem.

- Representation of the recursive functions: lambda definability theorem. The existence of the fixed point for any lambda term. Church Fixed Point and Curry fixed point.
- Representation of other data types in the lambda-calculus: pairs, lists, trees, the solution of recursive equations on lambda-terms ([2] chapters 1, 2, 5).

- P. Dehornoy, Calculabilite et Decidabilite, (1993) Springer-Verlag (in francese);
- J.-L. Krivine, Lambda Calculus: Types and Models, (1993) Ellis Horwood editore.
- M. Sipser, An introduction to the theory of computation (2005), Course Technology.