The course aims to provide an introduction to computability theory.

It will be divided into two parts: a general part, which includes a review of logic and an introduction to computation theory; and a special part, which will focus in particular on the study of the works of Alan M. Turing.

1. Algorithms
1.1 What is an algorithm
1.2 Flowcharts
1.3 Algorithms that sometimes do not produce results
1.4 Natural numbers and data encoding

2. Mathematical Functions and Algorithms
2.1 The mathematical concept of function
2.2 Functions computed by algorithms
2.3 Functions and decision algorithms
2.4 Total and partial functions
2.5 Arithmetic functions and encodings
2.6 Non-computability and undecidability: a preview

3. Turing Machines
3.1 Toward a rigorous notion of algorithm
3.2 Alan Turing’s model of computation
3.3 Machines that compute arithmetic functions
3.4 Machines that do not halt

4. Recursive Functions
4.1 Introduction
4.2 Operations on functions: composition and recursion
4.3 The class of primitive recursive functions
4.4 Computability of primitive recursive functions
4.5 Computable functions that are not primitive recursive
4.6 The class of general recursive functions
4.7 Total general recursive functions

5. Church’s Thesis and Undecidable Problems
5.1 Church’s Thesis
5.2 Church’s Thesis and parallel computation
5.3 The Universal Turing Machine
5.4 The existence of undecidable problems

6. Computability and the Foundations of Mathematics
6.1 The evolution of the axiomatic method
6.2 Church’s and Gödel’s theorems

7. Computability, Computer Science, and the Study of the Mind
7.1 Stored-program architecture and von Neumann machines
7.2 Computational complexity
7.3 Mind, computation, and cognitive science

8. Reading and Analysis of Selected Texts by Alan M. Turing

The course requires a basic knowledge of logic.

Participation in the Training Camp is highly recommended (info: Anya Pellegrin): https://filosofia.uniurb.it/training-camp/

Knowledge and Understanding
By the end of the course, students should be able to understand and explain selected texts from the history of logic and its computational applications. They should be familiar with and able to discuss some of the classic problems in computation theory, as well as use key bibliographic and informational tools relevant to the field.

Applying Knowledge and Understanding
By the end of the course, students should be able to critically discuss and evaluate the main arguments and theses in the field of computation theory, and apply this knowledge to the analysis of contemporary debates on the subject.

Making Judgements
By the end of the course, students should demonstrate independent judgment regarding the main topics covered. Class discussion will be encouraged to support this goal. In the assessment process, the ability to personally rework and interpret the acquired knowledge will be particularly valued.

Communication Skills
By the end of the course, students should be able to present and discuss the studied topics with conceptual and linguistic accuracy, and to outline general frameworks that effectively and concisely illustrate the issues addressed. To this end, classroom interaction, along with careful reading and close analysis of reference texts, will play an important role.

Learning Skills
By the end of the course, students should have gained familiarity with the subject matter and with research methods in the field, enabling them to independently acquire new knowledge by consulting major bibliographic tools in this and related areas.

The teaching material prepared by the lecturer in addition to recommended textbooks (such as for instance slides, lecture notes, exercises, bibliography) and communications from the lecturer specific to the course can be found inside the Moodle platform › blended.uniurb.it

Lectures:

Training Camp: https://filosofia.uniurb.it/training-camp/

Synergia Lectures: https://sites.google.com/a/uniurb.it/synergia

Lectiones Commandinianae: https://sites.google.com/site/lectionescommandinianae/

Teaching

The teaching is delivered in mixed mode, i.e., the lectures take place in the classroom and are simultaneously transmitted remotely within the Moodle platform.

Classroom lectures offer general frameworks, analyses of particular topics and exercises, and comments on the relevant literature. Students are encouraged to ask questions, comment, and discuss things before, during, and after the lecture. Of course, personal study at home will be equally important.

Innovative teaching methods

As part of the innovative teaching approach to logic, targeted e-tivities will be organized to foster critical and argumentative thinking through interactive online activities. Students will engage in guided exercises, discussions, and collaborative problem solving to strengthen their deductive reasoning skills.

Attendance

Students should attend classes regularly and actively, since the very beginning. Because of the analytic and often abstract character of the subject matter, active participation in classroom discussion will be very useful. In order to do that, and in general to follow the lectures successfully, it is strongly advised to do every day the homework suggested as preparation for the following lecture.

Course books

Richard L. Epstein, “An Introduction to Formal Logic”, Advanced Reasoning Forum, 2016.

