I.   Number and Title of the Course

MAT 401  Introduction to Computability
 

II.   Reasons for Revision

We have updated the bibliography and expanded the course pre-requisites to better address and reflect the current work in this area.  The title of the course has also been changed.  The course continues to serve the following purposes in our program:

A. To introduce our students to finite automata and Turing machines, and the general area of abstract computability.

B. To provide students with an opportunity to study the characterization and nature of mathematical problems that are undecidable and gain a broader understanding of the nature of computers.
 

III. Major Objectives of the Course

A. Students will learn about concepts of finite automata and Turing machines, their basic features, and the nature of the sets they accept and functions they define.

B. Students will learn about special problems in mathematics that are undecidable, for example, the Halting Problem for Turing Machines.
 

IV. Topical Outline

A.  Finite Automata

1. Description and representation
2. Sets accepted
3. Deterministic and nondeterministic automata

1. Definition and representation
2. Functions computable by a Turing machine
3. Universal Turing machines
4. The Halting Problem for Turing machines

1. Recursive and partial-recursive functions
2. Recursive and recursively enumerable sets
3. Turing machine characterizations of functions and sets

1. Kleene's representation theorem of sets accepted by a finite automata
2. Complexity measures
3. The Recursion Theorem

V. Bibliography

Boolos, G. and Jeffrey, R. (1989). Computability and Logic. Cambridge: Cambridge University Press.
Cutland, N. (1992). Computability. Cambridge:  Cambridge University Press.
Dewdney, A. (1993). The New Turing Omnibus.  New York:  W.H. Freeman.
Feynman, R. (1996). Lectures on Computation.  New York:  Addison-Wesley.
Hennie, F. (1979). Introduction to Computability.  New York:  Addison-Wesley.
Smith, C. (1994). A Recursive Introduction to the Theory of Computation.  New York:  Springer--Verlag.
 

VI Presentation and Evaluation

A.   Presentation by lectures and class discussion.

B.   Evaluation by examinations, homework assignments and class participation.
 

VII. Prerequisites

MAT 270 and either MAT 301 or MAT 351.
 

VIII. Credit

 3 Credits (3:0)
 

IX. Statement of Approval

This course proposal was examined in accordance with recommended procedures and
approved by the Department of Mathematics Curriculum Committee on
 _______________________.   ________________________________
       Signature of Department Chair       Date
 

X. Catalog Description

An introduction to topics in finite automata and Turing Machines, including universal Turing machines, and abstract computability.
 

XI. Statement of Qualifications of Faculty Who Will Teach the Course

A.  General faculty qualifications:  A Ph.D. in Mathematics or expertise in the area of computability.

B.   The following faculty have, at the present time, the necessary qualifications:
 Dr. Joseph Barback, Ph.D. in Mathematics
 Dr. Daniel Cunningham, Ph.D. in Mathematics
 

XII. Support Services Required

 Present classroom facilities are adequate.