Tese de chuck

[pic]

Angelica Cristina Paulino Hirosue RA 0993003302
Ciência da Computação – 6° semestre

Trabalho de Teoria da Computação

Introdução à Tese de Church

Turing propôs um modelo abstrato de computação, conhecido como Máquina de Turing, com o objetivo de explorar os limites da capacidade de expressar soluções de problemas. Trata-se, portanto, de uma proposta de definição formal da noção intuitiva de algoritmo. Diversos outros trabalhos, como Máquina de Post (Post - 1936) e Funções Recursivas (Kleene - 1936), bem como a Máquina Norma e o Autômato com Pilhas, resultaram em conceitos equivalentes ao de Turing. O fato de todos esses trabalhos independentes gerarem o mesmo resultado em termos de capacidade de expressar computabilidade é um forte reforço no que é conhecido como Hipótese de Church ou Hipótese de Turing-Church:

Resumo:

A Tese de Church é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar. Afirma que qualquer outra forma de expressar algoritmos terá, no máximo, a mesma capacidade computacional da Máquina de Turing. Afirmando também que qualquer função computável pode ser processada por uma Máquina de Turing, que existe um algoritmo expresso na forma de Máquina de Turing capaz de processar a função. Como a noção de algoritmo ou função computável é intuitiva, a Hipótese de Church não é demonstrável. Supondo verdadeira a Hipótese de Church, pode-se afirmar que para Função Computável é possível construir uma Máquina de Turing (ou formalismo equivalente) que compute a função e que para Função Não-Computável não existe Máquina de Turing (ou formalismo equivalente) que compute a