Faculdade Anhanguera de Taubaté – Ciência da Computação
Teoria
da
Computação
Aula
Prof. Fabiano Sabha
1
5
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Tese
de
Church
Prof. Fabiano Sabha
2
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Nosso Plano de Ensino
Prof. Fabiano Sabha
3
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Um pouco de revisão...
 Programas
Um conjunto de operações e testes compostos de
acordo com uma estrutura de controle
 Máquinas
Interpreta Programas e possui uma interpretação para
cada operação ou teste que constituem o programa.
Prof. Fabiano Sabha
4
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Equivalência de programas e máquinas
 Forte de Programas: Um par de programas pertence à
relação se as correspondentes funções computadas
coincidem para qualquer máquina;
 Programas em uma Máquina: Um par de programas
pertence à relação se as correspondentes funções
computadas coincidem para uma dada máquina;
 Máquinas: Um par de máquina pertence à relação se as
máquinas podem se simular mutuamente. A simulação de
uma máquina por outra pode ser feita usando programas
diferentes.
Prof. Fabiano Sabha
5
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Operações e Testes
 Não é necessário saber qual a natureza precisa das operações e dos
testes que constituem as instruções. Serão conhecidas pelos seus
nomes.
Identificadores de Operações: F, G, H, ...
Identificadores de Testes: T1, T2, T3, ...
 Um teste é uma operação de um tipo especial a qual produz somente
um dos dois possíveis valores verdade, ou seja, verdadeiro ou falso,
denotados por: v e f, respectivamente.
 Uma operação que não faz coisa alguma, denominada: operação vazia,
denotada pelo símbolo 
Prof. Fabiano Sabha
6
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Um pouco mais sobre máquinas...
 Máquina universal
Se for possível representar qualquer algoritmo como um
programa, em tal maquina,então esta é denominada
máquina Universal.
Realiza três operações básicas:
- Operação de incrementar 1
- Operação de decrementar 1
- Teste se o valor armazenado é ZERO.
Prof. Fabiano Sabha
7
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Um pouco mais sobre máquinas...
 Máquina de Turing
Proposta por Alan Turing em 1936, é o modelo mais
utilizado como formalização de algoritmos.
O



modelo formal é baseado em:
Uma fita (Entrada/Saída/Rascunho)
Uma unidade de controle
Um programa
Prof. Fabiano Sabha
8
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
Um pouco mais sobre máquinas...
 Máquina de Turing
É um modelo abstrato de um computador que se restringe
apenas aos aspectos lógicos do seu funcionamento e a sua
implementação.
Prof. Fabiano Sabha
9
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
A 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.
Prof. Fabiano Sabha
10
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
A Tese de Church
 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”
Prof. Fabiano Sabha
11
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
A Tese de Church
 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.
Prof. Fabiano Sabha
12
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
A Tese de Church
 Afirma 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 intuitiva de algoritmo não é
matematicamente precisa, é impossível formalizar uma
demonstração de que a Máquina de Turing é,
efetivamente, o mais genérico dispositivo de computação.
Prof. Fabiano Sabha
13
Teoria da Computação
Faculdade Anhanguera de Taubaté – Ciência da Computação
A Tese de Church
 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.
Prof. Fabiano Sabha
14
Teoria da Computação