hrcak mascot   Srce   HID

Stručni rad

Izračunljivost i apstraktni strojevi

Marko Doko
Vedran Novaković

Puni tekst: hrvatski, pdf (395 KB) str. 30-48 preuzimanja: 30* citiraj
APA 6th Edition
Doko, M. i Novaković, V. (2006). Izračunljivost i apstraktni strojevi. Math.e, 9, 30-48. Preuzeto s https://hrcak.srce.hr/6217
MLA 8th Edition
Doko, Marko i Vedran Novaković. "Izračunljivost i apstraktni strojevi." Math.e, vol. 9, 2006, str. 30-48. https://hrcak.srce.hr/6217. Citirano 31.07.2021.
Chicago 17th Edition
Doko, Marko i Vedran Novaković. "Izračunljivost i apstraktni strojevi." Math.e 9 (2006): 30-48. https://hrcak.srce.hr/6217
Harvard
Doko, M., i Novaković, V. (2006). 'Izračunljivost i apstraktni strojevi', Math.e, 9, str. 30-48. Preuzeto s: https://hrcak.srce.hr/6217 (Datum pristupa: 31.07.2021.)
Vancouver
Doko M, Novaković V. Izračunljivost i apstraktni strojevi. Math.e [Internet]. 2006 [pristupljeno 31.07.2021.];9:30-48. Dostupno na: https://hrcak.srce.hr/6217
IEEE
M. Doko i V. Novaković, "Izračunljivost i apstraktni strojevi", Math.e, vol.9, str. 30-48, 2006. [Online]. Dostupno na: https://hrcak.srce.hr/6217. [Citirano: 31.07.2021.]

Sažetak
U ovom članku razmatramo neke od apstraktnih modela izračunavanja, dokazujemo njihovu ekvivalenciju i uspostavljamo vezu sa stvarnim računalima. Prema Church-Turingovoj tezi, intuitivni pojam izračunljivosti odgovara tim modelima, tj. problem ima algoritamsko rješenje točno onda kad se ono može ostvariti na nekom od njih. U članku pokazujemo da postoje problemi koji se ne mogu riješiti i funkcije koje se ne mogu izračunati unutar tih modela (npr. Halting problem i "Busy beaver" funkcije). Uzmemo li Church-Turingovu tezu kao istinitu, to su primjeri problema koji dokazano nikad neće biti algoritamski riješeni, odnosno primjeri neizračunljivih funkcija.

Hrčak ID: 6217

URI
https://hrcak.srce.hr/6217

Posjeta: 224 *