La diagonale

let diagonale p =
  if arrete p p then (while true do () done) else ()

Notons $D$ le programme diagonale. Que fait diagonale D ? Par définition, elle teste arrete D D.

• Cas arrete D D = true : cela signifie « $D$ appliqué à $D$ s'arrête ». Or, dans ce cas, diagonale D entre dans while true : elle ne s'arrête pas. Contradiction avec true.

• Cas arrete D D = false : « $D$ appliqué à $D$ ne s'arrête pas ». Or diagonale D prend alors la branche else et s'arrête. Contradiction avec false.

arrete ne peut donc renvoyer ni true ni false de façon cohérente : elle ne peut exister.