For a narrow/printable version of this webpage click here. Syllabus

Lectures

Professor

Textbook

Grades

Exams

Class Participation

Honor Principle

Disabilities

Questions

Some Final Thoughts

Homework Schedule



Syllabus

The 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.


Lectures

Meeting Time MWF 1:45 - 2:50
x-hour Thursday 1:00 - 1:50
Meeting Place 103 Bradley Hall


Professor

My name is Alex McAllister and I will be teaching Math 29 for Spring 1999. My office is 411 Bradley Hall and my telephone number is 646-2960. If you need to speak with me, you may come to my office hours, or contact me via e-mail at Alex.M.McAllister@dartmouth.edu. You might also be interested in visiting my home page at http://www.math.dartmouth.edu/~amcallis/.


Textbook

The textbook for this course is:
  • Computability: An Introduction to Recursive Function Theory
This text was written by Nigel J. Cutland and is published by Cambridge University Press.


Grades

Your grade for the course will be determined by the following:
Quizzes 20%
Homework Problems 20%
Class Presentations 10%
Midterm Exam 25%
Final Exam 25%


Exams

As mentioned above, there will be a Midterm Exam and a Final Exam. The Midterm Exam will occur the week of April 26th - 30th; the Final Exam will occur between June 4th and June 6th at a time and place to be determined once the registrar announces the regular schedule.

The exams will take place at the following times and places:

Exam Date Time Place
Midterm Exam TBA TBA TBA
Final Exam TBA TBA TBA


Class Participation

Class participation is an essential part of the course; mathematics is not a spectator sport. For this course, class participation consists of class attendance, reading assignments, quizzes, homework problems, and class presentations.

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.


Honor Principle

Work on all quizzes and exams should be strictly your own.

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.


Disabilities

I encourage students with disabilities, including but not limited to disabilities like chronic diseases, learning disabilities, and psychiatric disabilities, and students dealing with other exceptional circumstances to come see me after class or during office hours so that we can make appropriate accommodations. Also, you should stop by the Academic Skills Center in Collis Center to register for support services.


Questions

If you have any questions about this syllabus or about the material presented in this course, come talk to me. Although, I do enjoy mathematics (and computability in particular), I am not here just to have fun. My primary goal is to help you learn and understand computability. Your questions are an important part of your learning process, and I can help you find answers.


Some Final Thoughts

The bulk of the course will be studying formal concepts and proving formal theorems. Do not get behind; it will be very difficult, if not impossible, to catch up. Study all the material as it is covered and make sure that you understand it. Simply remembering it, although necessary, will not be adequate.

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.
Alfred North Whitehead