Thank you, that was a good explanation. However… > How do we prove that fib(n) halts while loop(n) does not? Unless your number system involves saturating sub

Thank you, that was a good explanation. However… > How do we prove that fib(n) halts while loop(n) does not? Unless your number system involves saturating subtraction (which I admit is a possibility, though this wasn't stated) your definition of fib(n) will never halt. No matter what natural number you start with it will always descend into negative numbers eventually since the fib(n-2) term skips over the fib(0) base case when n == 1: fib(2) fib(1) + fib(0) (fib(0) + fib(-1) ) + 1 ( 1 + (fib(-2) + fib(-3))) + 1