Content deleted Content added
Line 359:
:''In fact, it is difficult to devise a '''total''' computable function that is not primitive recursive.''
--[[User:Jobu0101|Jobu0101]] ([[User talk:Jobu0101|talk]]) 11:13, 22 April 2015 (UTC)
:: The ackerman function is such a function. It is not primitive recursive. And its total. The proof goes usually by majorization. In terms of LOOP/WHILE one would show that for every program with n-LOOPs there is some ackerman function invocation, that grows more than the n-LOOPs program. By this majorization, one can show that the ackeman function cannot be implemented by a LOOP-program.
:Good point. I changed "computable" to "total recursive" in that sentence. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 04:56, 23 April 2015 (UTC)
| |||