Les énoncés dont on ne peut prouver ni qu'ils sont vrais ni qu'ils sont faux semblent moins rares qu'on ne l'imaginait : de tels « indécidables », redoutés par les mathématiciens, ont été trouvés avec des problèmes portant sur de petites machines de Turing.