For a narrow/printable version of this
webpage click here.
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.
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.
Lectures
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:
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:
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.
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.Honor Principle
Work on all quizzes and exams should be strictly your own.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.
