Suppose there is a town where a man has set up shop as a barber. This barber shaves all men, and only the men, who do not shave themselves.
Does the barber shave himself?
This type of puzzle is known as a paradox. Think of the men in this town as belonging to 2 sets: the set of men who shave themselves, and the set of men who do not shave themselves. (There is no third set!) If the barber belongs to the first set (men who shave themselves), then, by the above described circumstances, he does not shave himself. So he belongs to the second set. But if he belongs to the second set, then by the same described circumstances, he must shave himself. So the answer is neither yes nor no.
The only solution to the above puzzle is the realization that the above described situation cannot exist.
The barber puzzle was devised by the English mathematician and philosopher Bertrand Russell to help explain a paradox he discovered in set theory.
First consider: most sets are not elements of themselves, but some are. For example, the set of all trees is not a tree, nor is the set of all languages a language. However, think of a list of all lists (which is a list), or the set of all abstract ideas, which is itself also an abstract idea.
Now suppose there is a set S, which is composed of all sets which are not elements of themselves. If S is not an element of itself, then it belongs in the set. But if S is in the set, then it is an element of itself and does not belong.
One solution to this problem is to require that
any set defined by a predicate also be a subset of a known set.
(The exception to this is the power set.) Since the set of "sets which
are not elements of themselves" is not known, it must be made a subset
first of some other known set. For example, let U
be a set of sets, and let A be any set which belongs to U
and is not an element of itself. Now define S as:
S = {A 
U
| A 
A}.
Now the question can be asked; is S an element of itself? The answer
is no. If S S,
(S belongs to the set of sets which are not elements of themselves),
it now satisfies it's own defining property, and therefore SS.
If you have had any experience with computers, you are by now aware of the concept of an "infinite loop." In fact, if you happen to be getting your degree in one of the computer sciences, you know that handing in a program with an infinite loop is not a good idea! What you (and the world in general) need is a program that takes as input another program and a data set, and produces as output one of 2 messages: Either "This program will halt on the input data." or "This program will loop forever on the input data."
This is the essence of the Halting Problem. Is there an algorithm which, given another algorithm and a data set, will determine whether or not the input algorithm will halt or loop forever?
Alan Turing proved that the answer is no, using the following reasoning.
Suppose there is an algorithm called "Halt", which when given as input a program P and data set D:
Halt(P, D) prints:
"halts" if P will halt after a finite number of steps on data D; or
"loops forever" if P loops forever on data D.
Since the characters which make up a program can also be used as a data set, it is possible to run Halt(P, P). So, it should be possible to define a new algorithm, TestHalt, which does the following:
On any input algorithm P:
TestHalt(P)
loops forever if Halt(P, P) prints "halts"; or
stops if Halt(P, P) prints "loops forever".
But what if you try running TestHalt on itself?
If TestHalt(TestHalt) terminates after a finite number of steps, then Halt(TestHalt, TestHalt) prints "halts" and TestHalt(TestHalt) will loop forever. (?!)
If TestHalt(TestHalt) loops forever, then Halt(TestHalt, TestHalt) will print "loops forever", and TestHalt(TestHalt) will terminate after a finite number of steps. (Again, ?!)
Remember, this begins with the assumption that there exists an algorithm which can determine whether or not another algorithm will halt or loop infinitely on a given data set. But since this assumption has led to a contradiction -- TestHalt(TestHalt) will both stop and loop forever -- the original assumption must be false. Like the Barber Puzzle and Russell's Paradox, this situation cannot exist in the world as we currently know it, and therefore there cannot be a Halting algorithm.
