Purpose of the course:This course is designed to complement the material learned in COT 4420, Theory of Computation, to create a well-rounded and rigorous treatment of topics in the Theory of Computation. The undergraduate class dealt with formal languages and automata, while this course deals with computability theory. Classic computability theory is defined by what abstract machines, i.e. Turing and Post machines, are capable of computing. In this course we develop this same material using a very simple programming language first developed by Martin Davis. The approach is very rigorous, yet the use of a programming language is much more intuitive than the classical approach using Turing machines. Students are expected to master many sophisticated concepts, and will be asked to show their mastery with problems and in-class tests that will include technical proofs. Material covered in the course will include:
Besides the required textbook for this course, but here are a list of several books that cover important material for this course. The books are listed in the order of relevance as determined by the instructor:
Meeting Place:Dirac Science Library (DSL) 499
Office Hours:I am either in my 498 DSL office or my Love 207 office and my office hours are 9:30-10:30AM on Tuesdays and Thursdays
The notes for the course can be found
Michael Mascagni, Ph.D.
Professor of Computer Science
Professor of Mathematics (Courtesy)
Professor of Scientific Computing (Courtesy)
Faculty in the Graduate Program in Molecular Biophysics
Florida State University
Tallahassee, FL 32306-4530
Office: Dirac Science Library 498/Love 207
For the curious, here are links to a brief
biography of the Professor, and the Professor's home page.
Warning and Encouragement:
The students are warned that by taking this course they are implicitly submitting themselves in the role of instructional "Guinea Pigs." As such, your constant input is not only permitted, but strongly encouraged. Feel free to speak up in class, to visit me in my office with your opinions and criticisms, or to e-mail me with ideas on how to improve this class.
The course will have an in-class mid-term exam, a take home final and a set of three assignments.
|In-class Midterm Exam||40%|
The grading scale is the standard scale with +/- being 3 percent.
Academic Honor Code:
Students are expected to uphold the Academic Honor Code published in The Florida State University Bulletin and the Student Handbook. The Academic Honor System of The Florida State University is based on the premise that each student has the responsibility (1) to uphold the highest standards of academic integrity in the student's own work, (2) to refuse to tolerate violations of academic integrity in the university community, and (3) to foster a high sense of integrity and social responsibility on the part of the university community.
Please see the following web site for a complete explanation of
the Academic Honor Code.
Americans with Disabilities Act:
Students with disabilities needing academic accommodation should:
(1) register with and provide documentation to the
For more information about services available to FSU students with disabilities, contact the
Student Disability Resource Center
Dean of Students Department
08 Kellum Hall
Florida State University
Tallahassee, FL 32306-4400
(This syllabus and other class materials are available in alternative format upon request.)