Actually this is only a paradox if we assume that it is impossible for the barber to lie. Just because the barber's sign STATES they "shave anyone who does not shave themselves and no one else" doesn't necessarily mean that IS the case. You might call that the Madison Avenue theory, or the P.T. Barnum... ;)