LOOP-izračunljivost

diplomski rad

• Naslov (engleski): LOOP-computability
• Autor: Ivan Avirović
• Mentor: Vedran Čačić (mentor)
• Član povjerenstva: Vedran Čačić (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Marko Horvat (član povjerenstva)
• Član povjerenstva: Marko Tadić (č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: 2022-07-20, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ukratko, u ovom radu proučavamo LOOP-izračunljivost; detaljnija motivacija može se naći u uvodu. U prvom poglavlju definiramo LOOP-stroj i pokazujemo njegov rad na nekoliko primjera. Definiramo LOOP-program te njegovu dubinu i duljinu. Na kraju definiramo LOOP-algoritam i što znači da je funkcija LOOP-izračunljiva. U drugom poglavlju najprije definiramo funkcijski potprogram i primitivno rekurzivne funkcije. Pomoću funkcijskog potprograma dokazujemo da je svaka primitivno rekurzivna funkcija ujedno i LOOP-izračunljiva. Zatim pokazujemo i obrat te tvrdnje, da je svaka LOOP-izračunljiva funkcija ujedno i primitivno rekurzivna. U trećem poglavlju definiramo kodiranje LOOP-programa. Uvodimo rekurzivne funkcije i pokazujemo da se naša definicija rekurzivnih funkcija poklapa s definicijom iz [1]. Na kraju definiramo univerzalnu funkciju koja može simulirati proizvoljni LOOP-program, te pomoću nje dobivamo primjer funkcije, a zatim i relacije, koja je rekurzivna, ali nije primitivno rekurzivna.

Sažetak (engleski)

In short, in this paper we study LOOP-computability; a more detailed motivation can be found in the introduction. In the first chapter, we define the LOOP-machine and demonstrate its operation on several examples. We define the LOOP-program and its depth and length. Then we define the LOOP-algorithm and what it means for a function to be LOOP-computable. In the second chapter, we first define a functional subroutine and primitively recursive functions. Using the functional subroutine, we prove that every primitive recursive function is also LOOP-computable. We also show the converse statement, that every LOOP-computable function is primitive recursive. In the third chapter, we define the encoding of LOOP-programs into natural numbers. We introduce recursive functions and show that our definition of recursive functions coincides with the definition from [1]. Finally, we define the universal function that is able to simulate an arbitrary LOOP-program, and using it we get an example of a function and a relation that are recursive while not being primitive recursive.

• Ključne riječi: LOOP-stroj; LOOP-algoritam; funkcijski potprogram; primitivno rekurzivne funkcije; rekurzivne funkcije
• Ključne riječi (engleski): LOOP-machine; LOOP-algorithm; functional subroutine; primitive recursive functions; recursive functions
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:145511
• 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: 2022-09-12 11:01:45