 |
Syllabus Lectures Professor Textbook |
|
Grades Exams Class Participation Honor Principle |
|
Disabilities Questions Some Final Thoughts Homework Schedule |
|
|
|
SyllabusThe fundamental notion in Computability Theory is the formalization of the intuitive notion of an algorithm. Various formal definitions were introduced by Church, Gödel, Kleene, and Turing in the 1930's and 1940's and were eventually all shown to be equivalent. Among the most commonly used formalizations is that of a Turing machine, which is essentially a computer program idealized to ignore the time and space limitations.
In this course we will begin with URMs, which are supped-up Turing machines
that utilize more modern notions associated with computers and programming.
We will study several approaches that formalize the notion of computability and will
discuss the equivalence of these formalizations, including Church's Thesis
which claims that these formalizations capture the intuitive notion of computability.
We will then look at universal machines and undecidable problems.
We will finish by studying recursive sets, recursively enumerable sets, relative computability
and degrees of unsolvability.
The exams will take place at the following times and places:
You are expected to attend every class.
You have invested a large sum of money for the opportunity to come to class and
I will invest a large amount of time in preparing for class;
I do not want any of us wasting the investments we have made.
Reading assignments will be given daily and should be read before coming to class.
For some of my thoughts on reading mathematics texts,
click here.
Quizzes will be administered at the end of class on Monday covering material presented in
class the previous week.
They will consist of a couple of questions and should only take 10 - 15 minutes to complete.
If you do the homework for the lectures given the previous week (including Friday's homework),
then you should do fine on the quizzes.
Homework problems will be assigned daily and collected the following class period.
Late homework will not be accepted and a grade of 0 will be assigned
(of course, exceptions can be made for emergencies such as illness, death, natural disasters...).
The solutions you present must be coherent and written in complete sentences whenever possible.
Simply stating answers or turning in garbled, unclear solutions will result in a grade of 0.
For further details consult the
Homework Schedule.
Finally, you will be asked to present a couple of proofs in class.
You will be given a few options to choose from and will have plenty of time to prepare.
I would expect to meet with you before your presentation to discuss the proof and
any details or questions you might have.
Collaboration on homework is encouraged (and expected);
although, you should first spend some time in individual concentration to gain
the full benefit of the homework. On the other hand, copying is discouraged.
You should not be leaving a study group with your homework ready
to be turned in; write up your solution sets by yourself.
Also, take care in crafting your own proofs. You should be creating clear, coherent arguments.
Use complete English sentences and pay careful attention to the use of logical connectives.
Mathematics ... may claim to be the most original creation of the human spirit.
|
| ||||||||||||||||||||||||||||
