CSC460 Theory of Computation (Spring 2005)


On-line Resources (required reading)

Catalog Course Description

This course focuses on the traditional, algorithmic theory of computation consisting of three subareas: (1) computability, (2) complexity theory, and (3) formal languages and automata. The topics include: Turing machines, decidability/undecidability, reducibility, Church-Turing thesis, context-free grammars/languages, push-down automata, finite automata, regular expressions/languages, and time/space complexity including NP-completeness. [Prerequisites: CSC310, CSC340]

Learning Goals

In this course, we examine a small number of general principles that lie behind a variety of computational phenomena so that we will be able to apply these principles to a broad range of real-world computation. One of the main goals of this course is to convince students that "theory" is useful for practically anyone. To do so, we need to observe examples of theory at work. Once we understand the benefits of using theory in general, we will be ready to explore Theory of Computation, which has always been behind the development of computer science. At the same time, we will also examine the limitations of Theory and identify what is really behind real-world computation. In this course, we will discuss most of the topics traditionally covered in an undergraduate-level Theory of Computation course. However, our approach will be to explore the possibility of applying Theory to practical problems which students are interested in. The course will not follow the textbook, nor will it do most of the textbook problems.

Content Goals (mastery of the following core concepts, deep understandings, misunderstandings, and technical knowledge)

  1. Practical problems can often be transformed into research and computational problems. Every problem is associated with cost/significance, which is relative to the evaluator. Computational problems can be represented as a set, readily available as the input to computational processing. [problem]
  2. A theory is a potentially infinite, consistent body of knowledge which can be systematically derived from a small number of abstract principles. The gap between the principles and the entire information is the source of the theory's predictive power. Also being abstract, a theory can be applied to a broad range of phenomena, which might appear distinct. [theory]
  3. Interactive computation subsumes algorithmic computation, but not vice versa. That is, there is a qualitative difference between these two modes of computation. [interactive computation]
  4. The algorithmic notion of computation can be represented in a variety of equivalent forms, which define a bounded class of sets. That is, there is a limit to algorithmic computation. [computability]
  5. The computable class of sets contains a hierarchy of proper subsets which can be characterized by distinct grammars and automata. [formal languages and automata]
  6. The practicality of an algorithm depends on its complexity relative to the input data size. [complexity]
  7. Power set, also encompassing the distinction between determinism and nondeterminism, can introduce discontinuity with respect to computability and complexity. [power set]

Performance Goals (expected outcomes and abilities to be observed as a result of successful learning)

  1. Identify real-world problems which are relevant to the student's life and can be tackled by computational means. [awareness]
  2. Transform real-world problems into research problems, and then into computational problems, along with the analysis of the cost/significance of a problem. [transformation]
  3. Analyze computational problems with respect to interactivity, computability, language/automata hierarchy, and complexity hierarchy. Then, evaluate the analysis with respect to its usefulness, correctness, and accuracy. [analysis/evaluation]
  4. Respect, analyze, and give constructive criticisms to the ideas in the literature and those expressed by other people. [critical attitude]
  5. Express ideas orally and in writing, in a manner clearly understood by other students (with equivalent background). Explain your own ideas orally and in writing, clearly and logically. Revise the ideas, reflecting the feedback from other students and the instructor. [communication]
  6. Take initiative in both independent and group activities. Also extend the domain of theoretical inquiry beyond the scope prepared by the instructor. [initiative]
  7. Reflect upon the student's own thinking process and assess the student’s own performance relative to the content and performance goals. [reflection]

Course Modules

This course is divided into the following four modules.

However, the topics of this course cannot be clearly separated into disjoint components. Thus, these modules should not be considered rigidly. Instead, these modules should be considered as evaluation units so that students can check their achievements in a timely manner.


This course is expected to facilitate learning experience with which students can analyze practical computational problems in a intellectual manner by applying principles in Theory of Computation. Therefore, students’ assessment must reflect their ability to do that in a realistic context. Take-home exercises are designed to provide activities reflecting the learning goals (except for Performance Goal 8) in a realistic context. Thus, students’ assessment will primarily based on how well they accomplish these exercises. As for Performance Goal 8, evaluation workshops will provide opportunities for students to reflect upon their thought processes and self-evaluate their achievements with respect to the learning goals.

The main assessment tools are students’ self-evaluation at the end of each module. Students will evaluate themselves with respect to the learning goals following the instructions on the self-evaluation form (preliminary eval form for Module A). Since students will be given the form at the beginning of each module, they will be aware of what they are expected to achieve for that module. The evaluation form will list the learning goals relevant to the module as well as evaluation criteria for the relevant goals. Analysis and reflections on take-home exercises will be most important as the exercises address the learning goals directly or indirectly. Students are also expected to respond to the instructor’s feedback on their take-home exercises. The evaluation workshop will generally include peer discussion sessions, when students can share their learning and evaluation experiences.