De Mol, Liesbeth, "Turing Machines", The Stanford Encyclopedia of Philosophy (Summer 2025 Edition), Edward N. Zalta & Uri Nodelman (eds.), forthcoming URL = <https://plato.stanford.edu/archives/sum2025/entries/turing-machine/>.

Oppy, Graham and David Dowe, "The Turing Test", The Stanford Encyclopedia of Philosophy (Winter 2021 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2021/entries/turing-test/>.

Copeland B. Jack, "The Modern History of Computing", The Stanford Encyclopedia of Philosophy, 2008, <https://plato.stanford.edu/archIves/sum2004/entries/computing-history/>.

Additional texts will be given to students during the lectures (the additional texts will also be available on the Moodle platform › blended.uniurb.it).

Assessment

Written and oral examination. You will be asked to analyze concepts, solve exercises, and demonstrate theorems.
This dual mode makes it possible to assess, in the best way, the achievement of the established formative objectives and competencies.
The final evaluation will consider the student's knowledge in terms of analysis of concepts, definitions, theorems, problems, theories, techniques, methods, scientific instruments, etc. The student's ability to use conceptual tools to solve problems and prove/analyze theorems and active participation in the classroom will also contribute to the final evaluation. Finally, the student's capacity for rigorous analysis of themes and problems, autonomy in solving problems and proving theorems, personal and autonomous reworking of knowledge, and planning will be particularly well-appreciated.

All these elements will have equal weight in the assessment. They will be distinguished on a scale of four levels (not sufficient, sufficient, good, excellent).
The final mark will be expressed in a range from 18/30 to 30/30. A sufficiently rigorous and clear exposition -using adequately specific terms- of the basic contents, concepts, methods, and the ability to solve simple exercises and prove simple theorems will be enough to obtain a sufficient evaluation and to pass the examination (18/30). The other marks will be calibrated on this basis.

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.

Teaching

Students will study on their own (individually or with others) according to the directions of this vademecum and, if possible, with the help that the teacher can give during office hours or through e-mail, Zoom, etc.

Attendance

In order to make up for the impossibility of attending classes, a hard and careful study is required. One should already possess good skills of autonomous learning and some capacity to read and understand logic and philosophical texts, at least at a basic level. Whenever possible, it is advisable to work with other students. 

Course books

Richard L. Epstein, “An Introduction to Formal Logic,” Advanced Reasoning Forum, 2016.

De Mol, Liesbeth, "Turing Machines", The Stanford Encyclopedia of Philosophy (Summer 2025 Edition), Edward N. Zalta & Uri Nodelman (eds.), forthcoming URL = <https://plato.stanford.edu/archives/sum2025/entries/turing-machine/>.

Oppy, Graham and David Dowe, "The Turing Test", The Stanford Encyclopedia of Philosophy (Winter 2021 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2021/entries/turing-test/>.

Copeland B. Jack, "The Modern History of Computing", The Stanford Encyclopedia of Philosophy, 2008, <https://plato.stanford.edu/archIves/sum2004/entries/computing-history/>.

Additional texts will be given to students during the lectures (the additional texts will also be available on the Moodle platform › blended.uniurb.it).

Non-attending students are invited to contact the professor with regard to the additional texts.

Assessment

Written and oral examination. You will be asked to analyze concepts, solve exercises, and demonstrate theorems.
This dual mode makes it possible to assess, in the best way, the achievement of the established formative objectives and competencies.
The final evaluation will consider the student's knowledge in terms of analysis of concepts, definitions, theorems, problems, theories, techniques, methods, scientific instruments, etc. The student's ability to use conceptual tools to solve problems and prove/analyze theorems will also contribute to the final evaluation. Finally, the student's capacity for rigorous analysis of themes and problems, autonomy in solving problems and proving theorems, personal and autonomous reworking of knowledge, and planning will be particularly well-appreciated.

All these elements will have equal weight in the assessment. They will be distinguished on a scale of four levels (not sufficient, sufficient, good, excellent).
The final mark will be expressed in a range from 18/30 to 30/30. A sufficiently rigorous and clear exposition -using adequately specific terms- of the basic contents, concepts, methods, and the ability to solve simple exercises and prove simple theorems will be enough to obtain a sufficient evaluation and to pass the examination (18/30). The other marks will be calibrated on this basis.

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.

Foreign students will be allowed to use English for questions and comments during the class, for all the required readings, and the final examination.