Professional paper

Izračunljivost i apstraktni strojevi

Marko Doko
Vedran Novaković

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

Publication date:

15.10.2006.

Visits: 1.338 *