b'\n_START_ARTICLE_\nAlgoritmo super-recursivo\n_START_PARAGRAPH_\nEm teoria da computa\xc3\xa7\xc3\xa3o, algoritmos super-recursivos s\xc3\xa3o uma generaliza\xc3\xa7\xc3\xa3o de algoritmos ordin\xc3\xa1rios que s\xc3\xa3o mais poderosos, isto \xc3\xa9, computam mais que uma m\xc3\xa1quina de Turing. O termo foi introduzido por Mark Burgin, cujo livro Super-recursive algorithms desenvolve sua teoria e apresenta modelos matem\xc3\xa1ticos. M\xc3\xa1quinas de Turing e outros modelos matem\xc3\xa1ticos de algoritmos convencionais permitem aos pesquisadores achar propriedades de algoritmos recursivos e de suas computa\xc3\xa7\xc3\xb5es. De uma maneira similar, modelos matem\xc3\xa1ticos de algoritmos super-recursivos, como m\xc3\xa1quinas de Turing indutivas, permitem aos pesquisadores achar propriedades dos algoritmos super-recursivos e de suas computa\xc3\xa7\xc3\xb5es._NEWLINE_Mark Burgin, assim como outros pesquisadores (incluindo Selim Akl, Eugene Eberbach, Peter Kugel, Jan van Leeuwen, Hava Siegelmann, Peter Wegner, and Ji\xc5\x99\xc3\xad Wiedermann) que estudaram diferentes tipos de algoritmos super-recursivos e contribu\xc3\xadram para a teoria dos algoritmos super-recursivos, t\xc3\xaam 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\xc3\xa1tica e n\xc3\xa3o foi amplamente aceito.\n_START_SECTION_\nDefini\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nBurgin (2005: 13) usa o termo algoritmo recursivo para algoritmos que podem ser implementados por uma M\xc3\xa1quina de Turing, e usa o termo algoritmo em um sentido mais geral. Em seguida, define que a classe de algoritmos super-recursivos \xc3\xa9 uma "classe de algoritmos que tem a possibilidade de computar fun\xc3\xa7\xc3\xb5es que n\xc3\xa3o s\xc3\xa3o comput\xc3\xa1veis por nenhuma m\xc3\xa1quina de Turing" (Burgin 2005: 107)._NEWLINE_Algoritmos super-recursivos s\xc3\xa3o intimamente relacionados com "hipercomputa\xc3\xa7\xc3\xa3o" de uma maneira similar a rela\xc3\xa7\xc3\xa3o entre computa\xc3\xa7\xc3\xa3o ordin\xc3\xa1ria e algoritmos ordin\xc3\xa1rios. Computa\xc3\xa7\xc3\xa3o \xc3\xa9 um processo, enquanto um algoritmo \xc3\xa9 ma constru\xc3\xa7\xc3\xa3o finita desse processo. Ent\xc3\xa3o, um algoritmo super-recursivo define um "processo computacional (incluindo processos, entrada e sa\xc3\xadda) que n\xc3\xa3o pode ser realizado por um algoritmo recursivo" (Burgin 2005: 108)._NEWLINE_Algoritmos super-recursivos tamb\xc3\xa9m s\xc3\xa3o relacionados a "esquemas de algoritmos" (algorithmic schemes), que s\xc3\xa3o mais generalizados que algoritmos super-recursivos. Burgin argumenta (2005: 115) que \xc3\xa9 necess\xc3\xa1rio fazer uma distin\xc3\xa7\xc3\xa3o clara entre algoritmos super-recursivos e aqueles "esquemas algor\xc3\xadtmicos" que n\xc3\xa3o s\xc3\xa3o algoritmos. Dentro dessa distin\xc3\xa7\xc3\xa3o, alguns tipos de hipercomputa\xc3\xa7\xc3\xa3o s\xc3\xa3o obtidos por algoritmos super-recursivos, por exemplo, m\xc3\xa1quinas de Turing indutivas, enquanto outros tipos de hipercomputa\xc3\xa7\xc3\xa3o s\xc3\xa3o direcionados por "esquemas de algoritmos", por exemplo, M\xc3\xa1quinas de Turing de tempo infinito. Isso explica como algoritmos super-recursivos s\xc3\xa3o relacionados a hipercomputa\xc3\xa7\xc3\xa3o e vice-versa. Segundo esse argumento, algoritmos super-recursivos s\xc3\xa3o apenas uma maneira de definir o processo de hipercomputa\xc3\xa7\xc3\xa3o.\n_START_SECTION_\nM\xc3\xa1quinas de Turing indutivas\n_START_PARAGRAPH_\nM\xc3\xa1quinas de Turing indutivas implementam uma importante classe de algoritmos super-recursivos. Uma m\xc3\xa1quina de Turing indutiva \xc3\xa9 uma lista definitiva de instru\xc3\xa7\xc3\xb5es bem definidas para completar uma tarefa, e quando essa m\xc3\xa1quina receber um estado inicial, ir\xc3\xa1 proceder atrav\xc3\xa9s de uma s\xc3\xa9rie bem definida de estados sucessivos, e eventualmente ir\xc3\xa1 dar o estado final. A diferen\xc3\xa7a entre uma m\xc3\xa1quina de Turing indutiva e uma M\xc3\xa1quina de Turing ordin\xc3\xa1ria \xc3\xa9 que a M\xc3\xa1quina de Turing ordin\xc3\xa1ria deve parar quando obtiver o resultado, enquanto que em alguns casos, a m\xc3\xa1quina 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\xc3\xa9m disse que esse algoritmo deveria eventualmente exibir "algum objeto" (Kleene 1952:137). Burgin argumentou que essa condi\xc3\xa7\xc3\xa3o \xc3\xa9 satisfeita nas m\xc3\xa1quinas de Turing indutivas, pois seus resultados s\xc3\xa3o exibidos ap\xc3\xb3s um n\xc3\xbamero finito de passos. A raz\xc3\xa3o para que m\xc3\xa1quinas de Turing indutivas n\xc3\xa3o poderem receber a instru\xc3\xa7\xc3\xa3o de parar quando achar a sa\xc3\xadda final \xc3\xa9 que em alguns casos, as m\xc3\xa1quinas de Turing indutivas n\xc3\xa3o s\xc3\xa3o capazes de dizer em que passo a sa\xc3\xadda foi encontrada._NEWLINE_M\xc3\xa1quinas de Turing indutivas simples s\xc3\xa3o equivalentes a outros modelos de computa\xc3\xa7\xc3\xa3o como a m\xc3\xa1quina de Turing de Schmidhuber generalizadas, predicados de tentativa e erro (trial and error predicates) de Hilary Putnam, limitando fun\xc3\xa7\xc3\xb5es parcialmente recursivas (limiting partial recursive functions) de Gold e m\xc3\xa1quinas de tentativa e erro de Hintikka and Mutanen (trial-and-error machines of Hintikka and Mutanen). M\xc3\xa1quinas de Turing indutivas mais avan\xc3\xa7adas s\xc3\xa3o muito mais poderosas. Existem hierarquias para m\xc3\xa1quinas de Turing indutivas que podem decidir a ades\xc3\xa3o da m\xc3\xa1quina em conjuntos arbitr\xc3\xa1rios da hierarquia aritm\xc3\xa9tica (Burgin 2005). Em compara\xc3\xa7\xc3\xa3o com outros modelos de computa\xc3\xa7\xc3\xa3o equivalentes, m\xc3\xa1quinas de Turing indutivas simples e m\xc3\xa1quinas de Turing generalizadas d\xc3\xa3o constru\xc3\xa7\xc3\xb5es diretas de automatos de computa\xc3\xa7\xc3\xa3o, que s\xc3\xa3o completamente fundamentados em maquinas f\xc3\xadsicas. Em constraste, predicados de tentativa e erro (trial-and-error predicates), limitando fun\xc3\xa7\xc3\xb5es recursivas (limiting recursive functions) e limitando fun\xc3\xa7\xc3\xb5es parcialmente recursivas (limiting partial recursive functions) apresentam apenas sistemas sint\xc3\xa1ticos de s\xc3\xadmbolos com regras formais para sua manipula\xc3\xa7\xc3\xa3o. M\xc3\xa1quinas de Turing indutivas simples e m\xc3\xa1quinas de Turing generalizadas s\xc3\xa3o relacionadas com "limitando fun\xc3\xa7\xc3\xb5es parcialmente recursivas" (limiting partial recursive functions) e "predicados de tentativa e erro"(trial and error predicate) como uma m\xc3\xa1quina de Turing est\xc3\xa1 relacionada com limitando fun\xc3\xa7\xc3\xb5es parcialmente recursivas (limiting partial recursive functions) e com calculo de lambda (lambda calculus)._NEWLINE_A n\xc3\xa3o-parada da computa\xc3\xa7\xc3\xa3o das m\xc3\xa1quinas de Turing indutivas n\xc3\xa3o deve ser confundido com computa\xc3\xa7\xc3\xa3o de tempo infinito(veja, por exemplo, Potgieter 2006).Primeiro, algumas vezes que uma m\xc3\xa1quina de Turing indutiva est\xc3\xa1 executando ela para. Como no caso das m\xc3\xa1quinas de Turing convencionais, alguns c\xc3\xa1lculos de parada(halting computation) produzem resultado, outros n\xc3\xa3o. Mesmo que n\xc3\xa3o pare, uma m\xc3\xa1quina de Turing indutiva produz uma sa\xc3\xadda de tempos em tempos. Se essa sa\xc3\xadda parar de mudar, ela \xc3\xa9 considerada o resultado do c\xc3\xa1lculo._NEWLINE_Existem duas principais dintin\xc3\xa7\xc3\xb5es entre m\xc3\xa1quinas de Turing indutivas simples e m\xc3\xa1quinas de Turing ordin\xc3\xa1rias. A primeira delas \xc3\xa9 que mesmo m\xc3\xa1quinas de Turing indutivas simples podem fazer muito mais que uma m\xc3\xa1quina de Turing convencional. A segunda distin\xc3\xa7\xc3\xa3o \xc3\xa9 que uma m\xc3\xa1quina de Turing convencional vai sempre determinar(indo para o estado final) quando o resultado foi obtido, enquanto que na m\xc3\xa1quina de Turing indutiva simples, em alguns casos (como quando se est\xc3\xa1 calculando algo que uma m\xc3\xa1quina de Turing convencional n\xc3\xa3o possa), n\xc3\xa3o se pode determinar.\n_START_SECTION_\nRela\xc3\xa7\xc3\xa3o com a tese de Church-Turing\n_START_PARAGRAPH_\nA tese de Church-Turing na teoria da recurs\xc3\xa3o baseia-se na defini\xc3\xa7\xc3\xa3o particular do termo algoritmo. Baseado em defini\xc3\xa7\xc3\xb5es mais gerais que a comummente usada em teoria da recurs\xc3\xa3o, Burgin argumenta que algoritmos super-recursivos, como por exemplo m\xc3\xa1quinas de Turing indutivas, refutam a tese de Church-Turing. Al\xc3\xa9m disso, ele prova que o uso de algoritmos super-recursivos podem teoricamente prover ganhos de efici\xc3\xaancia ainda maior que algoritmos qu\xc3\xa2nticos._NEWLINE_A interpreta\xc3\xa7\xc3\xa3o de Burgin acerca dos algoritmos super-recursivos encontrou oposi\xc3\xa7\xc3\xa3o na comunidade matem\xc3\xa1tica. Um dos cr\xc3\xadticos \xc3\xa9 o matem\xc3\xa1tico Martin Davis, que argumenta que as afirma\xc3\xa7\xc3\xb5es de Burgin tem sido bem compreendidas "por d\xc3\xa9cadas". Davis afirma:_NEWLINE_"A cr\xc3\xadtica presente n\xc3\xa3o \xc3\xa9 sobre a discuss\xc3\xa3o matem\xc3\xa1tica dessas quest\xc3\xb5es, mas apenas sobre as alega\xc3\xa7\xc3\xb5es equivocadas sobre os sistemas f\xc3\xadsicos do presente e do futuro."(Davis 2006: 128)_NEWLINE_Davis contesta as alega\xc3\xa7\xc3\xb5es de Burgin que define a n\xc3\xadvel  da hierarquia de aritm\xc3\xa9tica podem ser chamados de comput\xc3\xa1veis. ele diz que:_NEWLINE_"\xc3\x89 geralmente compreendido que para um resultado computacional se \xc3\xbatil, deve ser capaz de, pelo menos, reconhecer que \xc3\xa9 na verdade o resultado desejado."'