toeoria

INSTITUTO DE COMPUTAÇÃO LISTA DE EXERCÍCIOS DE TEORIA DA COMPUTAÇÃO – 2013.2 PROFSSORA ELIANA ALMEIDA
• Sobre Máquinas de Turing (MT) e o problema da parada • Construa MT que reconheça: ▪ L = {am bn / m ≠ n} ▪ L = {xwwRy / x, y, w ∈ {0, 1}* e | x | >= | y|}
1. Mostre que o problema da parada é indecidível para linguagens de alto nível (linguagens que contém procedimentos e o comando enquanto – repetição indefinida)
2. Descreva uma Máquina de Turing que resolva o seguinte problema de decisão: Dada uma MT arbitrária M e uma palavra de entrada w, a computação de M com entrada w irá parar em menos de 1000 transições?
3. Descreva sobre a Tese de Church-Turing e explique porque ela não foi provada.
4. Prove a indecidibilidade do Problema da Parada. Identifique nesta prova onde o teorema da diagonal de Cantor é aplicado.
5. Prove que o o seguinte problema de decisão é decidível: Dada uma MT M, determinar se M escreve algum símbolo diferente do branco, para a entrada e (símbolo vazio)
6. Prove que o seguinte problema de decisão é indecidível: Dados uma MT M, uma palavra w e um estado q de M, determinar se a computação de M para a entrada w atinge o estado q.
Resp:
1-
-Considere uma MT M e uma entrada w;
-Simule M sobre a entrada
-Se_M entra em seu estado de aceitação, aceita; se _ entra no estado de rejeição, rejeita;
Se M entrar em loop sobre w, a maquina entra em loop.
2- considerando o possivel loop a máquina não é aceita. E caso a entrada não for aceita, rejeita;
3- é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar. O algoritmo consiste de um conjunto finito de instruções simples e precisas, que são descritas com um número finito de símbolos.
O algoritmo sempre produz resultado em um número finito de passos.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