MATH230-12S2 (C)
Logic, Automata, and Computability
This is a semester two course worth 15 points.
Course Information
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.
We will study classical propositional and quantifier logic using an approach called `natural deduction'. We will also look at aspects of non-classical logic, such as intuitionistic logic and its significance for computation, and paraconsistent logic, in which, surprisingly, contradiction does not necessarily lead to disaster.
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
Enquiries
Maarten McKubre-Jordens
Room 703 Erskine Building
Phone Extension 3823
Homepage