Trent University, Winter 2010
Mathematics-Computer & Information Systems 4216H - Computability
(Formerly Mathematics-Computer Science 416H.)

Prerequisite: 60% or higher in COIS 3050H (COSC 305H) or MATH-COIS 4215H (MATH-COSC 415H), or permission of the instructor. Excludes MATH-COSC 416H.

Instructor | Text | Meetings | Marking | Content | Honour | Aids | Help! | Work & Handouts

Instructor

Stefan Bilaniuk
office: GCS 337
Fall: Mondays 11:00-11:50, Tuesdays 14:00-14:50, Wednesdays 12:00-12:50
hours: Monday, Wednesday, and Thursday 13:00-13:50, and Friday 12:00-12:50, or by appointment, or just drop by...
phone: 748-1011 x7474
home phone: 705 742-7862 (Do not call between 10 p.m. and 8 a.m. unless it's an emergency.)
e-mail: sbilaniuk{at}trentu{dot}ca
web: http://www.trentu.ca/mathematics/sb/

Text

A Problem Course in Mathematical Logic, Version 1.6, Stefan Bilaniuk, 2003.
(You may also end up using some material from version 1.7, O guinea pigs!)
It's free, and can be downloaded from: http://www.trentu.ca/mathematics/sb/pcml/

Meetings

Lectures: Wednesday 11:00-11:50 in ECC 202, Thursday 14:00-14:50 in ECC 202, and Friday 10:00-10:50 in ECC 202.
Seminars: Thursday 15:00-15:50 in ECC 202.

In practice we will use our periods as lectures, seminars, or problem-solving sessions as necessary.

Marking scheme

There will be twelve weekly assignments and a project (including a proposal, a paper, and a presentation). The assignments will usually be handed out and collected every week in the Wednesday lectures. The proposal will be due on Friday, 12 February, and the paper on Friday, 23 April, while the presentations will be given during the last two weeks of classes. These items will weigh as follows in the final mark:

Students unable to hand in work in time, or deliver their presentations as scheduled, for reasons beyond their control should contact the instructor as soon as possible. Note that there is no attendance requirement per se, but the consequences of missing classes are ultimately the student's responsibility to deal with.

This scheme may be modified for individual students in exceptional circumstances, such as a lengthy absence due to illness. Any such modification will require the agreement of both the student and the instructor.

Please note that this year's Reading Week will come after only five weeks of classes, in the week of 15 February, and that the final date to withdraw from the course without academic penalty is Friday, 12 March.

Content

We will cover most of the following in the first eight weeks or so of the course:

1. Turing machines
2. Turing-computable, non-computable, and recursive functions
3. Computational equivalence of Turing machines and recursive functions
4. Universal Turing machines and the Halting Problem

5. More on the topics above.
6. Gödel Incompleteness Theorems [MATH-COIS 4215H or equivalent required!]
7. Complexity theory (up to the P=NP problem and NP-completeness)

Honour

The obligatory statement concerning academic integrity reads as follows:

Academic dishonesty, which includes plagiarism and cheating, is an extremely serious academic offence and carries penalties varying from a 0 grade on an assignment to expulsion from the University. Definitions, penalties, and procedures for dealing with plagiarism and cheating are set out in Trent University's Academic Integrity Policy. You have a responsibility to educate yourself - unfamiliarity with the policy is not an excuse. You are strongly encouraged to visit Trent's Academic Integrity website to learn more - www.trentu.ca/academicintegrity .

For clarity, the following guidelines will apply in MATH-COIS 4216H:

You are permitted and encouraged to study together and to work together on the assignments and projects, consult any books or other sources you wish, and ask anyone willing (especially the instructor!) for hints, suggestions, and help. However, you must write up all work submitted for credit entirely by yourself (respectively, yourselves, for those doing a group project), giving due credit to all relevant sources of help and information.

Aids

You may find it convenient to look up and use specialized software, such as Turing machine simulators, for some parts of the course.

Note that "personal response systems" such as clickers will not be used in MATH-COIS 4216H.

Help!

Subject to the conditions mentioned above, you can get help from a number of different sources, especially from each other and from the instructor. In some circumstances you may also be eligible for special help or accommodation. The obligatory statement concerning access to instruction reads as follows:

It is Trent University's intent to create an inclusive learning environment. If a student has a disability and/or health consideration and feels that he/she may need accommodations to succeed in this course, the student should contact the Disability Services Office (Bata Library Suite 109, 705 748-1281, disabilityservices{at}trentu{dot}ca) as soon as possible. Complete text can be found under Access to Instruction in the Academic Calendar.

Work & Handouts

• MATH-COIS 4216H Course Outline
• MATH-COIS 4216H Assignments
• MATH-COIS 4216H Projects
• A Problem Course in Mathematical Logic, Version 1.6
  From Version 1.7α, Part V: Chapter 19, 20, 21
  

Department of Mathematics

Trent University