*Time*: 2:30-4:30 PM Tuesdays *Place*: 237 MSCS

*Instructor*: M. Samadzadeh *Office*: 215 MSCS *Phone*: 744-5674

*Office Hours*: 11:30-12:15 Monday, Tuesday, Wednesday, Thursday, or by appointment if necessary

*Prerequisite*: CS 5313, Formal Language Theory

*Primary Text*:

Steven Homer and Alan L. Selman, *Computability and Complexity Theory*,
Springer-Verlag, Inc., New York, NY, 2001.

*Optional/Recommended Texts, etc.*:

**Introductory References:**

· Henry Hamburger and Dana Richards, *Logic and Language Models for
Computer Science*, Prentice Hall, Upper Saddle River, New Jersey, 2002.

· A. K. Dewdney, *The New Turing Omnibus: 66 Excursions in Computer
Science*, A W. H. Freeman / Owl Book, Henry Holt and Company,
New York, NY, 1989.

· John C. Martin, *Introduction to Languages and the Theory of
Computation*, Third Edition, McGraw-Hill, Inc., New York, NY, 2003.

· R. McNaughton, *Elementary Computability, Formal Languages,
and Automata*, Prentice-Hall Inc., 1982.

· Dexter C. Kozen, *Automata and Computability*, Springer-Verlag,
Inc., New York, NY, 1997.

· Peter Linz, *An Introduction to Formal Languages and Automata*,
2nd Edition, D. C. Heath and Company, Lexington, Massachusetts, 1996.

· John E. Savage, *Models of Computation: Exploring the Power of
Computing*, Addison Wesley Longman, Inc., Reading, Massachusetts, 1998.

· Peter J. Denning, Jack B. Dennis, and Joseph E. Qualitz,
*Machines, Languages, and Computation*,
Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1978.

· Daniel A. Cohen, *Introduction to Computer Theory* (Revised Edition),
John Wiley & Sons Inc., New York, NY, 1991.

· Neil D. Jones, *Computability and Complexity from a Programming
Perspective*, Academic Press, The MIT Press, Cambridge, Massachusetts, 1997.

· D. Wood, *Theory of Computation*, Harper & Row Publishers, 1987.

· B. M. E. Moret and H. D. Shapiro, *Algorithms from P to NP: Volume 1
Design and Efficiency*, The Benjamin/Cummings Publishing Company, Inc.,
Redwood City, California, 1991.

· M. L. Minsky, *Computation: Finite and Infinite Machines*,
Prentice-Hall Inc., 1967.

· Martin D. Davis and Elaine J. Weyuker, *Computability. Complexity, and
Languages: Fundamentals of Theoretical Computer Science*, Academic Press,
Inc., Orlando, Florida, 1983.

· Eitan M. Gurari, *An Introduction to the Theory of Computation*,
Computer Science Press, Rockville, MD, 1989.

· Thomas A. Sudkamp, *Languages and Machines: An Introduction
to the Theory of Computer Science*, 2nd Edition, Addison-Wesley
Longman, Inc., Reading. Massachusetts, 1997.

· J. M. Brady, *The Theory of Computer Science: A programming Approach*,
Chapman and Hall, 1977.

· Robert W. Floyd and Richard Beigel, *The Language of Machines: An
Introduction to Computability and Formal Languages*, Computer Science
Press, An Imprint of W. H. Freeman and Company, New York, NY, 1994.

· Harry R. Lewis and Christos H. Papadimitriou,
*Elements of the Theory of Computation*, 2nd Edition,
Prentice-Hall, Inc., Upper Saddle River, New Jersey, 1998.

· Michael Sipser, *Introduction to the Theory of Computation*,
PWS Publishing Company, an International Thomson Publishing (ITP) Company,
Boston, Massachusetts, 1997.

**Advanced References:**

· Rudolph Sommerhalder and S. C. van Westrhenen, *The Theory of
Computability: Programs, Machines, Effectiveness and Feasibility*,
Addison-Wesley Publishing Company, Inc., Workingham, England, 1988.

· Carl H. Smith, *A Recursive Introduction to the Theory of
Computation*, Springer-Verlag, New York, 1994.

· Robert I. Soare, *Recursively Enumerable Sets and Degrees: A
Study of Computable Functions and Computably Generated Sets*,
Springer-Verlag, Heildelberg, Germany, 1987.

· Seymour Ginsburg, *The Mathematical Theory of Context-Free
Languages*, McGraw-Hill Book Company, New York, NY, 1966.

· N. Cutland, *Computability*, Cambridge University Press, 1980.

· J. Glenn Brookshear, *Theory of Computation: Formal Languages, Automata,
and Complexity*, The Benjamin/Cummings Publishing Company, Inc.,
Redwood City, California, 1989.

· S. Barry Cooper, *Computability Theory*,Chapman & Hall/CRC,
Washington, D.C., 2004.

· Martin Davis, *Computability and Unsolvability*, McGraw-Hill Book
Company, Inc., New York, NY, 1958.

· Roza Peter, *Recursive Functions in Computer Theory* (translated
by: I. Juhasz), Halsted Press: a division of John Wiley & Sons,
Chichester, New York, 1981.

· Walter S. Brainerd and Lawlrence H. Landweber, *Theory of
Computation*, John Wiley & Sons, Inc., New York, NY, 1974.

· Arto Salomaa, *Jewels of Formal Language Theory*, Computer Science
Press, Inc., Rockville, Maryland, 1981.

· Hartley Rogers, Jr., *Theory of Recursive Functions and Effective
Computability*, McGraw-Hill Book Company, Inc., New York, NY, 1967.

