Tese de Church-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:

1. 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.
2. O algoritmo sempre produz resultado em um número finito de passos.
3. O algoritmo pode, a princípio, ser executado por um ser humano com apenas papel e lápis.
4. 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 e que todos os computadores são "iguais", variando apenas a capacidade de processamento.

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 formalmente provada, mas pode ser refutada caso seja descoberta uma máquina teórica mais poderosa que a máquina de turing.

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

Ver artigo principal: História da tese de Church-Turing

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.

Utilização informal em provas

Provas na teoria da computabilidade comummente usam a tese de Church-Turing de um jeito informal para estabelecer a computabilidade de funções, evitando os detalhes (muitas vezes muito longos) que normalmente seriam mostrados em uma prova mais formal. Para estabelecer que uma função é computável usando uma máquina de Turing, normalmente é considerado suficiente dar uma descrição informal de como a função pode ser efetivamente computada, e então concluir "De acordo com a tese de Church-Turing" que a função é Turing computável. Dirk van Dalen (em Gabbay 2001:284) dá o seguinte exemplo a fim de ilustrar esse uso informal da tese de Church-Turing:

EXEMPLO: Cada conjunto RE infinito contém um conjunto recursivo infinito.

Prova: Seja A um RE infinito. Nós listamos os elementos de A como n₀, n₁, n₂, n₃, ...

A partir dessa lista, extraímos uma sublista crescente: faça m₀=n₀, após um número finito de passos acharemos um n_k tal que n_k > m₀, faça m₁=n_k. Nós repetimos esse processo para achar m₂ > m₁, etc. Isso produz uma listagem eficaz do subconjunto B={m₀,m₁,m₂,...} de A, com a propriedade m_i < m_i+1.

Reivindicação: B é decidível. Para testarmos k em B precisamos testar se k=m_i para algum i. Já que a sequência de m_i's está aumentando, nós temos que produzir no máximo k+1 elementos da lista e comparar com k. Se nenhum é igual a k, então k não está em B. Já que esse teste é eficiente, B é decidível e, de acordo com a tese de Church, recursivo.

A fim de tornar o exemplo acima completamente rigoroso, deveríamos cuidadosamente construir uma Máquina de Turing, ou função-λ, ou cuidadosamente usar axiomas recursivos, ou na melhor das hipóteses habilmente usar vários teoremas da teoria da computabilidade. Mas já que teoristas da computabilidade acreditam que a computabilidade de Turing corretamente captura o que se pode ser computado efetivamente, e porque um procedimento eficaz é dado em linguagem informal para decidir o conjunto B, teóricos da computabilidade aceitam isso como prova que o conjunto é de fato recursivo.

Como regra geral, a tese de Church-Turing só deve ser usada para simplificar provas em casos onde o escritor e o leitor sejam capazes de, facilmente (mas não necessariamente, rapidamente) produzir uma prova rigorosa se a mesma for pedida.

Variações

O Sucesso da tese de Church-Turing acarretou em várias outras teses, baseadas na de Church-Turing mas com algumas variações, a serem propostas. Por exemplo, a Physical Church-Turing thesis (PCTT) afirma:

"De acordo com a PCTT, todas as funções fisicamente computáveis, são Turing-computáveis"

A tese de Church-Turing não menciona nada sobre a eficiência com que um modelo computacional pode simular outro. Foi provado que uma Máquina de Turing multi-fita só sofre uma desaceleração logarítmica ao simular qualquer Máquina de Turing. Nenhum resultado como esse foi provado para um arbitrário, mas razoável , modelo computacional. Uma variação da tese de Church-Turing que trata desse problema é a Feasibility Thesis ou (Classical) Complexity-Theoretic Church–Turing Thesis (SCTT), as quais não são de Church ou Turing, mas sim foi realizado gradualmente no desenvolvimento da teoria da complexidade. Ele afirma:

"Uma Máquina de Turing probabilística pode eficientemente simular qualquer modelo computacional realístico."

A palavra "eficientemente" significa problemas que são redutíveis em tempo polinomial. Essa tese foi originalmente chamada "Computational Complexity-Theoretic Church-Turing Thesis" de Ethan Bernstein e Umesh Vazirani (1997). A "Computational Complexity-Theoretic Church-Turing Thesis" afirma que todos os modelos computacionais razoáveis pertencem a mesma classe de problemas que podem ser computados em tempo polinomial. Assumindo a conjectura de que o tempo polinomial probabilístico (BPP) é igual ao tempo polinomial determinístico (P), a palavra probabilístico é opcional na Computational Complexity-Theoretic Church-Turing Thesis. Uma tese similar, chamada de Tese Invariante, foi introduzida por Cees F. Slot e Peter van Emde Boas. Ela afirma: "Máquinas Razoáveis podem simular uma as outras dentro limitadas polinomialmente em sobrecarga no tempo e como fator constante de sobrecarga no espaço. A tese originalmente foi publicada na STOC'84, foi a primeira tese a mostrar que a sobrecarga de tempo polinomial e sobrecarga constante no espaço poderiam ser realizados simultaneamente para uma simulação de uma máquina de acesso aleatório em uma Máquina de Turing.

