Course Number and Title: CS 5663, Computability and Decidability

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