Máquinas de Turing: Definições e Exemplos

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
 
 
 
 
 
 
 
 
 
 
 
 
Descrição de Alto-nível de Máquinas de Turing: 
Definições, Convenções e Exemplos 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Disciplina: GCC108 – Teoria da Computação 
Material Complementar das aulas sobre Máquinas de Turing 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
1) Descrições de Máquinas de Turing 
Foram apresentadas no curso duas alternativas para a descrição de Máquinas de Turing (MT): 
a definição formal e a definição de alto-nível. 
Descrição Formal 
Cada elemento da sétupla é formalmente definido; a função de 
transição de estados, , é representada sistematicamente através de um diagrama de estados, 
uma tabela, ou uma lista. 
Descrição de Alto-Nível 
Descrição em formato de pseudo-código. Neste formato, a palavra de entrada é definida 
explicitamente e as operações são descritas através de uma conjuntos de passos de 
processamento. Laços (loops) e ramificações (branches) são representados através de 
transições entre estes passos. 
Exemplo: 
MT = {Na palavra de entrada p: 
Passo 1: Leia o símbolo da fita. Se o símbolo lido for a, Rejeite. Caso contrário, mova 
a cabeça le para a direira e vá para o Passo 2. 
Passo 2: Leia o símbolo da fita. Se o símbolo lido for b, Rejeite. Se o símbolo lido for 
a, mova a cabeça le para a direita e vá para o Passo 1. Caso contrário, mova a cabeça 
de le para a direira e vá para o Passo 3. 
Passo 3: ...} 
 
Os objetos e operações utilizados no pseudo-código são definidos de acordo com os conceitos 
envolvendo Máquinas de Turing. Temos dois objetos básicos e quatro operações básicas: 
Objetos: Fita e cabeça le. 
Operações: Leitura de símbolo na fita; escrita de símbolo na fita; movimento da 
cabeça le para a esquerda; movimento da cabeça le. 
À partir das operações básicas, outras operações, mais complexas, podem ser utilizadas de 
acordo com as convenções definidas previamente (apresentadas na próxima seção), e com os 
objetivos do exercício. Como regra geral, em exercícios envolvendo a solução de problemas 
básicos deverão ser usadas operações básicas; exercícios envolvendo a solução de problemas 
complexos permitirão o uso de operações mais complexas. 
O pseudo-código poderá conter comentários representados da seguinte forma: 
/* Comentário */ ou // Comentário 
A seguir, apresentaremos algumas convenções que poderão ser usadas na resolução de 
qualquer exercício. 
2) Convenções 
 Vamos assumir que marcadores não fazem parte do alfabeto de entrada e, portanto, 
não é necessário explicitar isso na definição da MT; 
 Leia o símbolo atual da fita leia o símbolo da fita que encontra-se sob a cabeça le; 
 Quando não especificado explicitamente o contrário, o movimento da cabeça le é da 
esquerda para a direita; 
o Exemplo: “Leia o próximo símbolo” “Leia o próximo símbolo à direita da 
posição atual da cabeça le“; 
o Note que na definição formal, o movimento da cabeça le para a direita seria 
realizado na transição anterior; 
 Rebobinar a fita retorne a cabeça le para o ínicio da fita; 
 Final da fita leitura do símbolo “˽“. 
 
3) Exemplo 
No exemplo a seguir, iremos apresentar três soluções para um exercício em diferentes níveis. 
As duas primeiras são soluções válidas para o exercício, ao passo que a terceira não é. 
Exercício 1: Projete uma MT que reconheça a linguagem | . Descreva-a 
em alto-nível. 
Solução 1: 
 Na palavra de entrada : 
