Re:A proof that Unix utility sed is Turing complete
by deytempo on Friday February 15, 2019 @07:36AM
(#19170341)
It fascinates me how few people can or are willing to explain concepts of computer science without using formal mathematical notational explanations. When asked, often they will say “that’s the only/best way to explain it” then I go and spend a few hours translating said concept from the formal math notational mess, finding that it’s indeed quite possible to explain it simply and even elegantly in either natural language or just a pseudo code example.
Re:A proof that Unix utility sed is Turing complete
by norswap on Friday February 15, 2019 @09:06AM
(#19170973)
Could you give an example of primitive recursion that is not µ-recursion?
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.
Re:A proof that Unix utility sed is Turing complete
by zeroonetwothree on Friday February 15, 2019 @10:14AM
(#19171504)
Primitive recursion is a subset of µ-recursion so there is no such example. I assume you just want an example of primitive recursion.
The term is confusing if you are used to “recursion” in the context of programming. Primitive recursion basically corresponds to programs that don’t use recursion or unbounded loops. For example “compute the factorial of 55” or “sort this input list of at most 10000 integers”.
[1] https://en.wikipedia.org/wiki/Primitive_recursive_function