Tese de Church-Turing
De Wikipedia, a enciclopédia encyclopedia
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 e que todos os computadores são "iguais", variando apenas a capacidade de processamento.