Spring 1999: Math 450 and Math 570
Math 450, MWF 12-1 DRL 4C4
You may also wish to contact Professor
Andre Scedrov
about this course.
Textbook
- M. Sipser. "Introduction to the Theory of Computation".
PWS Publishing Company, 1997. ISBN 0-534-94728-X.
About This Course
From the textbook preface: Theory of computation, a fascinating and important
subject, comprises the fundamental mathematical properties of computer
hardware, software, and certain applications thereof. In studying this
subject we seek to determine what can and cannot be computed, how quickly,
with how much memory, and on which type of computational model. ...
Nearly everyone working with computers is curious about these amazing
creations, their capabilities, and their limitations. A whole new branch
of mathematics has grown up in the past 30 years to certain basic questions.
Here's a big one that remains unsolved: If I give you a large number, say,
with 500 digits, can you find its factors (the numbers that divide it evenly)
in a reasonable amount of time? Even using a supercomputer, no one
presently knows how to do that in all cases within the lifetime of
the universe!
Topics
Finite Automata, Regular Languages, Nondeterminism,
Context-Free Languages, Turing Machines, Decidability,
The Halting Problem. Time and Space Computational Complexity,
Computational Complexity Classes P, NP, and PSPACE,
NP-Complete Problems, PSPACE-Complete Problems,
Alternation, Probabilistic Algorithms, Interactive Proof Systems.
Math 570, MWF 3-4 DRL 4C4
You may also wish to contact Professor
Andre Scedrov
about this course.
About This Course
From
Encyclopaedia Britannica:
Gödel's proof, which states that within any rigidly logical
mathematical system there are propositions (or questions)
that cannot be proved or disproved on the basis of the
axioms within that system and that, therefore, it is
uncertain that the basic axioms of arithmetic will not give
rise to contradictions. This proof has become a hallmark of
20th-century mathematics, and its repercussions continue
to be felt and debated.
Textbooks
- D. van Dalen. "Logic and Structures", Third Edition.
Springer-Verlag, 1994. ISBN 0-387-57839-0 paperback.
- G.S. Boolos and R.C. Jeffrey. "Computability and Logic", Third Edition.
Cambridge University Press, 1989. ISBN 0-521-38923-2 paperback.
Topics
- Propositional Logic: Propositions and Connectives, Semantics, Natural
Deduction, Completeness.
- Predicate Logic: Quantifiers, Structures, Semantics, Natural Deduction,
The Completeness Theorem, Compactness and Skolem-Löwenheim Theorems,
Skolem Functions.
- Undecidability and Incompleteness: Turing Machines, Undecidability of
Predicate Logic, Gödel's First and Second Incompleteness Theorems.