The low academic results traditionally obtained by students during their learning of theoretical computer science, often due to its high level of abstraction and mathematical content, have been one of the reasons why many students decide to postpone its study until it is absolutely necessary. For this reason, some optional theoretical subjects have been postponed for the last years, and in some cases, have not been finally included in the curricula due to lack of students interested in taking them. To reverse this problematic situation in the teaching of theoretical computer science, it is essential that students acquire, as soon as possible, an intuitive and progressive knowledge of the main concepts of theoretical computer science and its associated skills and abilities, with more current motivations and implications in the real world. To achieve this goal, in this paper, we explore the use of impossibility and undecidability results that in recent years have appeared in the world of physics to present, introduce, and interrelate ideas about theoretical computation and its associated computational thinking in the first years of undergraduate science and engineering degrees. To provide evidence of the impact of the applicability of the proposed methodology, we analyze the experimental results and student feedback we have obtained to confirm that the introduction of theoretical computational questions from impossibility and undecidability problems in physics increases students’ academic results in theoretical computer science subjects.