Paradoxo do barbeiro

O paradoxo do barbeiro é um paradoxo que relaciona lógica matemática e teoria de conjuntos. O paradoxo considera uma aldeia onde, todos os dias, um barbeiro faz a barba de todos os homens que não se barbeiam sozinhos e não faz a barba de quem se barbeia sozinho. Isso vale para todos que estão na aldeia. Ora tal aldeia não pode existir:

• Se o barbeiro é um homem que não se barbeia sozinho, então ele deve fazer a barba a si mesmo imediatamente, tornando-se um homem que se barbeia sozinho.
• Se agora ele é um homem que se barbeia sozinho, então ele deve parar imediatamente de fazer a própria barba, tornando-se um homem que não se barbeia sozinho.

A regra resulta num paradoxo, pois o barbeiro ao mesmo tempo deve e não deve fazer a própria barba, não podendo se decidir sem quebrar a regra.

O paradoxo costuma ser atribuído a Bertrand Russell, um matemático britânico que em 1901 elaborou o paradoxo de Russell para demonstrar a natureza auto-contraditória da teoria de conjuntos de Georg Cantor. O paradoxo é também usado no teorema da incompletude de Gödel bem como na prova da indecidibilidade do problema de paragem de Alan Turing.

Linguagens de programação

Em Prolog, as condições que levam ao paradoxo do barbeiro podem ser expressas pela cláusula auto-referente:

barbeia(barbeiro,X) :- homem(X), not(barbeia(X,X)).

homem(adao).

onde a negação por falha é pressuposta. Assim, a clausula

barbeia(barbeiro,adao).

será provada como verdadeira, já que barbeia(adao,adao). não pode ser provado. No entanto, com:

homem(barbeiro).

cria-se um loop infinito.

Variante: morte por enforcamento ou decapitação

Uma outra versão conta a história de um filósofo que cometeu algum crime muito grave (por exemplo, olhou para uma das esposas do Rei), e deve ser executado. O Generoso Rei, porém, permite que ele escolha se quer ser enforcado ou decapitado (ou poderia ser queimado vivo ou crucificado), desde que ele diga uma verdade ou uma mentira. O filósofo, então, diz Eu serei decapitado.