MÓDULO 4 - O PROBLEMA DA PARADA - PROBLEMAS NÃO SOLUCIONÁVEIS SOBRE AS MÁQUINAS DE TURING E SOBRE AS GRAMÁTICAS

Prévia do material em texto

Módulo 4 - Máquinas de Turing Universais - O Problema da Parada -
 Problemas Não Solucionáveis sobre as Máquinas de Turing e sobre as 
Gramáticas. 
 
Máquina Universal 
 Uma máquina de Turing Universal é uma máquina de Turing capaz de simular qualquer 
outra apropriadamente codificada. 
 “Processa programas que são codificações de máquinas de Turing.” (Ramos, Vega e 
Neto, 2009). 
 Simula a máquina descrita e produz como resultado o mesmo resultado que a máquina 
simulada produziria. 
 É universal, pois é capaz de executar qualquer algoritmo. 
 
Ordenação lexicográfica 
 
 É possível especificar uma máquina de Turing através de uma descrição passível de ser a 
entrada de outra Máquina de Turing. A seguinte convenção pode ser adotada: 
 Cada estado distinto da máquina de Turing é nomeado por uma cadeia constituída do 
símbolo q, que deve ser sucedido por uma cadeia de símbolos do alfabeto binário. 
 Cada símbolo da cadeia de entrada é nomeado por uma cadeia constituída 
do símbolo “a” e sucedido por uma cadeia de símbolos do alfabeto binário 
 Os estados e os símbolos da cadeia de entrada devem ser ordenados. Pode-se, por 
convenção, ordená-los em ordem lexicográfica crescente de tal forma que: 
 o estado inicial é o primeiro e os estados de aceitação são os últimos; 
 os símbolos especiais são os primeiros na seguinte ordem: (branco, início de fita (·), 
movimento à esquerda (E) e movimento à direita (D)); 
 “M” é um conjunto de quádruplas, obtidas a partir da função de transição g de M e deve 
ser ordenada em ordem lexicográfica crescente. 
 Os estados e os símbolos da cadeia de entrada devem ser ordenados. Pode-se, por 
convenção, ordená-los em ordem lexicográfica crescente de tal forma que: 
o o estado inicial é o primeiro e os estados de aceitação são os últimos; 
o os símbolos especiais são os primeiros na seguinte ordem: (branco, início de fita 
(·), movimento à esquerda (E) e movimento à direita (D)); 
o “M” é um conjunto de quádruplas, obtidas a partir da função de transição g de M 
e deve ser ordenada emordem lexicográfica crescente. 
Exemplo: seja uma MT M, tal que: 
Q = {q0, q1, qf} 
A = {b, >, x} 
F = {qf} 
q0 é o estado inicial; 
b representa “branco”. 
A função de transição é dada como se segue: 
estado Símbolo de entrada g 
q0 x (q1, b) 
q0 b (qf, b) 
q0 > (q0, D) 
q1 x (q0, x) 
q1 b (q0, D) 
q1 > (q1, D) 
 
Tem-se que “ a Máquina de Turing M pode ser descrita pela tabela acima ou seja pela sua 
ordenação lexicográfica. 
M ” = (q00, a100, q01, a000), (q00, a000, q11, a000), (q00, a001, q00, a011), (q01, a100, 
q00, a011), (q01, a000, q00, a011), (q01, a001, q01, a011). 
 
Problema Solucionável (ou decidível) 
 Um problema é dito Solucionável ou Totalmente Solucionável se eixste um 
algoritmo que solucione o problema tal que sempre para para qualquer entrada, com 
uma resposta afirmativa (aceita) ou negativa (rejeita). 
Problema Não-Solucionável (Não decidível) 
 Um problema é dito Não-Solucionável se não existe um algoritmo que solucione 
o problema tal que sempre para, qualquer que seja a entrada. 
 
Problema Parcialmente Solucionável ou Computável 
 Um problema é dito Parcialmente Solucionável ou Computávelse existe um 
algoritmo que solucione o problema tal que pare quando a resposta é afirmativa 
(aceita). Entretanto quando a resposta esperada for negativa, o algoritmo pode parar 
(rejeita) ou permanecer processando indefinidamente. 
 
Problema Completamente Insolúvel 
 Um problema é dito Completamente Insolúvel ou Não-Computável se não existe 
um algoritmo que solucione o problema tal que pare quando a resposta é afirmativa. 
É importante observar que alguns problemas não-solucionáveis são parcialmente 
solucionáveis. Ainda, existem problemas não-solucionáveis que possuem solução 
parcial. 
A Classe dos Problemas Solucionáveis é equivalente à Classe das Linguagens 
Recursivas. 
A Classe dos Problemas Parcialmente Solucionáveis é equivalente à Classes das 
Linguagens Recursivamente Enumeráveis. 
 
