4 ms·

Basically, anything that can recurse is Turing-complete.

klmr 8y ago
No. Only anything that can perform µ-recursion is Turing complete. Primitive recursion [1] is not enough. In practice virtually all languages that allow recursion allow its Turing complete form but it’s important to realise that other forms exist. [1] https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function
- deytempo 8y ago
  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.
- norswap 8y ago
  Could you give an example of primitive recursion that is not µ-recursion?
  - OskarS 8y ago
    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.
  - zeroonetwothree 8y ago
    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”.

klmr 8y ago

No. Only anything that can perform µ-recursion is Turing complete. Primitive recursion [1] is not enough. In practice virtually all languages that allow recursion allow its Turing complete form but it’s important to realise that other forms exist. [1] https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function

deytempo 8y ago
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.
norswap 8y ago
Could you give an example of primitive recursion that is not µ-recursion?
- OskarS 8y ago
  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.
- zeroonetwothree 8y ago
  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”.