Re:A proof that Unix utility sed is Turing complete
by OskarS on Friday February 15, 2019 @09:56AM
(#19171362)
Every primitive recursive function is also µ-recursive: the primitive recursive functions are a subset of µ-recursive functions. But the converse is not true: there are µ-recursive functions that are not primitive recursive. The canonical example is the Ackermann function. It can be shown that it grows faster than all primitive recursive functions, and is thus in itself not primitive recursive.
Since the Ackermann function is obviously computable, and easily computable by a Turing machine, this implies that the primitive recursive functions are not Turing complete, and thus more limited than the µ-recursive functions.
Since the Ackermann function is obviously computable, and easily computable by a Turing machine, this implies that the primitive recursive functions are not Turing complete, and thus more limited than the µ-recursive functions.