Problemas Não solucionáveis sobre Máquinas de Turing 
Provam-se insolúveis os seguintes problemas sobre gramáticas: 
Dada uma máquina de Turing M e uma palavra w, ambas arbitrárias, M para com uma 
entrada w? 
Dada uma máquina de Turing M, M para com a fita de entrada vazia? 
Dada uma máquina de Turing M arbitrária, existe uma palavra que a faça parar? 
Dada uma máquina de Turing M arbitrária, M para com qualquer entrada possível? 
Dadas duas máquinas de Turing M1 e M2 arbitrárias elas param com as mesmas 
entrada”. 
Dada M arbitrária, a Linguagem por ela aceita é regular? É livre de contexto? É 
recursiva? 
Problemas Não solucionáveis sobre Gramáticas; 
Provam-se insolúveis os seguintes problemas sobre gramáticas: 
Para uma dada gramática geral G e uma palavra w, determinar se a palavra w  L(G) 
(L(G) significa: Linguagem gerada pela gramática G). 
Para uma dada gramática G, determinar se a palavra vazia  pertence à Linguagem 
gerada por G, ou seja, L(G). 
Dadas duas gramáticas gerais arbitrárias G1 e G2, determinar se as Linguagens geradas 
pro G1 e G2 são iguais; 
Para uma gramática geral arbitrária G determinar se a Linguagem gerada é um conjunto 
vazio (ou seja, não existem palavras); 
Propriedades das Linguagens Recursivas 
Diz-se que uma máquina de Turing M enumera a Linguagem L, se e somente se, para 
um determinado estado q de M, ao analisar uma fita de entrada com apenas um símbolo 
branco, passa periodicamente por um determinado estado q (q não pode ser estado de 
parada), insere na fita de entrada a palavra w que pertence à linguagem L. 
Se as palavras forem enumeradas lexicograficamente por M, diz-se que a linguagem L é 
recursiva. 
Teorema: Uma Linguagem é recursiva se e somente se for Turing-enumerável 
lexicograficamente. 
Linguagens Não Recursivamente Enumeráveis 
É provado que existem linguagens que não são recursivamente enumeráveis. 
Seja o alfabeto A = {a, b} 
É possível codificar todas as máquinas de Turing como uma palavra sobre o alfabeto A, 
de tal forma que cada código represente uma única máquina de Turing Ti . 
A linguagem: L = {Xi | Xi não é aceita por Ti} não é recursivamente enumerável. 
 
Exercício Resolvido 1: Considere a seguinte definição do problema da Parada: 
Definição (GERSTING, 2000): “existe um algoritmo para decidir, dadas uma máquina 
de Turing T qualquer e uma cadeia , se T, começando com uma fita contendo , vai 
parar?” 
Teorema sobre o problema da parada: o problema da parada é insolúvel. 
Pede-se argumentos que mostrem que o problema da Parada é insolúvel. (Observação: 
não se trata de uma demonstração formal, apenas uma argumentação) 
Tem-se que: 
Considere uma máquina de Turing X capaz de analisar qualquer máquina de Turing T. 
As duas únicas possibilidades de X parar são descritas a seguir: 
I - A Máquina de Turing X deve parar com a fita contendo apenas um algarismo 1, se e 
somente se, T aceitar uma cadeia α. 
II - A Máquina de Turing X deve parar com a fita contendo apenas um algarismo 0, se e 
somente se T, nunca parar ao processar a cadeia α. 
Considere-se por absurdo que a máquina de Turing. X possa ser projetada. Uma vez que 
seja possível o projeto de X, é possível modificar X e obter uma máquina de Turing Y 
com as seguintes características: 
I - A Máquina de Turing Y não para se e somente se, T parar ao processar a cadeia α. 
(basta acrescentar a X um loop infinito). 
II - A Máquina de Turing Y deve parar com a fita contendo apenas um algarismo 0, se e 
somente se T, nunca parar ao processar a cadeia α. 
É portanto possível criar uma máquina de Turing Z que copie a cadeia de entrada α e 
em seguida submeta à máquina de Turing Y, a cadeia α α 
Sabe-se que é possível obter-se uma cadeia “M” que represente a máquina de Turing M, 
qualquer que seja. 
Assim sendo, considere-se a situação em que Z processasua própria representação “Z”. 
O desdobramento imediato é o seguinte paradoxo: 
Z para,ao processar “Z” porque Y (que faz parte de Z) não para ao processar (“Z”, “Z”). 
Ou ainda, Z não para ao processar “Z”, porque Y para ao processar (“Z”, “Z”). 
Exercício Resolvido 2 : É um exemplo de problema não solucionável: 
a) Não existem problemas não solucionáveis. 
b) Minimização de um autômato finito. 
c) Detector universal de loops. 
d) Reconhecimento de linguagens recursivas. 
e) Tratamento de não determinismos em linguagens regulares. 
Resposta: a alternativa correta é a c). O detector universal de loops, diz respeito ao 
Problema da Parada. 
 
 
Referências 
Gersting, J. L. Fundamentos Matemáticos para a Ciência da Computação Rio de 
Janeiro: LTC, 2001. 
Lewis H. R. ; Papadimitrious, C. H. Elementos da Teoria da Computação Porto Alegre: 
Bookman, 200 4. 
RAMOS, Marcus Vinicius Midena. NETO; João José. VEGA, Italo Santiago. 
Linguagens Formais. Teoria, Modelagem e Implementação Porto Alegre: Bookman, 
2009.