Designing Theory of Computing Backwards
Ryan Edward Dougherty · 2024
The over-arching question that is continually asked in nearly every Theoretical Computer Science (TCS) course is: " what are the limitations of computers?" The motivation is to start with "simple" machines, explore them, and to determine that they are not sufficiently powerful to handle problems that everyday computers can. Then the course would add " computational power" to these machines so that they can more accurately compute answers to problems students should already know how to do with their own machines. Students then learn about decidability and undecidability, and observe that as computer models get more powerful, the fewer questions about them remain decidable, which is a trade-off. One of the main issues with this approach is the justification of which "simple'' machines to consider initially.