MATH 4LT3/6LT3 - Topics in Logic

2021 Fall Term (tentative)

Instructor: Matt Valeriote | E-mail: matt@math.mcmaster.ca | Office: HH 323 | Telephone: (905) 525-9140 ext. 23402

 

 Web Page:  http://ms.mcmaster.ca/~matt/ | Course Web Page: http://ms.mcmaster.ca/~matt/4lt3

 

Lectures:  Monday, Thursday 12:30pm-1:20pm, Tuesday 1:30pm-2:20pm.   All lectures will be presented live, online, via Zoom. Details on how to obtain links for the Zoom lectures can be found on the Avenue to Learn site for this course and also on the course website.  You will be expected to attend and participate in the online classes.  The lectures will be recorded and available online through the Avenue To Learn site for this course.

 

 Office Hours:  from 2:00pm to 3:20pm on Mondays and Thursdays (tentative days and times) and by appointment.

 

COURSE DESCRIPTION

At the foundations of Computer Science lies some very interesting and beautiful mathematics.  In this course we will investigate the foundations of computer science by considering various mathematical models of computation and by formulating a precise definition of an algorithm.  We will study simple computational devices known as automata as well as the more powerful model developed by Alan Turing (known as Turing Machines).  With a formal notion of an algorithm in hand we will be able to study the class of computable functions and also produce natural functions that are not computable. Once the basic theory of computation has been set up we will then consider questions of computational complexity and will focus on the celebrated P vs. NP problem.

 

Three lectures; one term

Prerequisite(s): Students will be admitted into this course by permission of the instructor but will be expected to have taken the course MATH 2R03 (Linear Algebra II). Students may be evaluated using a set of graded assignments, midterm test(s), a project, and a final exam.   Note that students who have taken a similar course from the Department of Computing & Software, such as COMP SCI 4TC3, should not register for this course.

 

COURSE AND LEARNING OBJECTIVES

In this course an introduction to the theory of computable functions will be given. We will investigate several models for computation, the most notable being the Turing machine. As an introduction to this we will briefly look at a simpler kind of machine, the so called finite state automaton.

Once these models for computation have been discussed we will consider computable and noncomputable sets and functions. If time permits we will look into questions dealing with the computational complexity of algorithms, and in particular, the famous P versus NP problem.  Currently, the plan is to work through most of the material found in the following chapters of the course textbook: 1, 2, 3, 6, 7, and 8.

 

MATERIALS & FEES

REQUIRED MATERIALS/ RESOURCES

Textbook:   "Concise Guide to Computation Theory", by Akira Maruoka, published by Springer-Verlag, 2011.  

Note that this book is available as an ebook from the McMaster Library system and so can be freely downloaded by students in the course.  No arrangements have been made for this book to be available from the campus bookstore.  Here is a link to the entry for this book in the McMaster Library system: http://discovery.mcmaster.ca/iii/encore/record/C__Rb1734127  You might need to be logged into the library system or be using an on campus computer in order to download this book.

