Ĉurĉa tezo

El Vikipedio, la libera enciklopedio

La Ĉurĉa tezo (aŭ Ĉurĉ-Turinga tezo) estas tezo pri komputeblaj funkcioj. Simple dirite, ĝi asertas ke ĉiu funkcio kiu estas algoritme komputebla (en intuicia senco de "algoritme komputebla") estas komputebla de Turinga aŭtomato. Ĉar ĝi parolas pri intuicia nocio, ĝi ne estas matematike preciza tezo kaj sekve ne pruveblas. La tezo estiĝis, ĉar diversaj formaligoj de la ideo de algoritma komputebleco estis pruveble egalvaloraj. Ĝi estis unue vortigita de Alonzo Ĉurĉo.