Syllabus

\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]

Welcome to CSC438!

1 Basic Info

Instructor	Harry Sha
TA	Devansh Shringi
Session	Fall 2026
Lecture	Wednesday, 1:10 PM–3:00 PM at ES 142
Tutorial	Friday, 1:10 PM–2:00 PM at ES 149

2 Course Description

This course covers computability theory and mathematical logic. We formalize computation, logic, truth, and proof and study them rigorously. Whereas other courses use these notions as tools to study objects such as numbers, graphs, or programs, this course treats the notions themselves as objects of study. In essence, this is a study of the foundations of mathematics.

We will ask and answer questions such as: What are the limits of computation? Can we automate logic? Does every truth have a proof? Does mathematics rest on solid foundations? The answers are often surprising and lead to even deeper questions about the nature of mathematics.

3 Course Objectives

By the end of this course, students will be able to:

• reason about countable and uncountable sets;
• prove results about decidability, recognizability, and computability using diagonalization, reductions, and self-reference;
• formulate and interpret propositional and first-order logic, clearly distinguishing syntax, semantics, truth, validity, and logical consequence;
• construct and analyze derivations in the proof systems PK and LK and explain their soundness, completeness, and compactness properties;
• analyze theories and models of arithmetic;
• explain why the incompleteness theorem does not contradict the completeness theorem;
• prove Gödel’s incompleteness theorem and explain its significance and limitations; and
• explain the deep connections between computation, logic, and mathematics.

4 Optional Readings

• Sipser — Introduction to the Theory of Computation
• Enderton — A Mathematical Introduction to Logic

5 Course Website

If you are viewing this syllabus online, you have already found the course website. It contains all the course resources. If you cannot find something, please ask on Piazza.

6 Marking Scheme

• Problem Sets. A problem set will be released each week. Problem sets are not worth marks. Before each term test, you may optionally submit your solution to one problem for feedback.
• Pre Lecture. There are a few questions before each lecture. These will be administed on Crowdmark and typically released by the Monday before lecture. The point of these questions is to help you prepare for lecture. The best 8 out of 12 count. For each pre-lecture you get 0.5% for answering the questions well, and 0.25% for any reasonable attempt. In total, these pre lecture questions are worth 4% of your overall grade.
• Term Tests. There are three term tests, each worth 21% of your grade. After your marked term test is returned, you may recover some points on a question you answered incorrectly by explaining the correct solution to me. This explanation will take the form of either a short meeting with me or a video submission (tbd). Your new grade for that question will be a weighted (tbd) the average of your original grade and the grade for your new explanation.
• Final Exam. The final exam is worth 33% of your grade. There is no automatic-fail policy.

7 Contact Information & Office Hours

7.1 Contact Information

Sign up for Piazza, the course forum.

I encourage you to participate in discussions on Piazza and ask questions. Please be respectful of your fellow students. If you have questions about course logistics, make a private post on Piazza.

Announcements will be made on Quercus. Quercus should then notify you by email.

• Course content questions: Post on Piazza.
• Course administration (special considerations, etc.): Private post on Piazza.

There are many resources to support your studies and academic life at U of T. Please see the Student Support section for both CS-specific and university-wide resources.

7.2 Office Hours

Office hours are times when you can drop in and ask questions about the course. I highly encourage you to come and hang out, ask questions, and meet your fellow students.

The most up-to-date office-hours schedule can be found on the course calendar on the course website.

8 Course Policies

I have copied the following course policy statements from the Faculty of Arts and Science and the Department of Computer Science. I have also added text specific to this course in my own voice. My additions appear in orange; the remainder comes directly from the Faculty of Arts and Science and the Department of Computer Science.

8.1 Academic Integrity

All suspected cases of academic dishonesty will be investigated following procedures outlined in the Code of Behaviour on Academic Matters. If you have questions or concerns about what constitutes appropriate academic behaviour or appropriate research and citation methods, please reach out to me. Note that you are expected to seek out additional information on academic integrity from me or from other institutional resources. For example, to learn more about how to cite and use source material appropriately and for other writing support, see the U of T writing support website. Consult the Code of Behaviour on Academic Matters for a complete outline of the University’s policy and expectations. For more information, please see A&S Student Academic Integrity and the University of Toronto website on Academic Integrity. 

8.2 Equity, Diversity, and Inclusion

