Dipende da cosa si intende con "semplice", esistono teorie elementari che sono incomplete, ad esempio quella dei gruppi, ma non per il fenomeno messo in luce da Gödel; e dipende anche da cosa si intende con "enunciato di Gödel". Gli enunciati di Gödel non sono importanti in sé, ma per quello che dicono sulle teorie, in una interpretazione metamatematica. Il loro carattere fondamentale è l'autoriferimento, che non è misterioso e si realizza spesso e naturalmente, ad esempio nella teoria e nella pratica dei computer, quando un programma tratta un altro programma, o se stesso, come un dato.
Il più semplice esempio è l'indecidibilità del problema dell'halt per macchine, o per algoritmi. Gli algoritmi (o i programmi per calcolare funzioni; limitiamoci a quelle aritmetiche a un argomento) si possono enumerare in modo effettivo (per lunghezza e ordine alfabetico): M₁, M₂, ...
Ognuno è individuato dal suo indice di posizione nella enumerazione. Scriviamo M_n(m) per indicare l'applicazione dell'algoritmo M_nall'input m, applicazione che dà un numero se il calcolo termina (si ferma) o può andare avanti all'infinito (si pensi a dividere certi numeri dispari per 2 per esempio). Supponiamo di voler decidere se un qualunque algoritmo applicato a un qualunque numero si ferma o meno, e con un metodo a priori effettivo, quindi ancora con un algoritmo.
Supponiamo che esista un tale algoritmo; ne esiste allora anche uno che indichiamo con M tale che per ogni n, risulti M(n) = 0 se M_n(n) non si ferma e M(n) =1 se M_n(n) si ferma. Si realizzerebbe allora facilmente un altro algoritmo M^' tale che M^'(n) = 0 se M_n(n) non si ferma, e M^'(n) non si ferma se M_n(n) si ferma (basta aggiungere a M poche istruzioni in modo che quando M(n) arriva a 1 scatta un ciclo).
Ora è fatta. Se M^' è un algoritmo, è uno della nostra lista precedente, poniamo quindi M^' = M_r. Ma ora si vede subito che M_r(r) non può né fermarsi né non fermarsi.
Dunque il problema dell'halt non è risolubile in modo effettivo. Con un ragionamento analogo si prova che non è possibile trovare una volta per tutte un programma che sia un anti-virus universale.