Faculty of Computer Science

Master of Science in Computer Science

European Master in Computational Logic

Theory of Computing

**11/01/2018**: The lecture notes for Part 7 are available.**11/01/2018**: The lecture notes for Exercises 9 and 10 are available.

- for the Principles of Computation Course (Theory of Computing module) within the European Master in Computational Logic
- for the Theory of Computing Course within the Data and Knowledge Engineering stream of the MSc in Computer Science

[M1]Introduction to Automata Theory, Languages, and Computation (3rd edition).J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.

[M2]Lecture Notes for Theory of Computing. Diego Calvanese. 2013. Available as scanned pages in pdf.

[M3]Languages and Machines (3rd edition).Thomas A. Sudkamp. Addison Wesley, 2005. Only Chapter 13.

[M4]The Convenience of Tilings.Peter van Emde Boas. InComplexity, Logic, and Recursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, pages 331-363, 1997.

[M5]Exercises on Theory of Computing. Available as scanned pages in pdf.

*Elements of the Theory of Computation (2nd edition).*H.R. Lewis, C.H. Papadimitriou. Prentice Hall. 1998.*Introduction to the Theory of Computation.*M. Sipser. PWS Publishing Company. 1997.*Computational Complexity.*C.H. Papadimitriou. Addison Wesley. 1995.*The Universal Computer: The Road from Leibniz to Turing.*M. Davis. A K Peters/CRC Press. 2011. Full text accessible to all unibz users at Safari Books Online.*The Church-Turing Thesis.*Copeland, B. Jack. The Stanford Encyclopedia of Philosophy. Fall 2008 Edition.*The Status of the P versus NP Problem.*Lance Fortnow. Communications of the ACM. Vol. 52 No. 9, Pages 78-86, September 2009. pdf*On P, NP, and Computational Complexity.*Moshe Y. Vardi. Communications of the ACM. Vol. 53 No. 11, Page 5, November 2010. pdf*Solving the Unsolvable.*Moshe Y. Vardi. Communications of the ACM. Vol. 54 No. 7, Page 5, July 2011. pdf*Who Begat Computing?*Moshe Y. Vardi. Communications of the ACM. Vol. 56 No. 1, Page 5, January 2013. pdf*Would Turing Have Won the Turing Award?*Moshe Y. Vardi. Communications of the ACM. Vol. 60 No. 11, Page 7, November 2017. pdf*What is an Algorithm?*Moshe Y. Vardi. Communications of the ACM. Vol. 55 No. 3, Page 5, March 2012. pdf*What Is an Algorithm?*Yuri Gurevich. In Proc. of the 38th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012). Springer LNCS Vol. 7147, Pages 31-42, 2012. pdf*On founding the theory of algorithms.*Yiannis N. Moschovakis. In Truth in Mathematics. Clarendon Press, Oxford, Pages 71-104, 1998. pdf*An Interview with Stephen A. Cook.*Philip L. Frana. Communications of the ACM. Vol. 55 No. 1, Pages 41-46, January 2012. pdf*Rosser's Theorem via Turing machines.*Scott Aaronson. Shtetl-Optimized - The Blog of Scott Aaronson. 21 July 2011

- Andrew Hodges Alan Turing Home Page.
- For info on simple Turing Machines with complex behaviour, consult the web pages on Busy Beavers by the following people: Heiner Marxen, Michael Somos, and Pascal Michel.
- A Universal Turing Machine with just 2 states and 3 symbols. Read more at http://www.wolframprize.org/.
- Lego Turing Machines: a version built in 2009 and one built in 2012.
- A Turing Machine in the classic style.
- The original 1971 paper by Steve Cook showing NP-completeness of SAT and 3SAT (put into TeX format by Tim Rohlfs).
- The P-versus-NP page, collecting links around papers that try to settle the "P versus NP" question (in either way).
- Video of a talk on What's all this about P not equaling NP?.

**Office hours**- Teaching assistant: there is no teaching assistant for this course. The exercise hours are taught by the lecturer.
- Schedule: The course is taught in the 1st semester: from October 4,
2017 to January 17, 2018.
**Lectures**(Lecture Room E223, Sernesi E):- Tuesday 8:30-10:30
- Wednesday 8:30-10:30

**Exercises**(Lecture Room E220, usually): Tuesday 14:00-16:00

**Additional teaching material**- Lecture notes (made available during the course)
- Esercises solved in class (made available during the course)
- Course program
- Exam esercises from the last years (in
part with solutions).

Note that Part 1 of the exams up to June 2007 deals with topics that are not covered anymore in this course. Also, Part 2 of some exams contains exercises on circuit complexity, which is currently not part of the course program, and has been substituted by the part on tiling problems.

**Exam dates**- Midterm: end of November (precise date to be announced)
- Winter session: Tuesday, 12/2/2018, 14:00-18:00
- Summer session: Monday, 18/6/2018, 14:00-18:00
- Autumn session: Tuesday, 18/9/2018, 8:30-12:30

**Rules for the exam**- At the exam, the student has to solve exercises and/or answer questions on the course topics in written or oral form.
- The exam is divided into two parts:
- Part 1 covers topics 1-4 of the course program;
- Part 2 covers topics 5-8 of the course program.

- The two parts of the exam can be taken together in the same exam session, or separately in different exam sessions.
- Even when the two parts of the exam are taken together, they can be passed separately.
- For a part to be passed, a minimum of 18/30 points is required (half marks are rounded upwards).
- A passed part of the exam (or the passed midterm) is valid until the end of the academic year (i.e., exam session of September). If the other part is not passed by then, the passed part is lost and cannot be carried over to the next academic year.
- For the written exam, each part has a duration of 90 minutes, with 15
minutes break between the two parts. During the exam, it
will
**not**be possible to consult any kind of material, to use laptops, smartphones, or tablets, or to leave the exam room before the break/end of the exam.

teaching page of Diego Calvanese