Dans un système formel F, on se demande si on peut trouver une preuve de l'énoncé math S t.q. le nb de symboles de la preuve < n. Le problème est décidable, il faut chercher la preuve dans tout le code de F dont les cordes (bit-strings) < n (c'est comme...

Une machine de Turing peut vérifier qu'elle fait telle opération A (par exemple afficher la 3000e décimale de pi) en donnant une suite d'états ou d'opérations qui aboutit à telle opération A mais elle ne peut vérifier qu'elle est dans tel état B parce...