MATH230-24S2 (C) Semester Two 2024

# Logic, Automata, and Computability

15 points

Details:
 Start Date: Monday, 15 July 2024 End Date: Sunday, 10 November 2024
Withdrawal Dates
Last Day to withdraw from this course:
• Without financial penalty (full fee refund): Sunday, 28 July 2024
• Without academic penalty (including no fee refund): Sunday, 29 September 2024

## Description

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

This course takes a tour through the process of rigourouslly formalising mathematics and the process of computation. 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 course is divided into two parts. The first part of the course will discuss first order logic and the process of formalising mathematics into first order logic. The limits of the methods of mathematics, uncovered by this process of formalisation, may be discussed if time permits. Lectures in the second half of the course will outline some formal models of computation and the limits they uncovered. Depending on the teaching staff the topics covered will be chosen from: recursive functions, lambda calculus, type theory, Curry-Howard correspondence, proof/program verification, undecidability, formal languages, finite-state automata, Turing machines, register machines, Markov algorithms, grammars, and cellular automata.

## 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).

## Timetable 2024

Students must attend one activity from each section.

Activity Day Time Location Weeks Lecture A 01 Thursday 10:00 - 11:00 Link 309 Lecture Theatre 15 Jul - 25 Aug 9 Sep - 20 Oct Lecture B 01 Monday 09:00 - 10:00 Link 309 Lecture Theatre 15 Jul - 25 Aug 9 Sep - 20 Oct Lecture C 01 Tuesday 13:00 - 14:00 Link 309 Lecture Theatre 15 Jul - 25 Aug 9 Sep - 20 Oct Tutorial A 01 Monday 13:00 - 14:00 Jack Erskine 442 Computer Lab 15 Jul - 25 Aug 9 Sep - 20 Oct 02 Monday 16:00 - 17:00 Jack Erskine 442 Computer Lab 15 Jul - 25 Aug 9 Sep - 20 Oct 03 Thursday 13:00 - 14:00 Jack Erskine 442 Computer Lab 15 Jul - 25 Aug 9 Sep - 20 Oct

## Indicative Fees

Domestic fee \$847.00

International fee \$4,988.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-24S2 (C) Semester Two 2024