Teaching Theory of Computation in the STEM K-12 Curricula Through Impossibility and Undecidability Problems

Abstract

Theoretical Computer Science is a challenging subject to motivate and teach, particularly for students at the beginning of their Computer Science education. Introducing this topic at the high school level within the framework of STEM K-12 curricula (Science, Technology, Engineering, Mathematics), and linking real-world problems from these areas to core theoretical concepts, may make theory of computation more approachable for students prior to college. This paper presents a pedagogical approach for integrating theory of computing topics into STEM K-12 courses. It includes a set of classroom activities based on the Collatz conjecture, Feynman’s infinite ladder of resistances, and polyomino tiling inspired by Penrose’s cosmological models. These activities combine computational experimentation in Python with conceptual discussion to help students distinguish between different sources of computational limits, including chaotic unpredictability, mathematical impossibility, and algorithmic undecidability. While the problems and activities are primarily embedded in mathematics and physics courses, they are clearly connected to computational challenges across other STEM K-12 disciplines. To evaluate the effectiveness of this methodology, we analyze experimental data showing that introducing theoretical computing concepts, particularly those related to impossibility and undecidability, can enhance students’ academic performance and motivation, compared to traditional K-12 programming courses.