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)
▲:: BTW: 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.
:: But you are not alone, David Hilbert believed the same, until the discovery of the [[Ackermann function]] showed the contrary.
:
== Floop issue. ==
| |||