Macchine di Turing potenzialmente universali

Quando si parla delle macchine di Turing si parla anche di macchine di Turing potenzialmente universali: con questa espressione si suole indicare quelle macchine che sono in grado di calcolare tutte le funzioni calcolabili da ogni macchina di Turing, ossia in grado di simulare fedelmente il comportamento di una qualsiasi macchina di Turing.
Per concludere vanno messe in luce le motivazioni che portarono alla tesi di Church-Turing; principalmente il motivo che spinse alla formulazione di tale tesi fu l’esigenza di generalizzare i teoremi di incompletezza scoperti da Godel nel 1931.
Secondo quanto afferma questo studioso infatti è impossibile trovare un procedimento algoritmico che consenta di generare al contempo tutti gli enunciati veri dell’aritmetica elementare senza che si generi nessun enunciato falso.
Questo problema però neanche la tesi Church-Turing è riuscita a risolverlo; ciò significa che non è possibile attraverso procedimenti algoritmici generare tutti gli enunciati dell’aritmetica che siano veri (se così fosse il procedimento algoritmico sarebbe incompleto).
Questo in ultima analisi significa che nell’ambito dell’IA o ci si accontenta dell’incompletezza delle operazioni che una macchina può compiere o si deve ammettere la sua fallibilità.