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?

Comments

For more information on the published version, visit ACM's (Association for Computing Machinery) Website.

DOI

10.1145/3382036

Full text currently unavailable.

COinS