Postgraduate Course: Logic, Computability and Incompleteness (PHIL11114)
Course Outline
| School | School of Philosophy, Psychology and Language Sciences |
College | College of Humanities and Social Science |
| Credit level (Normal year taken) | SCQF Level 11 (Postgraduate) |
Availability | Not available to visiting students |
| SCQF Credits | 20 |
ECTS Credits | 10 |
| Summary | The course will focus on key metatheoretical results linking computability and logic.
Shared with the undergraduate course Logic, Computability and Incompleteness PHIL10133
For courses co-taught with undergraduate students and with no remaining undergraduate spaces left, a maximum of 8 MSc students can join the course. Priority will be given to MSc students who wish to take the course for credit on a first come first served basis after matriculation. |
| Course description |
In particular the course will focus on Turing machines and their formalization in first-order logic, linking uncomputability and the halting problem to undecidability of first-order logic. We will then study recursive functions and their construction, followed by first-order formalizations of arithmetic, particularly Robinson arithmetic and Peano arithmetic. We will then turn to the topic of the arithmetization of syntax and the diagonal lemma, before proceeding to prove some of the main limitative results concerning formal systems, in particular Gdel's two incompleteness theorems, and allied results employing the diagonal lemma, including Tarski's Theorem and Lb's Theorem.
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
Students MUST have passed:
Logic 1 (PHIL08004)
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | Students must have passed Logic 1 or equivalent course in their previous undergraduate studies. |
Course Delivery Information
|
| Academic year 2015/16, Available to all students (SV1)
|
Quota: 8 |
| Course Start |
Semester 2 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
200
(
Lecture Hours 20,
Feedback/Feedforward Hours 2,
Programme Level Learning and Teaching Hours 4,
Directed Learning and Independent Learning Hours
174 )
|
| Assessment (Further Info) |
Written Exam
100 %,
Coursework
0 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
The course will be assessed 100% by exam; the mark for the course will be based on this examination.
Date of exam: TBC by central university
|
| Feedback |
Guidance based on exercise sets assigned during the semester. |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- demonstrate familiarity with the general philosophical/mathematical project of Hilbert's program and how this is impacted by the technical results explored in the course
- understand some key limitative results in logic and computability, including the halting problem, the undecidability of first-order logic, and the incompleteness of first-order arithmetic
- employ abstract, analytical and problem solving skills
- formulate clear and precise pieces of mathematical reasoning
|
Reading List
Syllabus
Our primary text will be Boolos & Jeffrey's Computability and Logic. We will use the 'canonical' 3rd edition.
Topic 1: Cardinality, Enumerability, Diagonalization, B&J ch 1,2.
Topic 2: Turing Machines and Computability, B&J ch 3,6.
Topic 3: Recursive Functions, B&J ch 7,8
Topic 4: First-Order Logic Revisited, B&J ch 9.
Topic 5: Uncomputability and Undecidability, B&J ch 5,10.
Topic 6: Completeness, Compactness and Lowenheim-Skolem, B&J ch 11,12,13.
Topic 7: Formal Arithmetic, B&J ch 14.
Topic 8: Diagonal Lemma, Godel and Tarski Theorems, B&J ch 15
Topic 9: Provability Predicates and Lob's Theorem, B&J ch 16.
Topic 10: Computational Complexity
|
Additional Information
| Course URL |
Please see Learn page |
| Graduate Attributes and Skills |
Students will demonstrate the following transferable skills:
- evaluating abstract theoretical claims;
- grasping and analysing complex metatheoretical concepts;
- deploy rigorous formal methods. |
| Additional Class Delivery Information |
The course is taught by Dr Paul Schweizer |
| Keywords | Not entered |
Contacts
| Course organiser | Dr Paul Schweizer
Tel: (0131 6)50 2704
Email: paul@inf.ed.ac.uk |
Course secretary | Miss Lynsey Buchanan
Tel: (0131 6)51 5002
Email: Lynsey.Buchanan@ed.ac.uk |
|
© Copyright 2015 The University of Edinburgh - 18 January 2016 4:42 am
|
University Homepage