The grading scheme for self-evaluation (and the instructor’s adjustment) is as follows:

The grades A, B, and C may be qualified with ‘+’ or ‘-’, where applicable. The overall course grade will be the weighted average of the module grades as shown below (using the standard conversion A = 4.00, A- = 3.67, etc., according to, not

If a student far exceeds the standard, s/he may be assigned an A+. Although there will be no course grade beyond A, an A+ (for a module) could offset, say, A- in another module. For example, if a student receives A, A-, A, and A+ for the four modules, respectively, s/he will receive an A for the course.

After almost every class meeting, there will be take-home exercises. Students are expected to do them and hand them in at the beginning of the next class meeting. Although these exercises will not be graded by the instructor, the instructor will give feedback on them and return them at the beginning of the next class meeting. When students self-evaluate, they will submit all the take-home exercises along with their responses to the instructors’ feedback. After submission of a module evaluation folder (called "portfolio"), the instructor will adjust students’ self-evaluation, provide comments, and temporarily return them to students for review (when possible). Note that all the submitted work will eventually be kept with the instructor.

Learning Activities

The main learning activities consist of class meetings (two 80-minute sessions per week) and take-home exercises (expected amount of work equivalent to 360 minutes per week). Take-home exercises will be given after almost every class meeting and due at the beginning of the next class meeting (unless otherwise stated). Class meetings will contain components such as the following:

Course Topics (subject contents)

  1. Types of problems
    1. Practical, research, and computational problems
    2. Condition and cost/significance of a problem
    3. Set representation of a problem
  2. Notion of "theory"
    1. Applicability of a theory
    2. Definition in the context of mathematical logic
  3. Computability
    1. Formal models of computation, e.g., Turing machines (TMs)
    2. Decidability/undecidability including diagonalization and halting problem
    3. Reduction
    4. Church-Turing thesis
  4. Formal languages and automata
    1. Chomsky hierarchy
    2. Context-free languages (CFL), context-free grammars (CFG), push-down automata (PDA); properties of CFLs
    3. Regular languages, regular expressions (RegExp), finite automata (FA); properties of regular languages
  5. Complexity
    1. Tractability/Intractability
    2. Nondeterministic polynomial
    3. NP-complete
    4. Space complexity
  6. Interactivity
    1. Effects of interaction
    2. Formal models of interaction


Schedule: Class meetings: Tue/Fri 4:00-5:20 p.m. in HH126

Topic Exercises
Introduction Your own computational problems
Problems: Anatomy and physiology [discrete math topics] Using a theory
Theory: Form and content [theory supplemantal notes] Your ideas about Theory of Computation
Theory of Computation: Possibilities and limitations [response to summary questions] Computational problem solving
Turing Machines: Vehicle for mechanistic touring [supplement, binary adder example] Test-drive TMs [JFLAP; local copy/examples]
(Un)Decidability: When to play dice Module A Comprehensive Exercise
Module A Evaluation Workshop [eval form, module review exercise] Simulating a TM using a TM
Universal TM: The art of circularity Universal TM
Diagonalization: Magic of obliqueness Diagonalization practice
Halting Problem: Can we prove that we too will die? Haunting problems
Reduction: How to get more from reduced stuff [response to summary questions] Reduction/Equivalence
Review; Church-Turing thesis: Civil rights movement in its abstract form Module B Comprehensive Exercise
Module B Evaluation Workshop [eval form, review exercise, supplement] The power of TMs (due 3/15)
Computability review [supplement, extra problems (optional)] -
No class (Spring break) -
Chomsky hierarchy: Often, we want less power Chomsky hierarchy
CFG, CFL, PDA: Shopping-mall navigation CF review/practice
Regular expression, regular set, FA: Vending-machine operation Regular practice
Properties of regular sets: Pumping gas for free [supplement on the Pumping Lemma] Pumping practice
Properties of CFLs: Pumping air into the lung; Chomsky hierarchy summary [supplement: response to questions] Module C Comprehensive Exercise
Module C Evaluation Workshop [eval form, review exercise, supplement] Data-size scalability
Complexity: Polynomial, Exponential, Nondeterminism Complexity basics; NP practice [Sample response to Part 1]
NP-complete: Why SAT rules NP/NPC practice; Mini research ideas
Space complexity: Is time the 4th dimension of space? [supplement on QBF and time-space tradeoff] Mini research outline
Parallel processing: What men (male) cannot do well Reading: MacLennan
Super-Turing computation (1): Identifying the TM limits Reading: van Leeuwen & Wiedermann
Super-Turing computation (2): Exceeding the TM limits Module D Comprehensive Exercise
Final Evaluation Workshop [eval form]; Conclusion -
Evaluate CS Practicum Presentations (required; instructions) -
Closing circle (canceled) -

// End