Parcijalno rekurzivni funkcionali

master's thesis

• Author: Andrej Pavlović
• Mentor: Mladen Vuković (mentor)
• Committee member: Mladen Vuković (predsjednik povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Tomislav Berić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Cilj ovog rada bio je napraviti generalizaciju parcijalno rekurzivnih funkcija na parcijalno rekurzivne funkcionale. Rad smo započeli uvođenjem pojmova izračunavanja te izračunljive funkcije. Potom smo definirali RAM-stroj i RAM-izračunljivu funkciju kako bi mogli definirati novu klasu izračunljivih funkcija, a to su parcijalno rekurzivne funkcije. Naveli smo osnovna svojstva parcijalno rekurzivnih funkcija te dali skicu dokaza glavnog teorema za parcijalno rekurzivne funkcije, a to je Kleenijev teorem o normalnoj formi. Prilikom davanja skice dokaza pokazali smo kako "efektivno kodirati" konačne nizove prirodnih brojeva definirajući funkciju kodiranja i kod konačnog niza te čitav postupak ilustrirali kroz primjere. Nakon što smo napravili uvod i definirali sve što nam je potrebno, uveli smo pojam funkcionala. Funkcional smo definirali kao funkciju koja uz prirodne brojeve može kao argumente imati i funkcije na prirodnim brojevima. Postupno generaliziramo pojmove koje smo u uvodu imali za funkcije definirajući intuitivno pojam izračunljivog funkcionala. Definiciju RAM-stroja proširujemo definicijom GRAM-stroja dodavajući novu instrukciju koja je zadužena za rad s ulaznim funkcijama nekog funkcionala. Na analogan način definiramo i GRAM-izračunljivu funkciju te definiramo da je svaka RAM-izračunljiva funkcija ujedno i GRAM-izračunljiva. Potom smo po analogonu za parcijalno rekurzivne funkcije dokazali važni teorem o normalnoj formi za parcijalno rekurzivne funkcionale. Sljedeći cilj, te ujedno i zaključak ovog rada bio je iskazati i dokazati također bitan prvi teorem rekurzije za parcijalno rekurzivne funkcionale. To smo napravali uvođenjem pojma fiksne točke te definicijom svojstva monotonosti i kompaktnosti za parcijalno rekurzivne funkcionale.

Abstract (english)

The main point of this work was to make a generalization of partial recursive functions to partial recursive functionals. First we introduced the notions of computability and a computable function. Then we defined RAM-machines and RAM-computable functions so that we could define a new class of computable functions. This is the class of partial recursive functions. We talked about the main characteristics of partial recursive functions and gave a quick review of the main theorem for partial recursive functions, which is Kleene’s normal form theorem. While we gave the quick proof we also introduced the notion of ”effective coding” of finite sequences of natural numbers by definig the coding function and the code of a finte sequence of natural numbers. We then gave examples of the coding procedure. After we defined everything needed, we introduced the notion of a functional and defined it as a function with parameters that can take not only natural numbers as arguments, but also functions on natural numbers. Then we are stepwise doing a generalization of notions that we had for functions by intuitively giving the definition of a computable functional. We generalize the definition of RAM-machines by defining GRAM-machines which have a new type of instruction. The job of the new instruction is to take care of the function arguments of a functional. Just like the definition of RAM-computable functions we define GRAM-computable functions and say that every RAM-computable function is also GRAM-computable. We then proved the normal form theorem for partial recursive functionals using the analogon of this theorem in terms of partial recursive functions. The next goal, and the last part of this work was to give the proof the important first recursion theorem for partial recursive functionals. We have done that by defining the fixed-point and defining the property of compactness and monothonity for recursive functionals.

• Keywords: parcijalno rekurzivne funkcije; parcijalno rekurzivni funkcionali; Keenijev teorem o normalnoj formi
• Keywords (english): partial recursive functions; partial recursive functionals; Kleene’s normal form theorem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:039921
• 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-02-17 10:33:32