LOOP-izračunljivost

master's thesis

• Title (english): LOOP-computability
• Author: Ivan Avirović
• Mentor: Vedran Čačić (mentor)
• Committee member: Vedran Čačić (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Marko Horvat (član povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-07-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: LOOP-stroj; LOOP-algoritam; funkcijski potprogram; primitivno rekurzivne funkcije; rekurzivne funkcije
• Keywords (english): LOOP-machine; LOOP-algorithm; functional subroutine; primitive recursive functions; recursive functions
• Language: croatian
• URN:NBN: urn:nbn:hr:217:145511
• 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: 2022-09-12 11:01:45