The Halting Problem In Computer Science

Share this post!

Vote this!

One of the most interesting non-programming parts of computer science is the study of what can (and cannot) be computed. For instance, take the question, "does this program complete?" I.e., will it not go into an infinite loop. How would you answer this question, given an arbitrary piece of code? You could try running it. But what if it takes a long time? How long are you willing to wait? Think about whether there is a general solution to this problem -- a method that you could apply to any piece of C code in order to demonstrate that it will eventually come to a stop.

Let's say that you discovered such a solution. It's a program that takes two arguments: the code for a program, and its input. This solution returns true if the program halts on the given input, and false if the program runs forever. Let's call this program DOES-HALT. We can use DOES-HALT as follows: more...