Teoria da Computação
Tese de Church, Classes de Solucionabilidade e Problemas de Decisão
Éder Gusatto, Helena Braga, José Mathias Gusso
29/05/2003

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 …exibir mais conteúdo…

Universo de Todos os Problemas

Solucionáveis

Não-Solucionáveis

Parcialmente
Solucionáveis

Completamente
Insolúveis

Computáveis

Não-Computáveis

Relação entre as classes de problemas

Problemas de Decisão
Problemas de Decisão:
Os problemas tratados são do tipo sim/não. A idéia básica é verificar se a função associada a eles é ou não computável em uma Máquina Universal. Como, pela Hipótese de Church, uma Máquina Universal é o dispositivo mais geral de computação, se a solução de um problema não puder ser expressa por uma
Máquina Universal, então tal problema é completamente insolúvel.
A essência de um problema de decisão é dada pela seguinte idéia: dado um programa P para uma máquina universal M, decidir se a função computada (P, M) é total (ou seja, se a correspondente computação é finita). Assim, não-solucionabilidade refere-se à inexistência de um método geral e efetivo para decidir se um programa para uma máquina universal pára para qualquer entrada. É importante reparar que o que está sendo discutido são métodos gerais. Portanto, é perfeitamente possível existir métodos específicos para programas particulares.
A existência de problemas não-solucionáveis é importante por diversas razões como, por exemplo:
• Alguns desses problemas não-solucionáveis permitem estabelecer, por si sós, importantes resultados
para