The University of Toronto is committed to equity, human rights, and respect for diversity. All members of the learning environment in this course should strive to create an atmosphere of mutual respect where all members of our community can express themselves, engage with each other, and respect one another’s differences. U of T does not condone discrimination or harassment against any persons or communities. 

8.3 Generative AI

Use of AI is not required for this course.

I leave it up to you to decide how and whether or not to use AI. I’m happy to chat more about this if you have questions or concerns.

8.4 Recording of Meetings

Some lectures for this course may be recorded. I cannot guarantee which lectures will be recorded or the quality of those recordings. Please attend class if possible. If you must miss a class, I encourage you to reach out to your fellow students for notes and come to office hours. I also post the slides used in class.

When there are recordings, they can be found on the course webpage.

Course videos and materials belong to your instructor, the University, and/or other sources depending on the specific facts of each situation, and are protected by copyright. Do not download, copy, or share any course or student materials or videos without the explicit permission of the instructor.

8.5 Remark Requests

Mistakes sometimes happen when marking. If you feel there is an issue with the marking of an assessment, you may request that it be remarked. Remark requests are accepted up to a week after assessments are returned, and will be completed before the final grades are submitted at the end of the term. You must give a specific reason for your request, referring to a possible error or omission by the marker. Remark requests without a specific reason will not be accepted.

The procedure for requesting a remark will be announced following the first term test.

8.6 Special Consideration and Missed Term Tests

If you know in advance that you will be unable to attend a term test, please let me know as soon as possible. If unexpected circumstances or an emergency prevent you from attending a term test, please contact me as soon as reasonably possible, even if that is after the test.

If you miss a term test, the weight of your missed term test will be equally distributed among your future assessments. There will be some adjustments made to account for discrepancies in the difficulty of the tests.

If you miss a second term test, you must meet with me, we can try to figure something out.

9 Student Support

9.1 Learning Strategist

Computer Science has a dedicated on-site learning strategist for one-on-one support in building effective study habits, problem-solving skills, time management, and strategies for exams, assignments, and academic success. Our learning strategist, Milena Pandy, can help you with these strategies and more. Learn more here or book an appointment.  

9.2 CS Academic Advisors

Academic advisors in the CS undergraduate office are here to help you with any questions you have about CS courses, programs, and co-curricular opportunities.  

Drop-in, in-person advising is available Mondays, Wednesdays, and Thursdays from 10:00 AM–12:00 PM and 2:00–4:00 PM in BA 4207. At other times, or if you have a more complex question and would like to schedule an advising appointment, please email cs.undergrad@utoronto.ca. Advisors are available during business hours Monday through Friday, and emails are typically answered within 2–3 business days. Learn more here. 

9.3 Mental Health and Well-Being / Wellness Supports

Your mental health is important. Throughout university life, many experiences can affect your mental health and well-being. As a University of Toronto student, you can access free mental health and well-being services at Health & Wellness, including same-day counselling, brief counselling, medical care, skill-building workshops, and drop-in peer support. You can also meet with a Wellness Navigation Advisor who can connect you with other campus and community services and support. Call the mental health clinic at 416-978-8030 ext. 5 to book an appointment, or visit the mental health care site to learn about the services available to you. 

You can also visit your College Registrar to learn about the resources and supports available.  

If you’re in distress, you can access immediate support at this link. 

9.4 Students with Disabilities or Accommodation Requests

Students with diverse learning styles and needs are welcome in this course. If you have an acute or ongoing disability issue or accommodation need, you should register with Accessibility Services (AS) at the beginning of the academic year by visiting their website, linked here. Without registration, you will not be able to verify your situation with your instructors, and instructors will not be advised about your accommodation needs. AS will assess your situation, develop an accommodation plan with you, and support you in requesting accommodation for your coursework. Remember that the process of accommodation is private: AS will not share details of your needs or condition with any instructor, and your instructors will not reveal that you are registered with AS. 

9.5 Religious Accommodation

As a student at the University of Toronto, you are part of a diverse community that welcomes and includes students and faculty from a wide range of cultural and religious traditions. For my part, I will make every reasonable effort to avoid scheduling tests, examinations, or other compulsory activities on religious holy days not captured by statutory holidays. Further to University Policy, if you anticipate being absent from class or missing a major course activity (such as a test or in-class assignment) due to a religious observance, please let me know as early in the course as possible and with sufficient notice—at least two weeks before the assessment due date—so that we can work together to make alternate arrangements.