Tese de Church-Turing
Keywords: Tese de Church-Turing, 1936, Alan Turing, Algoritmo, Algoritmo de Euclides, Alonzo Church, Entscheidungsproblem, Kurt Gödel, Linguagem de programação, Máquina de Turing
Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar.
Geralmente assume-se que um algoritmo deve satisfazer os seguintes requisitos:
- O algoritmo consiste de um conjunto finito de instruções simples e precisas, que são descritas com um número finito de símbolos.
- O algoritmo sempre produz resultado em um número finito de passos.
- O algoritmo pode, a princípio, ser executado por um ser humano com apenas papel e lápis.
- A execução do algoritmo não requer inteligência do ser humano além do necessário para entender e executar as instruções.
Um exemplo de tal método é o algoritmo de Euclides para a determinação do máximo divisor comum de dois números naturais.
A noção de algoritmo é intuitivamente clara mas não é definida formalmente, pois não está claro o que quer dizer "instruções simples e precisas", e o que significa "inteligência necessária para executar as instruções".
Informalmente a tese enuncia que nossa noção de algoritmo pode ser formalizada (sob a forma de funções computáveis) e que computadores podem executar esses algoritmos. Além disso, qualquer computador pode, teoricamente, executar qualquer algoritmo, isto é, o poder computacional teórico de cada computador é o mesmo e não é possível construir um artefato de cálculo mais poderoso que um computador.
A tese pode ser considerada uma lei física, já que não pode ser matematicamente demonstrada.
| Conteúdo |
Tese de Church-Turing
A tese, de acordo com as palavras do próprio Turing, pode ser enunciada como:
- Toda 'função que seria naturalmente considerada computável' pode ser computada por uma Máquina de Turing.
Devido à imprecisão do conceito de uma "função que seria naturalmente considerada computável", a tese não pode ser nem provada nem refutada formalmente.
Qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral; assim, a tese é equivalente a dizer que qualquer linguagem de programação de propósito geral é suficiente para expressar qualquer algoritmo.
História
A tese leva o nome dos matemáticos Alonzo Church e Alan Turing. Em seu artigo "On Computable Numbers, with an Application to the Entscheidungsproblem", de 1936, Alan Turing tentou capturar a noção de algoritmo (então chamado "computabilidade efetiva"), com a introdução de máquinas de Turing. No artigo ele mostrou que o 'Entscheidungsproblem' não pode ser resolvido. Alguns meses antes Alonzo Church provou um resultado similar em "A Note on the Entscheidungsproblem", mas ele usou as noções de funções recursivas e funções lambda-definíveis para descrever formalmente a computabilidade efetiva. Funções lambda-definíveis foram introduzidas por Alonzo Church e Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935), e funções recursivas por Kurt Gödel e Jacques Herbrand (Gödel 1934, Herbrand 1932). Estes dois formalismos descrevem o mesmo conjunto de funções, como mostrado no caso de funções de inteiros positivos por Church e Kleene (Church 1936a, Kleene 1936). Ao ouvir a proposta de Church, Turing logo foi capaz de mostrar que suas máquinas de Turing descrevem o mesmo conjunto de funções (Turing 1936, 263ff).
Sucesso da tese
Desde aquela época muitos outros formalismos foram propostos para descrever a computabilidade efetiva, incluindo funções recursivas, o cálculo lambda, máquinas de registros, sistemas de Post, lógica combinatória e algoritmos de Markov. Foi mostrado que todos esses sistemas computam essencialmente o mesmo conjunto de funções que as máquinas de Turing; sistemas como esses são chamados Turing completos. Como todas as diversas tentativas de formalizar o conceito de algoritmo levaram a resultados equivalentes, geralmente assume-se que a tese de Church-Turing é correta. No entanto, a tese é uma definição, e não um teorema, e portanto não pode ser provada. Ela poderia, no entanto, ser refutada se alguém descobrisse um método que fosse universalmente aceito como um algoritmo efetivo mas que não pudesse ser executado por uma máquina de Turing.
No início do século XX, matemáticos freqüentemente usaram o termo informal efetivamente computável, então foi importante achar uma boa formalização do conceito. Matemáticos modernos usam, em seu lugar, o termo bem-definido Turing-computável (ou apenas computável). Já que a terminologia indefinida caiu em desuso, a questão de como definí-la é agora menos importante.
Leitura adicional
- Hofstadter, Douglas R., Gödel, Escher, Bach: um entrelaçamento de gênios brilhantes, capítulo 17.
Referências
- Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
- Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
- Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
- Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
- Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
- Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
- Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
- Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
- Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
- Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
- Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
- Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
- E. Bernstein, U. Vazirani, Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411–1473
Links externos
- Detailed info on the Church-Turing Hypothesis (Stanford Encyclopedia of Philosophy) - em inglês