UTSA logo Computability Theory
MAT 4953.01F
Summer I 2003
Instructor: J. Iovino
 

The course has been scheduled for Monday-Thursday, 2:00pm-3:50pm, during the first summer session.

Prerequisites

Familiarity with mathematical proofs. Formally, at least one the following courses, or instructor consent:
Foundations of Mathematics (MAT 2243)
Discrete Mathematical Structures (CS 3233)
Calculus II (MAT 1223).

Content

The initial purpose of computability theory is to make precise the intuitive idea of computable function. The fundamental ideas of computability arose in the early 1930's, and gave rise to some of the most profound intellectual achievements of the 20th century, such as Gödel's Incompleteness Theorems, and Turing's proof that computability via Turing machines is equivalent to computability via recursive functions. The concepts studied in the course have implications and applications in fields as diverse as computer science, philosophy, psychology, and the foundations of mathematics, as well as many areas of mathematics itself. The course will start with a study of the intuitive concept of computable function (modeled through the concept of unlimited register machines) and will conclude with a proof of Gödel's First Incompleteness Theorem.

  • Computable functions. Effective procedures, decidable problems
  • Generating computable functions. The basic functions, substitution, recursion, minimalization.
  • Different approaches to computability: Church's thesis. Gödel-Kleene computability (partial recursive functions), Turing computability (Turing machines), symbol manipulation systems of Post and Markov.
  • Numbering of computable functions. Numbering programs, the diagonal method, the s-m-n theorem.
  • Universal programs. Universal functions and universal programs.
  • Decidability and unsolvability. Undecidable problems, the word problem for groups, diophantine equations and Hilbert's tenth problem, Sturm's algorithm.
  • Recursive and recursively enumerable sets. Recursive sets, recursively enumerable sets, productive and creative sets.
  • Gödel's Incompleteness Theorem. Formal arithmetic, incompleteness, undecidability of truth.

    • Textbook

    Nigel Cutland, Computability: An introduction to Recursive Function Theory, Cambridge University Press, 1980.

    Additional References

    Martin Davis, Computability and Unsolvability, McGraw-Hill Series in Information Processing and Computers McGraw-Hill Book Co., Inc., New York-Toronto-London 1958.
    [A beautiful classic by an award-winning mathematician. Reprinted by Dover in 1983. At $10 for the Dover reprint, an incredible bargain.]

    George Boolos and Richard Jeffrey, Computability and Logic, Third edition. Cambridge University Press, 1989.
    [A classic too. There is a fourth edition which I do not recommend, however, because it introduced many typos. If you find a copy of any of the earlier editions, grab it.]

    Evaluation

    There will be five problem sets. Each problem set will be worth 20% of the grade.

    How to contact the instructor

    Office: SB 4.01.34 (Directions: Go to the fourth floor of the Science Building and as you get off the elevator follow the arrows to the Applied Mathematics Department. My office is right across the hall from the main office.)

    Telephone: 210-458-5531

    Email: iovino@math.utsa.edu

    Office hours: M,T,W, 4-5pm, or by appointment.

    Valid HTML 4.0!