0
$\begingroup$

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I understood) compute anything that isn't growing faster than $Ack(n)$.

Is this implying that the upper bound runtime complexity for LOOP programs is $O(Ack(n))$? And are there functions similar to Ackermann's function, which can't be computed by primitive recursive functions, but grow slower than $Ack(n)$?

(sorry for spelling and grammar)

$\endgroup$
0
$\begingroup$

Take Ack(n-1). Grows much slower than Ack(n).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.