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 Dodaje: sv:Church-Turings hypotes
Addbot (razgovor | doprinos)
m Bot: migracija 27 međuwiki veza sada dostupnih na stranici d:q309157 na Wikidati
Red 8: Red 8:
[[Kategorija:Teorija računanja]]
[[Kategorija:Teorija računanja]]


[[bg:Тезис на Чърч]]
[[ca:Tesi de Church-Turing]]
[[cs:Churchova-Turingova teze]]
[[da:Church-Turing-tesen]]
[[de:Church-Turing-These]]
[[en:Church–Turing thesis]]
[[eo:Ĉurĉa tezo]]
[[es:Tesis de Church-Turing]]
[[et:Churchi tees]]
[[fa:تز چرچ-تورینگ]]
[[fi:Churchin–Turingin teesi]]
[[fr:Thèse de Church]]
[[he:תזת צ'רץ'-טיורינג]]
[[hr:Church-Turingova teza]]
[[hu:Church–Turing-tézis]]
[[it:Tesi di Church-Turing]]
[[ja:チャーチ=チューリングのテーゼ]]
[[ko:처치-튜링 명제]]
[[lt:Tiuringo mašina#Tiuringo tezė]]
[[lt:Tiuringo mašina#Tiuringo tezė]]
[[nl:Church-Turing-hypothese]]
[[pl:Hipoteza Churcha-Turinga]]
[[pt:Tese de Church-Turing]]
[[ru:Тезис Чёрча — Тьюринга]]
[[simple:Church-Turing thesis]]
[[sv:Church-Turings hypotes]]
[[tr:Church-Turing tezi]]
[[uk:Теза Черча]]
[[zh:邱奇-图灵论题]]

Verzija na datum 11 mart 2013 u 13:50

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.