ABSTRACT
Generalization is commonly promoted as a key problem solving technique within the field of computing, and an understanding of the theory of computation provides important depth and insight within the generalization process. Since the shaping of a course and a curriculum should reflect educational priorities and objectives, a discussion of theory naturally turns to consideration of desired skills and background for our graduates. A full course on the theory of computation can provide depth, intuition, and skill together with extended consideration of the following: models of computation, limits of computing, responses to limits, connections between theory and applications, student construction of logical arguments, and communication skills. Students engage contrasting models of computation, determine what problems each model can and cannot solve, consider when models are equivalent or not equivalent, etc. Finally, the study of theory can help students relate their careful reasoning for coding to the more general context of logical reasoning and its presentation orally or in writing.
