Tese de chuck

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (268 palavras )
  • Download(s) : 0
  • Publicado : 9 de outubro de 2012
Ler documento completo
Amostra do texto
[pic]


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

Trabalho de Teoria da Computação

Introdução à Tese de ChurchTuring 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 omesmo 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 quequalquer 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 serprocessada 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çãocomputá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áquinade 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 função.
tracking img