Ackermannfunktion

#Studium #Informatik #Definition #BeKo

Die Ackermannfunktion (Variante nach Rózsa Péter) ist eine total berechenbare Funktion, die extrem schnell wächst und nicht primitiv-rekursiv (und damit nicht LOOP-berechenbar) ist. Sie ist definiert durch:

a (x, y) := {\begin{cases} y + 1 & if x = 0 \\ a (x - 1, 1) & if x > 0 and y = 0 \\ a (x - 1, a (x, y - 1)) & if x > 0 and y > 0 \end{cases}