Theoretical Computer Science Education from Impossibility and Undecidability Problems in Physics
Rafael del Vado Vírseda · 2023
Classroom examples of non-computable problems most often involve sets of Turing machines, which makes these problems too abstract and far divorced from real-world practice, so some students are turned off by the abstract nature of theoretical CS. In this paper, we explore the pedagogical connection of undecidability results in theoretical computing with similar (un)computability results in physics that have recently appeared. We argue that incorporating these new impossibility and undecidability results can increase students' interest in theoretical computing topics, as well as improve their understanding of the underlying science and mathematics.