Algoritmo super-recursivo

Origem: Wikipédia, a enciclopédia livre.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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
  • 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
  • Burgin, M. and Klinger, A. Three Aspects of Super-recursive Algorithms and Hypercomputation or Finding Black Swans, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 1-11
  • Burgin, M. Algorithmic Complexity of Recursive and Inductive Algorithms, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 31-60
  • Burgin, M. and Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 71-91
  • Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91-109
  • Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
  • Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
  • Eberbach, E. (2005) Toward a theory of evolutionary computation, BioSystems 82, 1-19
  • Eberbach, E., and Wegner, P., Beyond Turing Machines, Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304
  • Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme," Monatshefte für Mathematik und Physik 38: 173-98.
  • Gold, E.M. Limiting recursion. J. Symb. Logic 10 (1965), 28-48.
  • Gold, E.M. (1967) Language Identification in the Limit, Information and Control, v. 10, pp. 447-474
  • Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
  • Hintikka, Ja. and Mutanen, A. An Alternative Concept of Computability, in “Language, Truth, and Logic in Mathematics”, Dordrecht, pp. 174-188, 1998
  • E.J. Horvitz. Reasoning about inference tradeoffs in a world of bounded resources. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, March 1986
  • Juraj Hromkovič, Design and Analysis of Randomized Algorithms, Springer, 2005
  • Kleene, Stephen C. (1952), Introduction to Metamathematics 1ª ed. , Amsterdam: North-Holland .
  • Kosovsky, N. K. (1981) Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad
  • Peter Kugel, It's time to think outside the computational box, Communications of the ACM, Volume 48, Issue 11, November 2005
  • Petrus H.Potgieter, Zeno machines and hypercomputation, Theoretical Computer Science, Volume 358, Issue 1 (July 2006) pp. 23 - 33
  • Hilary Putnam, Trial and Error Predicates and the Solution to a Problem of Mostowski. J. Symbolic Logic, Volume 30, Issue 1 (1965), 49-57
  • Darko Roglic, "The universal evolutionary computer based on super-recursive algorithms of evolvability"
  • J. Schmidhuber (2000): Algorithmic Theories of Everything http://arxiv.org/abs/quant-ph/0011122
  • J. Schmidhuber (2002): Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612 http://www.idsia.ch/~juergen/kolmogorov.html
  • Hava Siegelmann, Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhauser, 1999
  • Turing, A. (1939) Systems of Logic Based on Ordinals, Proc. Lond. Math. Soc., Ser.2, v. 45: 161-228
  • van Leeuwen, J. and Wiedermann, J. (2000a) Breaking the Turing Barrier: The case of the Internet, Techn. Report, Inst. of Computer Science, Academy of Sciences of the Czech. Rep., Prague
  • Jiří Wiedermann, Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, Theoretical Computer Science, Volume 317, Issue 1-3, June 2004
  • Jiří Wiedermann and Jan van Leeuwen, The emergent computational potential of evolving artificial living systems, AI Communications, v. 15, No. 4, 2002
  • Hector Zenil and Francisco Hernandez-Quiroz, On the possible computational power of the human mind, Worldviews, Science and Us, edited by Carlos Gershenson, Diederik Aerts and Bruce Edmonds, World Scientific, 2007, (arXiv:cs.NE/0605065v3)
  • S. Zilberstein, Using Anytime Algorithms in Intelligent Systems, "AI Magazine", 17(3):73-83, 1996

Ligações externas[editar | editar código-fonte]

Obtida de "https://pt.wikipedia.org/w/index.php?title=Algoritmo_super-recursivo&oldid=65203925"