LOOP-izračunljivost ; LOOP-computability

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. ; 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 ...