Use the Tab and Up, Down arrow keys to select menu items.
An introduction to various formal logics, the theory of automata, and the theoretical limitations of the computer.
During the first half of the course, we will take a tour through some of the rigorous mathematical foundations of modern computer science. 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 in this part. The second half of the course will take a close look at the concept of logical deduction. We will study classical propositional and quantifier logic using an approach called `natural deduction'. Towards the end of the course, we will look at intuitionistic logic, after an introduction to various philosophies of mathematics.Topics covered: Lectures for the first half will draw on 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.The second half of the course will take a close look at the concept of logical deduction. Lectures will cover propositional and first-order natural deduction, soundness and completeness of formal systems, interpretations, Gentzen's sequent calculus, equivalence of logical systems, and links between proof and computation. Time depending, we may venture into aspects of non-classical logics such as intuitionistic logic and substructural logics.
By the end of the course, students should:have developed an appreciation for the mathematical foundations of computationhave insight into the way humans reasonunderstand some fundamental ideas concerning proofbe convinced that computers, despite their amazing computing power, have fundamental limitations
30 points from MATH100-199 excluding MATH101; or with permission of the Head of Department
MATH208, MATH308, PHIL208, PHIL210, PHIL308, PHIL225, PHIL246, PHIL346
PHIL210
Maarten McKubre-Jordens
MATH230 Homepage
Domestic fee $622.00
International fee $3,200.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 .