Improve the understanding of the mathematical aspects of the notion of computation, and study the relationships between different computational models and the computational complexity.
Curriculum
teacher profile teaching materials
- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Programme
1) Computability, complexity and representability:- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
Core Documentation
[1] DEHORNOY, P., COMPLEXITÈ ET DECIDABILITÈ. SPRINGER-VERLAG, (1993).[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Reference Bibliography
G. Lolli, Hilbert e la logica, Le Matematiche, [S.l.], v. 55, n. 3, p. 93-126, mar. 2005. ISSN 2037-5298. Dexter C. Kozen, Theory of Computation, Springer-Verlag (2006). G. Ausiello, G. Gambosi, F. d'Amore Linguaggi, Modelli, Complessità Aho, Hopcroft, Ullman, Design and Analysis of Computer Programming. A. Bernasconi, B. Codenotti, Introduzione alla complessità computazionale, Springer-Verlag. H. Hermes, Enumerability, Decidability, Computability, Die Grundlehren der Mathematichen Wissenshaften in Einzeldarstellungen, n. 127, Springer-Verlag. F. Cardone and J. R. Hindley, History of Lambda-calculus and Combinatory Logic, from Swansea University Mathematics Department Research Report No. MRRS-05-06.Type of delivery of the course
Lectures.Attendance
Optional.Type of evaluation
The exam consists of two parts: a written exam, that can be replaced with a mid-term exam and a final partial exam (final evaluation will be computed by weighting at 35% the mid-term exam and 65% the final exam) and an oral examination, either to compensate for an insufficient written exam (starting at 15 points), either to improve a sufficient written exam. teacher profile teaching materials
- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Mutuazione: 20410417 IN410-CALCOLABILITÀ E COMPLESSITÀ in Scienze Computazionali LM-40 PEDICINI MARCO
Programme
1) Computability, complexity and representability:- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
Core Documentation
[1] DEHORNOY, P., COMPLEXITÈ ET DECIDABILITÈ. SPRINGER-VERLAG, (1993).[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Reference Bibliography
G. Lolli, Hilbert e la logica, Le Matematiche, [S.l.], v. 55, n. 3, p. 93-126, mar. 2005. ISSN 2037-5298. Dexter C. Kozen, Theory of Computation, Springer-Verlag (2006). G. Ausiello, G. Gambosi, F. d'Amore Linguaggi, Modelli, Complessità Aho, Hopcroft, Ullman, Design and Analysis of Computer Programming. A. Bernasconi, B. Codenotti, Introduzione alla complessità computazionale, Springer-Verlag. H. Hermes, Enumerability, Decidability, Computability, Die Grundlehren der Mathematichen Wissenshaften in Einzeldarstellungen, n. 127, Springer-Verlag. F. Cardone and J. R. Hindley, History of Lambda-calculus and Combinatory Logic, from Swansea University Mathematics Department Research Report No. MRRS-05-06.Type of delivery of the course
Lectures.Attendance
Optional.Type of evaluation
The exam consists of two parts: a written exam, that can be replaced with a mid-term exam and a final partial exam (final evaluation will be computed by weighting at 35% the mid-term exam and 65% the final exam) and an oral examination, either to compensate for an insufficient written exam (starting at 15 points), either to improve a sufficient written exam. teacher profile teaching materials
- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Programme
1) Computability, complexity and representability:- Introduction to decision problems, algorithmic and non-algorithmic procedures, deterministic computations, discrete procedures, the notion of alphabet, of speech. 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: a 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. The transitive closure of a relationship, owned by Church-Rosser. Listing of lambda-terms concerning 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. Existence of the fixed point for the lambda terms. 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).
Core Documentation
[1] DEHORNOY, P., COMPLEXITÈ ET DECIDABILITÈ. SPRINGER-VERLAG, (1993).[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
Reference Bibliography
G. Lolli, Hilbert e la logica, Le Matematiche, [S.l.], v. 55, n. 3, p. 93-126, mar. 2005. ISSN 2037-5298. Dexter C. Kozen, Theory of Computation, Springer-Verlag (2006). G. Ausiello, G. Gambosi, F. d'Amore Linguaggi, Modelli, Complessità Aho, Hopcroft, Ullman, Design and Analysis of Computer Programming. A. Bernasconi, B. Codenotti, Introduzione alla complessità computazionale, Springer-Verlag. H. Hermes, Enumerability, Decidability, Computability, Die Grundlehren der Mathematichen Wissenshaften in Einzeldarstellungen, n. 127, Springer-Verlag. F. Cardone and J. R. Hindley, History of Lambda-calculus and Combinatory Logic, from Swansea University Mathematics Department Research Report No. MRRS-05-06.Type of delivery of the course
Lectures.Attendance
Optional.Type of evaluation
The exam consists of two parts: a written exam, that can be replaced with a mid-term exam and a final partial exam (final evaluation will be computed by weighting at 35% the mid-term exam and 65% the final exam) and an oral examination, either to compensate for an insufficient written exam (starting at 15 points), either to improve a sufficient written exam.