MÓDULO 3 - TESE DE TURING CHURCH

Prévia do material em texto

Módulo 3 – Hipótese de Turing – Church 
 
"...A tese de Turing- Chuch diz respeito à noção de um método mecânico e efetivo no 
contexto da Lógica e Matemática. Efetivo e seu sinônimo mecânico, são termos destas 
disciplinas. Não apresentam o significado do nosso dia-a-dia. 
Um método, ou procedimento, M, que é empregado para se obter um resultad 
o desejado é denominado “efetivo” ou mecânico. 
Assim M: 
 Deve ser descrito em um número finito de instruções exatas. (Cada 
instrução sendo expressa por um número finito de símbolos); 
 Se M não apresentar erros, deve produzir o resultado desejado em um 
número finito de etapas; 
 M pode ser realizado por um ser humano sem o auxílio de uma máquina, 
ou seja, empregando apenas “lápis e papel”; 
 O método M não deve exigir nenhuma inferência e nem mesmo 
inventividade do ser humano que o executa." (Zalta, E. N.) 
 
O que é um algoritmo? (Cormen, Leiserson) 
“Informalmente, um algoritmo é qualquer procedimento computacional que recebe 
como entrada um ou mais valores e produz como saída um ou mais valores. Um 
algoritmo é portanto uma seqüência etapas computacionais que transformam valores 
de entrada para valores de saída” . 
Tese de Turing-Church: "As máquinas de Turing são versões formais de algoritmos 
e nenhum procedimento computacional é considerado um algoritmo a não ser que 
possa ser apresentado na forma de uma máquina de Turing" (José Neto, J.). 
Estabelece-se assim, a equivalência entre algoritmos e a Máquina de Turing 
Hipótese de Turing – Church: “Uma função da teoria dos números é computável por 
um algoritmo se, e somente se, for computável por Turing.” 
Este enunciado da hipótese de Turing – Chuch é contemplado para a computação dos 
números inteiros. Sim, a máquina de Turing pode executar cálculos de números 
inteiros. Considere-se o seguinte exemplo: 
Função incrementa(n), definida como: 
 incrementa(n) = n + 1 se n  0 e 
 incrementa(n) é indefinida para n < 0. 
 Adota-se representação unária, tal que I é a representação do número inteiro 0 
e In é a representação do número inteiro n – 1, n >1. 
Tem-se que: 
g(q0, >) = (q0, >, D) 
g(q0, I) = (q0, I, D) 
g(q0, ) = (qf, I, D) 
 
Observe-se a figura seguinte: 
> I I I   ...
q0
> I I I   ...
q0
> I I I I  ...
qf
> I I I   ...
q0
> I I I   ...
q0
> I I I   ...
q0
 
Figura 1 – A função Incrementa (2) 
Máquinas equivalentes à Máquina de Turing 
Há provas formais que demonstram que o dispositivo da MT com fita infinita possui 
exatamente o poder computacional de qualquer outra versão estendida, tais como 
as seguintes: 
 Múltiplas trilhas; 
 Múltiplas fitas; 
 Múltiplos cursores; 
 Fita ilimitada em ambos os sentidos; 
 Transições que deslocam o cursor um número variável de posições; 
 Transições sem leitura ou gravação de símbolos; 
 Máquinas de Turing Multidimensionais; 
 Máquinas de Turing com uma estrutura de memória auxiliar organizada em 
pilha. 
Máquinas de Turing Não- Determinísticas 
Nas máquinas de Turing, a função de transição g remete para o não determinismo 
inerente aos dispositivos aceitadores apresentados. Em outras palavras: dada uma 
mesma combinação de estado corrente e de símbolo na fita de trabalho, é possível 
especificar múltiplas transições. 
Exemplo: 
 g(q1, a) = (q1, b, D) g(q1, a) = (q2, b, D) 
 g(q1, a) = (q3, b, D)g(q1, a) = (q2, b, E) 
 
Exercício Resolvido 1: A Máquina de Turing permite a computação de números 
naturais. Seja I um símbolo fixo não-branco. Um número natural n pode ser 
representado em notação unária, pela cadeia de símbolos I, de comprimento n+1. 
Considerando esta definição, selecione a representação unária para os números 0, 1 
e 2, respectivamente, com I =0 
Tem-se: 
(0)10 = (0)1 
(1)10 = (00)1 
(2)10 = (000)1 
 
Exercício Resolvido 2: Relativamente à Hipótese de Church, responda: 
a) Quais as implicações da Hipótese de Church? 
Pela Hipótese de Church, as máquinas de Turing são versões formais dos algoritmos. 
Adotar tal modelo de algoritmo implica na possibilidade de formalmente se provar que 
certos problemas não podem ser resolvidos por nenhum algoritmo. 
b) Por que a Hipótese de Church é assim denominada, em vez de Teorema de 
Church? 
A Hipótese de Church não é um resultado formalmente provado. 
Referências: 
Cormen T. H., Leiserson C. E. ; Rivest, C. S. Algoritmos Campus, 2012. 
Lewis H. R. ; Papadimitrious, C. H. Elementos da Teoria da Computação 
RAMOS, Marcus Vinicius Midena. NETO; João José. VEGA, Italo Santiago. 
Linguagens Formais. Teoria, Modelagem e Implementação Porto Alegre: Bookman, 
2009. 
Zalta, E. N. Stanford Encyclopedia of Philisophy disponível em 
http://plato.stanford.edu/entries/church-turing/. Última data de acesso: 29 de março de 
2016) 
 
http://plato.stanford.edu/entries/church-turing/