Algoritmo super-recursivo
Em teoria da computação, algoritmos super-recursivos são uma generalização de algoritmos ordinários que são mais poderosos, isto é, computam mais que uma máquina de Turing. O termo foi introduzido por Mark Burgin, cujo livro Super-recursive algorithms desenvolve sua teoria e apresenta modelos matemáticos. Máquinas de Turing e outros modelos matemáticos de algoritmos convencionais permitem aos pesquisadores achar propriedades de algoritmos recursivos e de suas computações. De uma maneira similar, modelos matemáticos de algoritmos super-recursivos, como máquinas de Turing indutivas, permitem aos pesquisadores achar propriedades dos algoritmos super-recursivos e de suas computações.
Burgin (2005: 13) usa o termo algoritmo recursivo para algoritmos que podem ser implementados por uma Máquina de Turing, e usa o termo algoritmo em um sentido mais geral. Em seguida, define que a classe de algoritmos super-recursivos é uma "classe de algoritmos que tem a possibilidade de computar funções que não são computáveis por nenhuma máquina de Turing" (Burgin 2005: 107). Algoritmos super-recursivos são intimamente relacionados com "hipercomputação" de uma maneira similar a relação entre computação ordinária e algoritmos ordinários. Computação é um processo, enquanto um algoritmo é ma construção finita desse processo. Então, um algoritmo super-recursivo define um "processo computacional (incluindo processos, entrada e saída) que não pode ser realizado por um algoritmo recursivo" (Burgin 2005: 108). Algoritmos super-recursivos também são relacionados a "esquemas de algoritmos" (algorithmic schemes), que são mais generalizados que algoritmos super-recursivos. Burgin argumenta (2005: 115) que é necessário fazer uma distinção clara entre algoritmos super-recursivos e aqueles "esquemas algorítmicos" que não são algoritmos. Dentro dessa distinção, alguns tipos de hipercomputação são obtidos por algoritmos super-recursivos, por exemplo, máquinas de Turing indutivas, enquanto outros tipos de hipercomputação são direcionados por "esquemas de algoritmos", por exemplo, Máquinas de Turing de tempo infinito. Isso explica como algoritmos super-recursivos são relacionados a hipercomputação e vice-versa. Segundo esse argumento, algoritmos super-recursivos são apenas uma maneira de definir o processo de hipercomputação.
exemplos de algoritmos super-recursivos são: Exemplos de esquemas de algoritmos(algorithmic schemes): Para exemplos de algoritmos super-recursivos práticos, veja o livro de Burkin.
Máquinas de Turing indutivas implementam uma importante classe de algoritmos super-recursivos. Uma máquina de Turing indutiva é uma lista definitiva de instruções bem definidas para completar uma tarefa, e quando essa máquina receber um estado inicial, irá proceder através de uma série bem definida de estados sucessivos, e eventualmente irá dar o estado final. A diferença entre uma máquina de Turing indutiva e uma Máquina de Turing ordinária é que a Máquina de Turing ordinária deve parar quando obtiver o resultado, enquanto que em alguns casos, a máquina de Turing indutiva pode continuar computando depois de que obtiver o resultado, sem parar. Kleene chamou procedimentos que poderiam executar para sempre, sem parar, pelo nome de "procedimento ou algoritmo de calculo" (calculation procedure or algorithm)(Kleene 1952:137). Kleene também disse que esse algoritmo deveria eventualmente exibir "algum objeto" (Kleene 1952:137). Burgin argumentou que essa condição é satisfeita nas máquinas de Turing indutivas, pois seus resultados são exibidos após um número finito de passos. A razão para que máquinas de Turing indutivas não poderem receber a instrução de parar quando achar a saída final é que em alguns casos, as máquinas de Turing indutivas não são capazes de dizer em que passo a saída foi encontrada.
A tese de Church-Turing na teoria da recursão baseia-se na definição particular do termo algoritmo. Baseado em definições mais gerais que a comummente usada em teoria da recursão, Burgin argumenta que algoritmos super-recursivos, como por exemplo máquinas de Turing indutivas, refutam a tese de Church-Turing. Além disso, ele prova que o uso de algoritmos super-recursivos podem teoricamente prover ganhos de eficiência ainda maior que algoritmos quânticos. A interpretação de Burgin acerca dos algoritmos super-recursivos encontrou oposição na comunidade matemática. Um dos críticos é o matemático Martin Davis, que argumenta que as afirmações de Burgin tem sido bem compreendidas "por décadas". Davis afirma: "A crítica presente não é sobre a discussão matemática dessas questões, mas apenas sobre as alegações equivocadas sobre os sistemas físicos do presente e do futuro."(Davis 2006: 128) Davis contesta as alegações de Burgin que define a nível Δ 2 0 {\displaystyle \Delta _{2}^{0}} da hierarquia de aritmética podem ser chamados de computáveis. ele diz que: "É geralmente compreendido que para um resultado computacional se útil, deve ser capaz de, pelo menos, reconhecer que é na verdade o resultado desejado."
