MATH230-23S2 (C) Semester Two 2023

Logic, Automata, and Computability

15 points

Details:
Start Date: Monday, 17 July 2023
End Date: Sunday, 12 November 2023
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 30 July 2023
  • Without academic penalty (including no fee refund): Sunday, 1 October 2023

Description

An introduction to various formal logics, the theory of automata, and the theoretical limitations of the computer.

This course takes a tour through some of the rigorous mathematical foundations of modern computer science and logic. Do not let the word “rigorous” scare you off – any student who possesses basic number skills, a healthy desire to grapple with abstract concepts, and perseverance may do well.

The first half of the course will take a close look at the concept of logical deduction. Lectures will be drawn from the following topics: natural deduction, soundness and completeness of formal systems, interpretations, intuitionistic logic, and links between proof and computation. Lectures for the second half of the course outline formal models of computation. We will cover topics from the following list: formal languages, finite-state automata, Turing machines, register machines, Markov algorithms, grammars, cellular automata, recursive functions, lambda calculus, other computation models, undecidability.

Learning Outcomes

  •  have developed an appreciation for the mathematical foundations of computation
  •  have insight into the way humans reason
  •  have developed skills in informal and formal reasoning
  •  understand some fundamental ideas concerning proof, proof checking, and proof search
  •  understand the links between different computation models
  •  be convinced that computers, despite their amazing computing power, have fundamental limitations

Prerequisites

15 points from MATH102-199, and a further 15 points from 100 level COSC, EMTH, MATH, PHIL or STAT courses, excluding COSC110 and MATH101.

Restrictions

MATH208, MATH308, PHIL208 (prior to 2014), PHIL210, PHIL308 (prior to 2014).

Equivalent Courses

Timetable 2023

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01-P1 Tuesday 11:00 - 12:00 Ernest Rutherford 141
17 Jul - 23 Jul
01-P2 Tuesday 08:00 - 09:00 Ernest Rutherford 141
24 Jul - 27 Aug
11 Sep - 22 Oct
Lecture B
Activity Day Time Location Weeks
01 Wednesday 11:00 - 12:00 E14 Lecture Theatre
17 Jul - 27 Aug
11 Sep - 22 Oct
Lecture C
Activity Day Time Location Weeks
01 Thursday 08:00 - 09:00 Jack Erskine 101
17 Jul - 27 Aug
11 Sep - 22 Oct
Tutorial A
Activity Day Time Location Weeks
01 Friday 13:00 - 14:00 Jack Erskine 442 Computer Lab
24 Jul - 27 Aug
11 Sep - 22 Oct
02 Wednesday 13:00 - 14:00 Jack Erskine 442 Computer Lab
24 Jul - 27 Aug
11 Sep - 22 Oct
03 Friday 14:00 - 15:00 Jack Erskine 442 Computer Lab
24 Jul - 27 Aug
11 Sep - 22 Oct

Examination and Formal Tests

Test A
Activity Day Time Location Weeks
01 Wednesday 18:30 - 20:30 Meremere 105 Lecture Theatre
14 Aug - 20 Aug

Course Coordinator

Robert Culling

Indicative Fees

Domestic fee $824.00

International fee $4,750.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Mathematics and Statistics .

All MATH230 Occurrences

  • MATH230-23S2 (C) Semester Two 2023
Previous year Next year