En la teoría de la computabilidad , los algoritmos superrecursivos se postulan como una generalización de la hipercomputación : algoritmos hipotéticos que son más potentes, es decir, calculan más que las máquinas de Turing .
El término fue introducido por Mark Burgin, cuyo libro Algoritmos superrecursivos desarrolla su teoría y presenta varios modelos matemáticos.
Burgin sostiene que los algoritmos superrecursivos pueden utilizarse para refutar la tesis de Church-Turing . Este punto de vista ha sido criticado dentro de la comunidad matemática y no es ampliamente aceptado.
Burgin (2005: 13) utiliza el término algoritmos recursivos para algoritmos que pueden implementarse en máquinas de Turing, y utiliza la palabra algoritmo en un sentido más general. Por lo tanto, una clase de algoritmos superrecursivos es "una clase de algoritmos en los que es posible calcular funciones que no pueden calcularse con ninguna máquina de Turing " (Burgin 2005: 107).
Los algoritmos superrecursivos también están relacionados con los esquemas algorítmicos , otro concepto novedoso de Burgin, que son más generales que los algoritmos superrecursivos. Burgin sostiene (2005: 115) que es necesario hacer una distinción clara entre algoritmos superrecursivos y aquellos esquemas algorítmicos que no son algoritmos. Bajo esta distinción, algunos tipos de hipercomputación se obtienen mediante algoritmos superrecursivos.
La tesis de Church-Turing en la teoría de la recursión se basa en una definición particular del término algoritmo . Basándose en sus definiciones personales, que son más generales que la que se utiliza habitualmente en la teoría de la recursión, Burgin sostiene que los algoritmos superrecursivos refutan la tesis de Church-Turing . Además, afirma demostrar que los algoritmos superrecursivos podrían proporcionar hipotéticamente ganancias de eficiencia incluso mayores que el uso de algoritmos cuánticos .
La interpretación de Burgin de los algoritmos superrecursivos ha encontrado oposición en la comunidad matemática. Uno de sus críticos es el lógico Martin Davis , quien sostiene que las afirmaciones de Burgin se han entendido bien "desde hace décadas". Davis afirma:
Davis cuestiona las afirmaciones de Burgin de que los conjuntos en el nivel de la jerarquía aritmética pueden llamarse computables, diciendo
