MATH335-09S2 (C)
Computability Theory
This is a second semester course worth 14 points.
Message of the Day
Posted by Douglas Bridges on September 29 2009, 4:27 pm
29 September 2009
A) I have now uploaded to the MATH 335 webpage the following pdf files:
1) Slides for my lectures on abstract complexity theory
2) Problem sheet 6
In the problem sheet do only the first 5 problems; the others are too advanced for this course.
B) The final test is confirmed for Monday 12 October, from 5.00 to 7.00 p.m., in a location to be advised. It covers only the material we have discussed this term; there will be no question specifically associated with Dr Diener's part of the lectures. You will not be asked about computable/noncomputable real numbers; in particular, the hard proof of Cantor's theorem will not be part of the test. What is important to know are things like the undecidability of the halting problem; recursive and recursively enumerable sets; proofs that sets are not recursive/r.e.; Rice's theorem and its applications; the recursion theorem and its applications; and the very elementary parts of Blum complexity theory (excluding recursive relatedness, gap theorem, speed-up theorem).
dsb
A) I have now uploaded to the MATH 335 webpage the following pdf files:
1) Slides for my lectures on abstract complexity theory
2) Problem sheet 6
In the problem sheet do only the first 5 problems; the others are too advanced for this course.
B) The final test is confirmed for Monday 12 October, from 5.00 to 7.00 p.m., in a location to be advised. It covers only the material we have discussed this term; there will be no question specifically associated with Dr Diener's part of the lectures. You will not be asked about computable/noncomputable real numbers; in particular, the hard proof of Cantor's theorem will not be part of the test. What is important to know are things like the undecidability of the halting problem; recursive and recursively enumerable sets; proofs that sets are not recursive/r.e.; Rice's theorem and its applications; the recursion theorem and its applications; and the very elementary parts of Blum complexity theory (excluding recursive relatedness, gap theorem, speed-up theorem).
dsb
Course Information
Mathematical models of computation. Computability and non-computability. Abstract complexity theory.
Class Representative
Enquiries
Prof. Douglas Bridges
Room 322 Rutherford Building
Phone Extension 8878
Homepage