An optional text for this course is the book "Introduction to the theory of computation" by Michael Sipser.  A hard copy of the 2nd edition of this book is available through the McMaster Library system (https://discovery.mcmaster.ca/iii/encore/record/C__Rb1273423?lang=eng), and a 3rd edition is also available (but not from the library).

VIRTUAL COURSE DELIVERY

To follow and participate in virtual classes it is expected that you have reliable access to the following: 

If you think that you will not be able to meet these requirements, please contact uts@mcmaster.ca as soon as you can. Please visit the Technology Resources for Students page for detailed requirements. If you use assistive technology or believe that our platforms might be a barrier to participating, please contact Student Accessibility Services, sas@mcmaster.ca, for support.

 

 

COURSE OVERVIEW AND ASSESSMENT  

Tests:

There will be two 50-minute tests held on Tuesday, October 19 during the class time and Tuesday, November 16 during the class time (both are tentative dates and times). Further details on the tests will be given in class and announced on the course web page. Each test will be worth 20% of your final grade.

 

 

Assignments:

Assignments will be assigned on a bi-weekly basis (more or less). In total, the grade from the assignments will count for 10% of the final grade. Late assignments will not be accepted for grading.

 

Please refer to request for "Relief for Missed Academic Term Work (MSAF) Policy" located within the General Academic Regulations of the Academic Calendar.  

 

Project:

Each student in the class will be expected to submit an essay on some topic related to the course material.  Further details and guidelines will be presented in class and on the course website. The project will be worth 5% of the final grade.

 

Final Examination:

As scheduled by the Registrar. Details (e.g., material that will be covered, final examination locations, etc.) will be given in class and announced on the course web page. The final exam will be worth 45% of the final grade.

 

EVALUATION

Your final grade for the course will be computed as follows:

 

       Assessment                                                                  Weight

1.       Final Exam

                        45%

 

2.       Test #1

                        20%

 

3.       Test #2

                        20%

 

4.       Assignments

                        10%

 

5.       Project            

                        5% 

 

 

 

 

 

The instructor reserves the right to change the weight of any portion of this marking scheme. For students in good academic standing, other weights might be considered. In either case, the final mark will be computed using this weighting and the new weighting(s). The highest score for a particular student will be her/his final mark. At the end of the course the grades may be adjusted but this can only increase your grade and will be done uniformly. We will use the grade equivalence chart published in the Undergraduate Calendar to convert between percentages and letter grades.

 

In case of difficulty/problems:

Contact Dr. Valeriote as soon as possible. Failing that, contact the Associate Dean's Office in BSB 129.

 

 

Requests for Relief for Missed Academic Term Work

McMaster Student Absence Form (MSAF):  In the event of an absence for medical or other reasons, students should review and follow the Academic Regulation in the Undergraduate Calendar "Requests for Relief for Missed Academic Term Work".

Academic Accommodation of Students with Disabilities

Students with disabilities who require academic accommodation must contact Student Accessibility Services (SAS) at 905-525-9140 ext. 28652 or sas@mcmaster.ca to make arrangements with a Program Coordinator. For further information, consult McMaster University's Academic Accommodation of Students with Disabilities  policy.

 

Academic Accommodation for Religious, Indigenous Or Spiritual Observances (Riso)

Students requiring academic accommodation based on religious, indigenous or spiritual observances should follow the procedures set out in the RISO policy. Students should submit their request to their Faculty Office normally within 10 working days of the beginning of term in which they anticipate a need for accommodation or to the Registrar's Office prior to their examinations. Students should also contact their instructors as soon as possible to make alternative arrangements for classes, assignments, and tests.

Courses with An On-Line Element

Some courses may use on-line elements (e.g. e-mail, Avenue to Learn (A2L), LearnLink, web pages, capa, Moodle, ThinkingCap, etc.). Students should be aware that, when they access the electronic components of a course using these elements, private information such as first and last names, user names for the McMaster e-mail accounts, and program affiliation may become apparent to all other students in the same course. The available information is dependent on the technology used. Continuation in a course that uses on-line elements will be deemed consent to this disclosure. If you have any questions or concerns about such disclosure, please discuss this with the course instructor.

Online Proctoring

Some courses may use online proctoring software for tests and exams. This software may require students to turn on their video camera, present identification, monitor and record their computer activities, and/or lock/restrict their browser or other applications/software during tests or exams. This software may be required to be installed before the test/exam begins. 

Academic Integrity

You are expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. Academic credentials you earn are rooted in principles of honesty and academic integrity.

It is your responsibility to understand what constitutes academic dishonesty.

Academic dishonesty is to knowingly act or fail to act in a way that results or could result in unearned academic credit or advantage. This behaviour can result in serious consequences, e.g. the grade of zero on an assignment, loss of credit with a notation on the transcript (notation reads: "Grade of F assigned for academic dishonesty"), and/or suspension or expulsion from the university. For information on the various types of academic dishonesty please refer to the Academic Integrity Policy, located at https://secretariat.mcmaster.ca/university-policies-procedures- guidelines/

 

The following illustrates only three forms of academic dishonesty:

Authenticity / Plagiarism Detection

Some courses may use a web-based service (Turnitin.com) to reveal authenticity and ownership of student submitted work. For courses using such software, students will be expected to submit their work electronically either directly to Turnitin.com or via an online learning platform (e.g. A2L, etc.) using plagiarism detection (a service supported by Turnitin.com) so it can be checked for academic dishonesty.

 

Students who do not wish their work to be submitted through the plagiarism detection software must inform the Instructor before the assignment is due. No penalty will be assigned to a student who does not submit work to the plagiarism detection software. All submitted work is subject to normal verification that standards of academic integrity have been upheld (e.g., on-line search, other software, etc.). For more details about McMaster's use of Turnitin.com please go to the McMaster Office of Academic Integrity's webpage.

Conduct Expectations

As a McMaster student, you have the right to experience, and the responsibility to demonstrate, respectful and dignified interactions within all our living, learning and working communities. These expectations are described in the Code of Student Rights & Responsibilities (the "Code"). All students share the responsibility of maintaining a positive environment for the academic and personal growth of all McMaster community members, whether in person or online.

 

It is essential that students be mindful of their interactions online, as the Code remains in effect in virtual learning environments. The Code applies to any interactions that adversely affect, disrupt, or interfere with reasonable participation in University activities. Student disruptions or behaviours that interfere with university functions on online platforms (e.g. use of Avenue 2 Learn, WebEx or Zoom for delivery), will be taken very seriously and will be investigated. Outcomes may include restriction or removal of the involved students' access to these platforms.

Copyright and Recording

Students are advised that lectures, demonstrations, performances, and any other course material provided by an instructor include copyright protected works. The Copyright Act and copyright law protect every original literary, dramatic, musical and artistic work, including lectures by University instructors.

 

The recording of lectures, tutorials, or other methods of instruction may occur during a course. Recording may be done by either the instructor for the purpose of authorized distribution, or by a student for the purpose of personal study. Students should be aware that their voice and/or image may be recorded by others during the class. Please speak with the instructor if this is a concern for you.

Extreme Circumstances

The University reserves the right to change the dates and deadlines for any or all courses in extreme circumstances (e.g., severe weather, labour disruptions, etc.). Changes will be communicated through regular McMaster communication channels, such as McMaster Daily News, A2L and/or McMaster email.