TESI di CHURCH-TURING

Ipotesi indimostrabile, elaborata del tutto indipendentemente e attraverso percorsi diversi, da Alonzo Church e Alan Turing. Secondo tale ipotesi, se un problema pu˛ essere ridotto in una serie finita di passi elementari, allora esisterÓ una macchina di Turing in grado di risolverlo.