The Halting Problem

CS0

Abstract

This POGIL activity is intended for the end of a CS0 or introductory computer science course in which students have already explored algorithms to solve many kinds of problems. The purpose of this activity is for groups to demonstrate to themselves that there are in fact limits on the kinds of problems computers can solve. The classical example of such a problem is the Halting Problem: Given an algorithm, determine if the algorithm will halt on a given input. Groups are guided to the conclusion that an algorithm for the Halting Problem cannot exist through a process of thinking critically about model algorithms and what they do. Learning objectives include using an algorithm as input to an algorithm, recognizing an infinite loop, and explaining why the Halting Problem cannot be solved.

This activity was developed with NSF support through IUSE-1626765. You may request access to this activity via the following link: IntroCS-POGIL Activity Writing Program. 

• Level: Undergraduate
• Setting: Classroom
• Activity Type: Learning Cycle
• Discipline: Computer Science
• Course: CS0
• Keywords: Algorithms, decidability, halting problem