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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.