More actions
Bot: Automatski unos stranica |
m bnz |
||
Redak 1: | Redak 1: | ||
U [[teorija izračunljivosti (računarstvo)|teoriji izračunljivosti]], '''Church-Turingova teza''' (poznata i kao '''Churchova teza''', '''Churchova konjektura''' te '''Turingova teza''') je [[hipoteza]] o prirodi [[računalo|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 [[algoritam|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 [[algoritam|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 ([[Turingov stroj|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. | Neformalno, '''Church-Turingova teza''' iskazuje da se intuitivna predodžba [[algoritam|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 ([[Turingov stroj|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. |
Posljednja izmjena od 8. svibanj 2022. u 15:46
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.
Nedovršeni članak Church-Turingova teza koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.