Gramática

Universidade de Caxias do Sul
CCTI – Centro de Computação e Tecnologia da Informação

Trabalho de Fundamentos Teóricos da Computação –Tese de Church
Orientação: este trabalho deverá ser realizado em duplas. Ele deverá ser realizado e postado no webfólio na aula até o dia 03 de julho às 22h35min
Introdução
“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.”
Com base na introdução sobre Tese de Church-Turing acima, seu grupo deve ler a respeito desta tese e explicar termos/conceitos relacionados a ela.
Instruções:
1. Explicar cada um dos conceitos a seguir. Eles estão relacionados com a Tese de Church-Turing.
a) Função Computável
b) Função