The Halting Problem

The Halting Problem [Wiki Link] is one of the most classic and well-known problem in computational theory. It can be stated as “Given the description of any computer programs, decide whether the programs continue running forever or finish running”. In other words, given a computer program (and input), you will need to decide if it halts or runs forever.

For example, the following halts quickly.

print "Hello from Python"

But this is not.

while True:
    print "Never stops"

In 1936, Alan Tuning proved that a general algorithm that solves the halting problem for all possible program input does not exist. The Halting Problem is ‘ undecidable ‘ over Tuning machines.

For instance, given the follow function P which takes two parameters: S and I that represents the source and input respectively.

def P(S, I):
	if halting(S, I): # return True if program S with input I halts
		while True:
			pass
	else:
		return 0  # Halts

The function halting will return True if the program S with input I halts and False otherwise.

What happens if you invoke P with its source (itself) and using the same as input? If it halts, it will enter an infinite loop. If it runs forever, then halts immediately. This is a paradox.

The following is a quite similar situation.

In the village, there is a barber, who only cuts hair for people that don’t cut his/her hair. So the paradox is that will the barber cut hair for himself?

References:

[1] http://en.wikipedia.org/wiki/Halting_problem

–EOF (The Ultimate Computing & Technology Blog) —