MATH230-18S2 (C) Semester Two 2018

Logic, Automata, and Computability

15 points
16 Jul 2018 - 18 Nov 2018

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 perserverance may do well.

Topics covered:

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, Gentzen's sequent calculus, equivalence of logical systems, and links between proof and computation.

Lectures for the second half of the course outline formal models of computation and establish the link of these models with formal logic. We will cover topics from the following list: formal languages, finite-state automata, push-down automata, computability, Turing machines, Markov algorithms, effective enumerations, the Church-Markov-Turing thesis, the Halting Problem.

Learning Outcomes

By the end of the course, students should:

  • have developed an appreciation for the mathematical foundations of computation
  • have insight into the way humans reason
  • understand some fundamental ideas concerning proof
  • be convinced that computers, despite their amazing computing power, have fundamental limitations
    • University Graduate Attributes

      This course will provide students with an opportunity to develop the Graduate Attributes specified below:

      Critically competent in a core academic discipline of their award

      Students know and can critically evaluate and, where applicable, apply this knowledge to topics/issues within their majoring subject.

Pre-requisites

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 2018

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Friday 11:00 - 12:00 Ernest Rutherford 140 16 Jul - 26 Aug
10 Sep - 21 Oct
Lecture B
Activity Day Time Location Weeks
01 Thursday 12:00 - 13:00 E14 Lecture Theatre 16 Jul - 26 Aug
10 Sep - 21 Oct
Lecture C
Activity Day Time Location Weeks
01 Monday 11:00 - 12:00 F1 Lectorial 16 Jul - 26 Aug
10 Sep - 21 Oct
Tutorial A
Activity Day Time Location Weeks
01 Friday 12:00 - 13:00 Jack Erskine 240 23 Jul - 26 Aug
10 Sep - 21 Oct
02 Monday 16:00 - 17:00 Jack Erskine 240 23 Jul - 26 Aug
10 Sep - 21 Oct

Course Coordinator / Lecturer

Hannes Diener

Textbooks

The lecture notes are largely self-contained. For a wider reading, the following are good resources.

For the course as a whole:
• Loveland, Hodel, and Sterrett’s Three Views of Logic (Princeton)

For the logic half:
• Prawitz’s Natural Deduction (Dover),
• Lemmon’s Beginning Logic
• Jeffrey’s Formal Logic: its scope and limits (Hackett)

For the automata half:
• Linz’s Introduction to Formal Languages and Automata (Jones & Bartlett)
• Hopcroft, Motwani, and Ullman’s Introduction to Automata Theory, Languages, and Computation (Addison-Wesley)

Indicative Fees

Domestic fee $749.00

International fee $3,788.00

* Fees include New Zealand GST and do not include any programme level discount or additional course related expenses.

For further information see Mathematics and Statistics.

All MATH230 Occurrences

  • MATH230-18S2 (C) Semester Two 2018