Skoči na glavni sadržaj

Stručni rad

Izračunljivost i apstraktni strojevi

Marko Doko
Vedran Novaković


Puni tekst: hrvatski pdf 395 Kb

str. 30-48

preuzimanja: 110

citiraj


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.

Ključne riječi

Hrčak ID:

6217

URI

https://hrcak.srce.hr/6217

Posjeta: 386 *