Teoria da Computação

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 computabilidade é um forte reforço no que é conhecido como Hipótese de Church ou
Hipótese de Turing-Church:
"A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação"
Em outras palavras, a Hipótese de Church afirma que qualquer outra forma de expressar algoritmos terá, no máximo, a mesma capacidade computacional da Máquina de Turing. Como a noção de algoritmo ou função computável é intuitiva, a Hipótese de Church não é demonstrável. Ela é uma tese, não um teorema, porque não é um resultado matemático: ela simplesmente afirma que um certo conceito informal (algoritmo) corresponde a um certo objeto matemático (máquina de Turing). Não sendo uma instrução matemática, a hipótese de Church não pode ser provada.
Supondo verdadeira a Hipótese de Church, pode-se afirmar que para:
a) Função Computável: É possível construir uma Máquina de Turing (ou formalismo equivalente) que compute a função;
b) Função Não-Computável: Não existe Máquina de Turing (ou formalismo equivalente) que compute a função.

Classes de Solucionabilidade de Problemas
Problema Solucionável:
Um problema é dito Solucionável ou Totalmente Solucionável se existe um algoritmo