Turing--izračunljivost na prirodnim brojevima

diplomski rad

• Autor: Bojana Đerić
• Mentor: Vedran Čačić (mentor)
• Član povjerenstva: Vedran Čačić (predsjednik povjerenstva)
• Član povjerenstva: Eduard Marušić-Paloka (član povjerenstva)
• Član povjerenstva: Goran Radunović (član povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-11-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ukratko, u ovom radu pokazali smo da Turingovi strojevi mogu simulirati Kleenijev model parcijalno rekurzivnih funkcija. U uvodnom dijelu dajemo definicije vezane uz Turingov model, definicije iz teorije parcijalno rekurzivnih funkcija, kao i definiciju tehnike za zapis proizvoljno (konačno) mnogo prirodnih brojeva na traci Turingovog stroja. Definiramo pojam uredne izračunljivosti, te u glavnom dijelu rada pokazujemo da je moguće uredno izračunati inicijalne funkcije, kompoziciju, primitivnu rekurziju i minimizaciju. Turingovi strojevi koji ih računaju su eksplicitno dani nizom fragmenata uz objašnjenje kako se fragmenti slažu do cjelovitog stroja.

Sažetak (engleski)

In this paper, we show that Turing machines can simulate Kleene’s model of partial recursive functions. In the introduction we give definitions of Turing’s model and of partial recursive functions, as well as definition of a technique for writing arbitrarily (but finitely) many natural numbers on a Turing machine tape. We also define concept of tidy computations, and, in the main part of paper, we show that it is possible to compute initial functions, composition, primitive recursion and minimization in a tidy way. Turing machines computing them are explicitly given in a series of fragments with explanation of how to arrange those fragments into a complete machine.

• Ključne riječi: Turingov stroj; Kleenijev model; parcijalno rekurzivne funkcije; uredna izračunljivost
• Ključne riječi (engleski): Turing machine; Kleene’s model; partial recursive functions; tidy computations
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:515568
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-07-02 11:21:27