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.
Veja mais na Wikipédia.org...
Free Download Now!