Se computadores quânticos pudessem ser produzidos em grande escala, os mesmos poderiam invalidar a Computational Complexity-Theoretic Church-Turing Thesis, uma vez que também é suspeitado que tempo quantum polinomial (BQP) é maior que BPP. Em outras palavras, existem algoritmos quânticos eficientes que realizam tarefas que não possuem algoritmos probabilísticos eficientes, por exemplo, fatorar inteiros. Eles, no entanto, não iriam invalidar a tese de Church-Turing original, já que um computador quântico pode sempre ser simulado por uma Máquina de Turing, mas eles invalidariam a Classical Computational Complexity-Theoretic Church-Turing Thesis por motivos de eficiência. Consequentemente , a Quantum Complexity-Theoretic Church-Turing Thesis afirma:

"Uma Máquina de Turing quântica pode eficientemente simular qualquer modelo computacional realístico;"

Eugene Eberbach e Peter Wegner afirmam que a tese de Church-Turing é, algumas vezes, interpretada de forma demasiadamente ampla, afirmando que "a mais ampla afirmação de que algoritmos precisamente capturam o que pode ser computado é inválido". Eles afirmam que as formas de computação não englobadas na tese são relevantes hoje em dia, termos os quais eles chamam de computação super-Turing.

Implicações Filosóficas

A tese de Church-Turing tem algumas implicações profundas para a filosofia da mente, no entanto muitas interpretações filosóficas da tese envolvem erros básicos de interpretação da afirmação da tese. Jack Copeland afirma que a questão da existência de processos físicos e determinísticos é uma questão empírica aberta, além disso, ele também afirma que a questão se qualquer desses processos estão envolvidos no funcionamento do cérebro humano também é uma questão empírica aberta. Existem também várias questões abertas sobre o relacionamento entre a tese de Church-Turing e à física, e a possibilidade da Hipercomputação. Quando aplicado a física, a tese tem possíveis significados:

1. O universo é equivalente a uma Máquina de Turing; então, computar funções não-recursivas é fisicamente impossível. Isso foi chamado de a Tese Forte de Chuch-Turing e é a origem da Física Digital.
2. O universo não é equivalente a uma máquina de Turing (i.e., as leis da física são não Turing-computáveis), mas eventos físicos incomputáveis não são aproveitáveis para a construção de um hipercomputador. Por exemplo, um universo no qual a física envolve números reais, em oposição aos reais computáveis, pode entrar nesta categoria.
3. O universo é um hipercomputador, e é possível construir dispositivos físicos para aproveitar essa propriedade e calcular funções não-recursivas. Por exemplo, a questão de se todos os eventos da mecânica quântica são Turing-computável é uma questão aberta, embora se saiba que os modelos rigorosos como a Máquina de Turing Quântica são deterministicamente equivalentes a Máquinas de Turing (elas não são necessariamente equivalentes em eficiência). John Lucas e Roger Penrose sugeriram que a mente humana pode ser um resultado de uma computação não algorítmica quântica-melhorada, apesar de não haver evidência científica para provar essa proposição.

Existem várias outras possibilidades técnicas que ficam fora, ou entre essas três citadas acima, mas essas servem para ilustrar a amplitude do conceito.

Funções Não-Computáveis

Pode-se definir formalmente funções que não são computáveis. Um exemplo bem conhecido desse tipo de função é o Algoritmo do Castor. Esta função pega uma entrada n e retorna o maior número de símbolos que uma máquina de turing com n estados pode mostrar antes de parar. Achar um limite superior nesta função é equivalente a resolver o problema da parada, um problema conhecido por não ter solução pelas máquinas de turing. Já que o Algoritmo do Castor não pode ser computada por máquinas de turing, a tese de Church-Turing afirma que esta função não pode ser efetivamente computada por qualquer método. Para mais informações veja o artigo sobre o castor ocupado.

Alguns modelos computacionais permitem a computação de (Church-Turing) funções não computáveis. São conhecidos como Hipercomputação. Mark Burgin argumenta que algoritmos super-recursivos como máquinas de Turing indutivas refutam a tese de Church-Turing. Seu argumento está numa definição mais ampla de algoritmo do que a usual e que funções não-computáveis obtidas de algumas máquinas de turing indutivas são chamadas computáveis. Essa interpretação da tese de Church-Turing difere da interpretação comumente aceita em Teoria da Computação. O argumento que algoritmos super-recursivos são de fato algoritmos no sentido da tese de Church-Turing não teve ampla aceitação entre a comunidade de investigação da computação.

Leitura adicional

• Hofstadter, Douglas R., Gödel, Escher, Bach: um entrelaçamento de gênios brilhantes, capítulo 17.

Bibliografia

• 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

Ligações externas

• Detailed info on the Church-Turing Hypothesis (Stanford Encyclopedia of Philosophy) - em inglês

Ver também

• Lógica da computabilidade
• História da tese de Church-Turing
• Computação interativa
• Teoria da computabilidade