Toward an intutive and interesting theory course: the first step of a road map
John L. Lowther, Ching-Kuang Shene · Journal of computing sciences in colleges · 2004
This paper presents the first step of an attempt in designing intuitive and interesting materials for a theory course. The materials developed cover the AL5 Basic Computability unit of the ACM/IEEE Computing Curricula 2001, and can be used in a stand-alone theory course. This paper describes a approach to basic computability. Topics include a proof of the Halting Problem and the use of a simple reduction technique to prove other interesting problems. Details of the chosen computation model, the construction of a universal program, and the Isomorphism Theorem are also discussed. Future topics for this course include advanced computability, computability with real numbers, and the connection between theory and programming languages.