Turing--izračunljivost na prirodnim brojevima

master's thesis

• Author: Bojana Đerić
• Mentor: Vedran Čačić (mentor)
• Committee member: Vedran Čačić (predsjednik povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Goran Radunović (član povjerenstva)
• Committee member: Goran Igaly (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Turingov stroj; Kleenijev model; parcijalno rekurzivne funkcije; uredna izračunljivost
• Keywords (english): Turing machine; Kleene’s model; partial recursive functions; tidy computations
• Language: croatian
• URN:NBN: urn:nbn:hr:217:515568
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-07-02 11:21:27