MATH230-13S2 (C) Semester Two 2013

Logic, Automata, and Computability

15 points

Details:
Start Date: Monday, 8 July 2013
End Date: Sunday, 10 November 2013
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Friday, 19 July 2013
  • Without academic penalty (including no fee refund): Friday, 4 October 2013

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

Prerequisites

30 points from MATH100-199 excluding MATH101; or with permission of the Head of Department

Restrictions

MATH208, MATH308, PHIL208, PHIL210, PHIL308, PHIL225, PHIL246, PHIL346

Equivalent Courses

Course Coordinator

Maarten McKubre-Jordens

Assessment

Assessment Due Date Percentage 
Tutorials 5%
Assignments 40%
Final Examination 55%

Course links

MATH230 Homepage

Indicative Fees

Domestic fee $647.00

International fee $3,325.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-13S2 (C) Semester Two 2013
Previous year Next year