THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2013/2014 -
- ARCHIVE as at 1 September 2013 for reference only
THIS PAGE IS OUT OF DATE

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Philosophy, Psychology and Language Sciences : Philosophy

Undergraduate Course: Logic, Computability and Incompleteness (PHIL10133)

Course Outline
SchoolSchool of Philosophy, Psychology and Language Sciences CollegeCollege of Humanities and Social Science
Course typeStandard AvailabilityAvailable to all students
Credit level (Normal year taken)SCQF Level 10 (Year 3 Undergraduate) Credits20
Home subject areaPhilosophy Other subject areaNone
Course website None Taught in Gaelic?No
Course descriptionThis course will focus on key metatheoretical results linking computability and logic. In particular, 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, along with 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: Mind, Matter and Language (PHIL08014) AND Knowledge and Reality (PHIL08017) AND Logic 1 (PHIL08004)
Co-requisites
Prohibited Combinations Other requirements Students studying Mathematics and/or Informatics may be able to take this course without the pre-requisites; this must be discussed with the Course Organiser who can give the necessary permission.
Additional Costs None
Information for Visiting Students
Pre-requisitesPasses in second level courses in Philosophy
Displayed in Visiting Students Prospectus?Yes
Course Delivery Information
Delivery period: 2013/14 Semester 2, Available to all students (SV1) Learn enabled:  Yes Quota:  25
Web Timetable Web Timetable
Course Start Date 13/01/2014
Breakdown of Learning and Teaching activities (Further Info) Total Hours: 200 ( Seminar/Tutorial Hours 22, Programme Level Learning and Teaching Hours 4, Directed Learning and Independent Learning Hours 174 )
Additional Notes
Breakdown of Assessment Methods (Further Info) Written Exam 100 %, Coursework 0 %, Practical Exam 0 %
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S2 (April/May) Logic, Computability and Incompleteness2:00
Delivery period: 2013/14 Semester 2, Part-year visiting students only (VV1) Learn enabled:  No Quota:  5
Web Timetable Web Timetable
Course Start Date 13/01/2014
Breakdown of Learning and Teaching activities (Further Info) Total Hours: 200 ( Seminar/Tutorial Hours 22, Programme Level Learning and Teaching Hours 4, Directed Learning and Independent Learning Hours 174 )
Additional Notes
Breakdown of Assessment Methods (Further Info) Written Exam 100 %, Coursework 0 %, Practical Exam 0 %
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S2 (April/May)Logic, Computability and Incompleteness2:00
Summary of Intended Learning Outcomes
Upon successful completion of the course, students 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;
thorough understanding of 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;
ability to employ abstract, analytical and problem solving skills;
ability to formulate clear and precise pieces of mathematical reasoning.
Also, students will demonstrate the following transferable skills:
evaluating abstract theoretical claims;
grasping and analysing complex metatheoretical concepts;
deploy rigorous formal methods.
Assessment Information
There will be an opportunity for formative assessment and guidance based on exercise sets assigned during the semester. The course will be assessed by a 2 hour degree examination. The final mark for the course will be based on this examination.
Special Arrangements
None
Additional Information
Academic description Not entered
Syllabus Not entered
Transferable skills Not entered
Reading list The following is a sample bibliography, intended to indicate the type of reading that will be covered in the course.
[1] Boolos, G.S., J.P. Burgess & R.C. Jeffrey (2002) Computability and Logic, 4th edition, Cambridge University Press.
[2] Machover, M (1996) Set Theory, Logic and Their Limitations, Cambridge University Press.
[3] Enderton, H. (2001) A Mathematical Introduction to Logic.
[4] Mendelson, E. (1987) An Introduction to Mathematical Logic.
[5] Smith, P. (2007) An Introduction to Gdel's Theorems, Cambridge University Press.
Study Abroad Not entered
Study Pattern Not entered
KeywordsNot entered
Contacts
Course organiserDr Paul Schweizer
Tel: (0131 6)50 2704
Email: paul@inf.ed.ac.uk
Course secretaryMiss Susan Richards
Tel: (0131 6)51 3733
Email: sue.richards@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information
 
© Copyright 2013 The University of Edinburgh - 10 October 2013 5:11 am