Math 29, Spring 2022

Introduction to Computability

Content

What does it mean for a function to be computable? This course examines several different mathematical formalizations of the notion of computability, inspired by widely varying viewpoints, and establishes the surprising result that all these formalizations are equivalent. It goes on to demonstrate the existence of noncomputable sets and functions, and to make connections to undecidable problems in other areas of mathematics. The course concludes with an introduction to relative computability.

Prerequisites

None, but requires a willingness to learn how to write formal proofs

Lecture Information

Please contact me if you'd like to make an appointment to meet outside of office hours.

Textbook

"Computability Theory", by Rebecca Weber, ISBN: 978-0-8218-7392-2

A digital copy of the book is available for free as a limited time rental. Lecture notes and handouts will be provided with the intention that the book will be a useful but optional resource.

Homework

Homework is assigned weekly on Wednesdays and is due the following Wednesday. Homework submissions should be legible, clearly presented, and begin with a short restatement of the problem. Rules for collaborating and using outside sources can be found below in the Honor Policy section.

Students will receive feedback on their solutions, and have the option to re-submit updated solutions to previous problems to improve their score. Refinement and iteration are important parts of both learning and practicing mathematics.

Exams

There will be a midterm exam and a final exam. Each exam will have an in-person portion and a take-home portion. The in-person portion will be a short quiz based on knowledge of the course material, and the take-home portion will feature questions testing your proof skills.

The in-person final exam will take place Monday, June 6th, at 11:30am in 201 Kemeny Hall.

Class Participation

Students will receive credit for attending lectures, answering and asking questions in class, and participating in group activities during lecture and X hours. There is no numerical quota for participation - students who are actively engaged in the course need not worry about this component of their grade.

Office Hours

TBD

X-Hours

Ben Logsdon will be running sessions during the X-hours covering material that is closely related to the course material. These sessions will include presentations, worksheets, group discussions, and proof strategies. Engagement during the X-hour sessions will count towards the course participation component of your grade.

Honor Policy

Academic integrity is at the core of our mission as mathematicians and educators, and we take it very seriously. We also believe in working and learning together.

Cooperation on homework is permitted (and encouraged), but you are not allowed to simply copy the answers from someone or somewhere else. You can share your thoughts with other students, but afterwards make sure to write only your own understanding of the problem: do not copy something verbatim. If your solution contains some insight from a fellow student, online post, or other external resource, attribution must be provided. (You do not need to credit me, lecture notes, or the Weber text, but must credit any other textbook you use.) Being inspired by someone else's ideas is encouraged, claiming credit for them is stealing.

On exams, you may not work with other students, use online sources, or any other external resource. For the in-class portion of the exam, you may not use lecture notes, the textbook, or any resource other than your memory and myself. During the take-home portion of the exam, you may consult your lecture notes, the official course textbook, and ask me questions, but no other resources.

Plagiarism, collusion, or other violations of the Academic Honor Principle, after consultation, will be referred to the The Committee on Standards. If you have any questions as to whether some action would be acceptable under the Academic Honor Principle, please speak to me beforehand.

Helpful Learning Resources

• Academic Skills Center
• Tutor Clearinghouse
• Academic Coaching

COVID-19 Information

Attendance

You are expected to attend class in person unless you have made alternative arrangements due to illness, medical reasons, or the need to isolate due to COVID-19.

For the health and safety of our class community, please: do not attend class when you are sick, nor when you have been instructed by Student Health Services to stay home.

Safety

Our class will observe College policy throughout the term, including making changes accordingly if the college revises its guidelines.

Accessibility

This course is meant to be welcoming and accessible to students from all backgrounds. Please schedule a meeting as soon as possible to discuss any potential conflicts arising from religious observances, planned medical procedures, or other life events. There is no guarantee that accommodations can be made if you wait until the last minute, so please be proactive.

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, or before the end of the second week of the term—at the latest, to discuss appropriate adjustments.

All students are encouraged to take care of their well-being. Dartmouth's Counseling Center and Wellness Center are available for student use. Please do not hesitate reach out to me about any difficulties you have in the course, or other stressors external to the course if you need someone to talk to.

Sexual respect, safety, and well-being are critical to Dartmouth's environment. Any and all forms of sexual assault, gender-based harassment, domestic violence, dating violence, and stalking are unacceptable and hostile to other members of the community. For more information, please visit Dartmouth's Sexual Respect website. Please note that, as a faculty member, I am a mandatory reporter under Title IX. That means that I must share any disclosures regarding conduct governed by Title IX to Dartmouth's Title IX coordinator. The Title IX office provides many resources to assist students who need them, which you can view here.

Mental Health

Even without the global pandemic, the academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. In the midst of a global pandemic, with all the uncertainty surrounding every aspect of our lives, these challenges take on an extra toll. There are a number of resources available to you on campus to support your wellness, including your undergraduate dean, Counseling and Human Development, and the Student Wellness Center.

Disability and COVID-19 Accommodations

Students requesting disability-related accommodations and services for this course are required to register with Student Accessibility Services (SAS; Getting Started with SAS webpage; student.accessibility.services@dartmouth.edu; 1-603-646-9900) and to request that an accommodation email be sent to me in advance of the need for an accommodation. Then, students should schedule a follow-up meeting with me to determine relevant details such as what role SAS or its Testing Center may play in accommodation implementation. This process works best for everyone when completed as early in the quarter as possible. If students have questions about whether they are eligible for accommodations or have concerns about the implementation of their accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.