Menu
I ran across this term for the first time today and the Wikipedia entry for it doesn't really tell me much:
In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.
396
What Is a Recursive Algorithm? A recursive algorithm calls itself with smaller input values and returns the result for the current input by carrying out basic operations on the returned value for the smaller input.
A classic example of recursion The classic example of recursive programming involves computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1 , and factorial(3) is 3*2*1 .
Recursive here does not refer to an algorithm that uses itself as a subroutine; rather, it refers to the class of recursive functions, which are those which can be computed by a Turing machine. A super-recursive function, then, would be a function which a Turing machine is not powerful enough to compute, requiring a more powerful computing model.
For example, the halting problem would require a super-recursive algorithm, since it is not solvable using an ordinary Turing machine.
125
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
