Church-Turingova teza

U teoriji izračunljivosti, Church-Turingova teza (poznata i kao Churchova teza, Churchova konjektura te Turingova teza) je hipoteza o prirodi računala, kao što je digitalno računalo ili ljudsko biće sa olovkom i papirom, a koji se podvrgavaju skupu pravila. Teza tvrdi da je bilo koji izračun koji je uopće moguć, moguće napraviti algoritmom koji se izvršuje na računalu, uz dostatne vremenske i prostorne resurse. Teza ne može biti matematički dokazana, te se stoga ponekad predlaže kao fizikalni zakon ili kao definicija.

Neformalno, Church-Turingova teza iskazuje da se intuitivna predodžba algoritma može precizirati, te da računala mogu izvršavati te algoritme. Nadalje, računalo teoretski može izvršavati bilo koji algoritam. Drugim riječima, sva uobičajena računala su međusobno ekvivalentna u terminima teoretske računske moći, i stoga nije moguće izgraditi uređaj za računanje koji će biti moćniji od najjednostavnijeg računala (Turingovog stroja). Valja uočiti da ova formulacija moći zanemaruje praktične faktore kao što su brzina ili memorijski kapacitet - razmatra se sve što je teoretski moguće, uz dano neograničeno vrijeme i memoriju.

Tezu je prvi predložio Stephen C. Kleene 1943., ali je imenovana po Alonzu Churchu i Alanu Turingu.