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.
http://www.pourlascience.fr/ewb_pages/a/article-des-indecidables-a-portee-de-main-37513.php