· K. Weihrauch, *Computability*, Springer-Verlag, 1987.

· S. C. Kleene, *Introduction to Metamathematics*, Van Nostrand
Co., Inc., Princeton, New Jersey, 1950.

· Michael A. Harrison, *Introduction to Formal Language Theory*,
Addison-Wesley Publishing Company, Inc., Reading, Massachusetts, 1978.

· Raymond M. Smullyan, *Godel's Incompleteness Theorems*, Oxford
University Press, Oxford, England, 1992.

· Raymond M. Smullyan, *Diagonalization and Self-Reference*, Oxford
University Press, Oxford, England, 1994.

**Journals and Conferences/Symposia/Workshops:**

· *Journal of Symbolic Computation*.

· *ACM Transactions on Computational Logic (TOCL)*.

· *Journal of Computational Complexity*.

· *The Journal of Functional Programming*.

· *Mathematical Structures in Computer Science*.

· *Theoretical Computer Science (TOC)*.

· *Parallel Computing*.

· *SIAM Journal on Computing*.

· *Acta Informatica*.

· *Combinatorica*.

· *SIAM Journal on Discrete Mathematics*.

· SIGACT News, *ACM Special Interest Group on Algorithms and Computation Theory*.

· International Symposium on Theoretical Aspects of Computer Science (STACS).

· International Symposium on Mathematical Foundations of Computer Science (MFCS).

· ACM Symposium on Theory of Computing (STOC).

· Symposium on Foundations of Computer Science (FOCS)

· International Conference on Developments in Language Theory (DLT)

· The European Joint Conferences on Theory and Practice of Software (ETAPS)

· International Conference on Compiler Construction (CC)

· International Workshop on Termination (WST)

· European Symposium on Programming (ESOP)

· Fundamental Approaches to Software Engineering (FASE)

· Foundations of Software Science and Computation Structures (FOSSACS)

· Tools and Algorithms for the Construction and Analysis of Systems (TACAS)

· Automated Verification of Infinite-State Systems (AVIS)

· Coalgebraic Methods in Computer Science (CMCS)

· Compiler Optimization Meets Compiler Verification (COCV)

· Fixed Points in Computer Science (FICS)

*Course Description*: Effectiveness, primitive recursivity, general
recursibility, recursive functions, equivalence of computability,
definitions, decidability, and recursive algorithms. Same course as MATH 5663.

*Grading*: Homeworks and Programs 30%

Tests (2) 20% each

Final Examination 30%

*Letter Grades*: [90-100] A, [80-90) B, [70-80) C, [60-70) D, [0-60) F

*Notes*:

**(1)** Homeworks and Programs are due at the beginning of class on the
date they are due (unless announced in class otherwise). Late Homework will
not be accepted. Late Program penalty is 10% per calendar day, according to the
date and time on the printout. Only when verifiable extenuating circumstances
can be demonstrated will make-up exams or extended assignment due dates be
considered. Verifiable extenuating circumstances must be reasons beyond control
of the students, such as illness or accidental injury. Poor performance in class
is not an extenuating circumstance. Advise your instructor of the verifiable
extenuating circumstances in advance or as soon as possible. In such
situations, the date and nature of the make-up exams and the extended due
dates for the assignments will be decided by the instructor.

**(2)** A general point about homeworks and tests:
It is understood and it is always the case that you must justify your
answers, show all your work, and state your assumptions on all problems and
exercises in the homeworks and examinations. A correct answer with no
justification and no work shown may be worth much less than a wrong
answer with full justification and having shown all the work.

**(3)** Cell phones should be turned off during class and in examination
sessions. Laptop usage is not allowed in class unless a clear and convincing
case is made for the use of one.

*Attendance Policy:* Attendance is strongly encouraged, but not required
or monitored. Students are responsible for all material covered in class. Some
of the material covered in class will not be in the required text book.
Announcements about assignments, project due dates, etc. will be made in
class and/or by email. Students are to check their emails regularly using
their class accounts, i.e., userid@cs.okstate.edu. Students are responsible
for all announcements made in class and/or by email. You are to either check
your class account email regularly or put an appropriate forwarding
mechanism in place to get your class-related email.

**Collaboration Policy for CS 5663**

*Homework*: Discussion of any kind is allowed. After discussion,
each student must write up his/her own solution. Copying another student's
work is not allowed. Giving another student your work is considered cheating
as well.

*Programs*: Discussion of techniques in a natural language (such as English)
is allowed, but a discussion in a computer or algorithmic language is not
allowed. Computer language discussions and questions are to be limited to
the language and should not concern the assignment. Stealing, giving or
receiving any code, drawings, diagrams, texts or designs is not allowed.
Every line of work that you turn in must be your own.

*Term Papers*: Discussion of any kind is allowed. After discussion,
each team must write up its own report. Copying another team's work is not
allowed. Giving another team your work is considered cheating as well.
Plagiarism will be severely penalized. Conventional rules of quoting,
referencing, and crediting sources of ideas and wordings apply.

*Examinations*: No discussion of any kind (except with the instructor)
is allowed. No access to any type of written material is allowed.

Students who **do not** comply with the described collaboration policy
will receive a grade of F in the course. Furthermore, the case will be
reported to the University Officials.

**Attachments:**

· Computer Science Department General Computer Use and Misuse Policy

· Academic Dishonesty Policy

· Disabilities Act

· Spring Semester 2005 Calendar

· Oklahoma State University Syllabus Attachment for Spring 2005