Passo 1: Leia o símbolo atual da fita e realize uma das seguintes ações: 
1. Se for o símbolo (marcador), mova a cabeça para direita e repita Passo 1; 
2. Se for o símbolo , sobrescreva com , mova a cabeça le para a direita e vá 
para o Passo 2; 
3. Se for o final da fita, Aceite. 
4. Se for qualquer outro símbolo, Rejeite. 
 
 
Passo 2: Leia o símbolo atual da fita e realize uma das seguintes ações: 
1. Se for o símbolo ou o símbolo , mova a cabeça para direita e repita Passo 
2; 
2. Se for o símbolo , sobrescreva com , mova a cabeça le para a direita e vá 
para o Passo 3; 
3. Se for o final da fita, Rejeite. 
4. Se for qualquer outro símbolo, Rejeite. 
Passo 3: Leia o símbolo atual da fita e realize uma das seguintes ações: 
1. Se for o símbolo ou o símbolo , mova a cabeça para direita e repita Passo 
2; 
2. Se for o símbolo , sobrescreva com , rebobine a fita e vá para o Passo 1; 
3. Se for o final da fita, Rejeite. 
4. Se for qualquer outro símbolo, Rejeite.} 
/* Note que os testes em cada passo são realizados ordenamente. Portanto, teste só é 
realizado se o teste falha */ 
Soluçao 2: 
 Na palavra de entrada : 
Passo 1: Avance a cabeça le e procure pelo primeiro símbolo diferente de 
1. Se for o símbolo , sobrescreva com , vá para o Passo 2; 
2. Se for o final da fita, Aceite. 
3. Se for qualquer outro símbolo, Rejeite. 
Passo 2: Avance a cabeça le e procure pelo primeiro símbolo diferente de e de a 
1. Se for o símbolo , sobrescreva com , mova a cabeça le para a direita e vá 
para o Passo 3; 
2. Se for o final da fita ou qualquer outro símbolo, Rejeite. 
Passo 3: Avance a cabeça le e procure pelo primeiro símbolo diferente de e de b 
1. Se for o símbolo , sobrescreva com , rebobine a fita e vá para o Passo 1; 
2. Se for o final da fita ou qualquer outro símbolo, Rejeite} 
/* Solução 2 apresenta uma descrição mais alto-nível que Solução 1, mas ainda é válida*/ 
Solução 3: 
 Na palavra de entrada : 
Passo 1: Verifique se a palavra é vazia. Se for o caso, Aceite. 
Passo 2: Verifique se a palavra é composta por uma sequência de a’s, seguida por uma 
sequência de b’s que, por sua vez, é seguida por uma sequência de c’s. Se for o caso, 
vá para o Passo 3. Caso contrário, Rejeite. 
Passo 3: Verifique se quantidade de a’s, b’s, e c’s é a mesma. Se for o caso, Aceite. 
Caso contrário, Rejeite.} 
/*SOLUÇÃO INVÁLIDA: Solução 3 apresenta a correta intuição para resolver o problema, 
mas é demasiadamente de alto-nível. O objetivo do exercício é que seja demontrada a 
habilidade para controlar a sequência e quantidade dos símbolos através de operações sobre a 
fita e a cabeça le; esta habilidade não ficou demonstrada na Solução 3.*/ 
 
Considere agora o seguinte exércício: 
Exercício 2: Projete uma MT que receba uma lista de palavras sobre o alfabeto {a,b} 
separadas por # e que aceite se todas palavras são diferentes. Formalmente, a linguage é L = 
{#p1#p2#...#pk# | cada pi ϵ {a,b}
+
 e para . Descreva-a em alto-nível. 
Solução 
A solução para este exercício é apresentada em outro lugar. O ponto a ser considerado aqui é 
que o objetivo deste exercício é avaliar a capacidade do aluno de simular laços aninhados em 
uma MT. 
Neste contexto, o teste de igualdade entre palavras ( poderia ser definido neste 
exercício como uma operação do pseudo-código. Em outras palavras, não é necessário que o 
aluno descreva explicitamente as operações da MT necessárias para verificar se duas palavras 
são iguais. Neste caso, o trecho de código abaixo seria válido: 
Passo x: Compare as duas palavras à direita de cada marcador. Se forem iguais, Rejeite. 
Caso contrário vá para o Passo . 
 
 
 
4) Considerações Finais 
O formato para a descrição de MTs apresentado neste documento não é o único formato 
possível ou aceitável. O aluno poderá fazer adaptações ou, até mesmo, utilizar um formato 
próprio. Entrentanto, o nível de organização e a clareza dos exemplos acima devem ser 
reproduzidos pelo aluno. 
Finalmente, não é possível determinar formalmente e precisamente o nível de abstração 
adequado para a decrição de uma MT já que o mesmo depende do objetivo do exercício. De 
qualquer maneira, indicações de operações de alto-nível permitidas em um exercício serão 
apresentadas no enunciado do exercício. Em caso de dúvida, o aluno deverá consultaro 
professor.