Parcijalno rekurzivni funkcionali

diplomski rad

• Autor: Andrej Pavlović
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Član povjerenstva: Tina Bosner (član povjerenstva)
• Član povjerenstva: Tomislav Berić (č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: 2017-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: parcijalno rekurzivne funkcije; parcijalno rekurzivni funkcionali; Keenijev teorem o normalnoj formi
• Ključne riječi (engleski): partial recursive functions; partial recursive functionals; Kleene’s normal form theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:039921
• 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-02-17 10:33:32