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.

Mark Burgin, assim como outros pesquisadores (incluindo Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Jiří Wiedermann) que estudaram diferentes tipos de algoritmos super-recursivos e contribuíram para a teoria dos algoritmos super-recursivos, têm argumentado que algoritmos super-recursivos podem ser usados para refutar a Tese de Church-Turing, mas esse ponto de vista foi muito criticado pela comunidade matemática e não foi amplamente aceito.

Definição

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

exemplos de algoritmos super-recursivos são:

Funções recursivas limitantes ("limiting recursive functions") e funções parcialmente recursivas limitantes ("limiting partial recursive functions") (E.M. Gold) Predicados de tentativa e erro ("trial and error predicates") (Hilary Putnam) Máquinas de inferência indutiva ("inductive inference machines") (Carl Smith) Máquinas de Turing indutivas ("inductive Turing machines"), que realizam cálculos parecidos com os de uma Máquina de Turing e produzem resultado após um número finito de passos. (Mark Burgin) Limite de máquina de Turing ("limit Turing machines"), que realizam cálculos similares aos de uma Máquina de Turing, mas seu resultado final são limites de seu resultado imediato. (Mark Burgin) Máquinas de tentativa e erro ("trial-and-error machines"). (Ja. Hintikka and A. Mutanen) Máquinas de Turing genéricas ("general Turing machines"). (J. Schmidhuber) Máquinas de Internet ("internet machines"). (van Leeuwen, J. and Wiedermann, J.) Computadores evolutivos ("evolutionary computers"), que usam DNA como valor para uma função. (Darko Roglic) Computação fuzzy ("fuzzy computation"). (Jirí Wiedermann) Máquinas de Turing evolutivas ("evolutionary Turing machines"). (Eugene Eberbach)

Exemplos de esquemas de algoritmos(algorithmic schemes): Máquinas de Turing com oráculos arbitrários ("Turing machines with arbitrary oracles") (Alan Turing) Operadores transrecursivos ("transrecursives operators") (Borodyanskii and Burgin) Máquinas que computam com números reais ("machines that compute with real numbers") (L. Blum, F. Cucker, M. Shub, and S. Smale) Rede neural baseada em números reais ("neural network based on real numbers") (Hava Siegelmann)

Para exemplos de algoritmos super-recursivos práticos, veja o livro de Burkin.

Máquinas de Turing indutivas

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.

Máquinas de Turing indutivas simples são equivalentes a outros modelos de computação como a máquina de Turing de Schmidhuber generalizadas, predicados de tentativa e erro (trial and error predicates) de Hilary Putnam, limitando funções parcialmente recursivas (limiting partial recursive functions) de Gold e máquinas de tentativa e erro de Hintikka and Mutanen (trial-and-error machines of Hintikka and Mutanen). Máquinas de Turing indutivas mais avançadas são muito mais poderosas. Existem hierarquias para máquinas de Turing indutivas que podem decidir a adesão da máquina em conjuntos arbitrários da hierarquia aritmética (Burgin 2005). Em comparação com outros modelos de computação equivalentes, máquinas de Turing indutivas simples e máquinas de Turing generalizadas dão construções diretas de automatos de computação, que são completamente fundamentados em maquinas físicas. Em constraste, predicados de tentativa e erro (trial-and-error predicates), limitando funções recursivas (limiting recursive functions) e limitando funções parcialmente recursivas (limiting partial recursive functions) apresentam apenas sistemas sintáticos de símbolos com regras formais para sua manipulação. Máquinas de Turing indutivas simples e máquinas de Turing generalizadas são relacionadas com "limitando funções parcialmente recursivas" (limiting partial recursive functions) e "predicados de tentativa e erro"(trial and error predicate) como uma máquina de Turing está relacionada com limitando funções parcialmente recursivas (limiting partial recursive functions) e com calculo de lambda (lambda calculus).

A não-parada da computação das máquinas de Turing indutivas não deve ser confundido com computação de tempo infinito(veja, por exemplo, Potgieter 2006).Primeiro, algumas vezes que uma máquina de Turing indutiva está executando ela para. Como no caso das máquinas de Turing convencionais, alguns cálculos de parada(halting computation) produzem resultado, outros não. Mesmo que não pare, uma máquina de Turing indutiva produz uma saída de tempos em tempos. Se essa saída parar de mudar, ela é considerada o resultado do cálculo.

Existem duas principais dintinções entre máquinas de Turing indutivas simples e máquinas de Turing ordinárias. A primeira delas é que mesmo máquinas de Turing indutivas simples podem fazer muito mais que uma máquina de Turing convencional. A segunda distinção é que uma máquina de Turing convencional vai sempre determinar(indo para o estado final) quando o resultado foi obtido, enquanto que na máquina de Turing indutiva simples, em alguns casos (como quando se está calculando algo que uma máquina de Turing convencional não possa), não se pode determinar.

Relação com a tese de Church-Turing

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 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."

Referencias Akl, S.G., Three counterexamples to dispel the myth of the universal computer, Parallel Processing Letters, Vol. 16, No. 3, September 2006, pp. 381 - 403. Akl, S.G., The myth of universal computation, in: Parallel Numerics, Trobec, R., Zinterhof, P., Vajtersic, M., and Uhl, A., Eds., Part 2, Systems and Simulation, University of Salzburg, Salzburg, Austria and Jozef Stefan Institute, Ljubljana, Slovenia, 2005, pp. 211 - 236 Angluin, D., and Smith, C. H. (1983) Inductive Inference: Theory and Methods, Comput. Surveys, v. 15, no. 3, pp. 237—269 Apsïtis, K, Arikawa, S, Freivalds, R., Hirowatari, E., and Smith, C. H. (1999) On the inductive inference of recursive real-valued functions, Theoret. Computer Science, 219(1-2): 3—17 Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, Transactions of the American Mathematical Society, v. 92, pp. 85-105 Blum, L., and Blum, M. (1975) Toward a mathematical theory of inductive inference. Information and Control vol. 28, pp. 125-155 Blum, L., F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer 1998 Boddy, M, Dean, T. 1989. "Solving Time-Dependent Planning Problems". Technical Report: CS-89-03, Brown University Borodyanskii, Yu. M. and Burgin, M.S. (1994) Operations with Transrecursive Operators, Cybernetics and System Analysis, No. 4, pp. 3-11 Burgin, Mark (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690 Review, José Félix Costa, MathSciNet. Review MR2246430. Review, Harvey Cohn (2005), "Computing Reviews", Review CR131542 (0606-0574) Review, Martin Davis (2007), Bulletin of Symbolic Logic, v. 13 n. 2. Online version Review, Marc L. Smith (2006), "The Computer Journal", Vol. 49 No. 6 Online version Review, Vilmar Trevisan (2005), Zentralblatt MATH, Vol. 1070. Review 1070.68038 Burgin, M. How We Know What Technology Can Do, Communications of the ACM, v. 44, No. 11, 2001, pp. 82-88 Burgin M., Universal limit Turing machines, Notices of the Russian Academy of Sciences, 325, No. 4, (1992), 654-658