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.
|
|