Skip to the main content

Professional paper

Izračunljivost i apstraktni strojevi

Marko Doko
Vedran Novaković


Full text: croatian pdf 395 Kb

page 30-48

downloads: 116

cite


Abstract

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.

Keywords

Hrčak ID:

6217

URI

https://hrcak.srce.hr/6217

Visits: 408 *