Church-Turingova teza – razlika između verzija

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretragu
Uklonjeni sadržaj Dodani sadržaj
m r2.7.1) (robot Mijenja: eo:Ĉurĉa tezo
Xqbot (razgovor | doprinos)
m r2.7.3) (robot Mijenja: zh:邱奇-图灵论题
Red 34: Red 34:
[[tr:Church-Turing tezi]]
[[tr:Church-Turing tezi]]
[[uk:Теза Черча]]
[[uk:Теза Черча]]
[[zh:邱奇-图灵论题]]
[[zh:邱奇图灵论题]]

Verzija na datum 6 juni 2012 u 18:41

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.