Title
Using Computer Programs and Search Problems for Teaching Theory of Computation
Document Type
Article
Publication Date
10-2020
Department
Computer Science
Language
English
Publication Title
Communications of the ACM
Abstract
The theory of computation is one of the crown jewels of the computer science curriculum. It stretches from the discovery of mathematical problems, such as the halting problem, that cannot be solved by computers, to the most celebrated open problem in computer science today: the P vs. NP question. Since the founding of our discipline by Church and Turing in the 1930s, the theory of computation has addressed some of the most fundamental questions about computers: What does it mean to compute the solution to a problem? Which problems can be solved by computers? Which problems can be solved efficiently, in theory and in practice?
DOI
10.1145/3382036
Recommended Citation
MacCormick, John. "Using Computer Programs and Search Problems for Teaching Theory of Computation." Communications of the ACM 63, no. 10 (October 2020): 33-35. https://cacm.acm.org/magazines/2020/10/247591-using-computer-programs-and-search-problems-for-teaching-theory-of-computation/fulltext
Comments
For more information on the published version, visit ACM's (Association for Computing Machinery) Website.