algorithm - recursivos - recursividad java

¿Qué es un algoritmo super-recursivo?

Question

Hoy encontré este término por primera vez y la entrada de Wikipedia no me dice mucho:

En teoría de computabilidad, los algoritmos super-recursivos son una generalización de algoritmos ordinarios que son más potentes, es decir, que computan más que las máquinas de Turing.

Answer 1

Recursivo aquí no se refiere a un algoritmo que se usa a sí mismo como una subrutina; más bien, se refiere a la clase de funciones recursivas, que son aquellas que pueden ser calculadas por una máquina de Turing. Una función súper recursiva, entonces, sería una función que una máquina de Turing no es lo suficientemente poderosa para computar, requiriendo un modelo de computación más poderoso.

Por ejemplo, el problema de la detención requeriría un algoritmo super-recursivo, ya que no puede resolverse usando una máquina de Turing ordinaria.