MaquinasTuring
88 pág.

MaquinasTuring


DisciplinaTeoria da Computação545 materiais16.685 seguidores
Pré-visualização4 páginas
em \u201cloop infinito\u201d e nunca 
termina) 
\uf0a7 É difícil diferenciar entre MTs de demoram bastante 
para produzir uma saída daquelas que entram em loop 
\uf0a7 Uma MT falha em aceitar uma palavra entrando no 
estado de rejeição ou entrando em loop 
\uf0a7 Um Decididor é uma MT que sempre produz Aceita ou 
Rejeita (fazem uma decisão) como resultado 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Turing Decidíveis 
\uf0a7 Uma linguagem é chamada Turing decidível se 
alguma MT a decide 
\uf0a7 Estas linguagens são também chamadas linguagens 
recursivas 
 
 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relação entre Linguagens 
Reconhecíveis e Decidíveis 
\uf0a7 Toda linguagem decidível é também Turing 
reconhecível. Entretanto algumas linguagens 
são Turing reconhecíveis mas não decidíveis 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
\uf0a7 Projete uma MT que reconheça a linguagem 
A = { anbncn| n>=0 }. Descreva-a em alto-nível 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 
\uf0a7 Projete uma MT que reconheça a seguinte 
linguagem L= {p| p contém um número igual 
de 0s e 1s} 
 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3 
\uf0a7 Projete uma MT que reconheça a seguinte 
linguagem: 
\uf0a7 
\uf0a7 L = {01\ud835\udc5b101\ud835\udc5b2, \u2026 , 01\ud835\udc5b\ud835\udc58| \ud835\udc58 > 0 \ud835\udc52 \ud835\udc5b1 < \ud835\udc5b2 \u2026 <
\ud835\udc5b\ud835\udc58}. 
\uf0a7 
\uf0a7 Informalmente, nas palavras aceitas pela MT, 
cada 0 deverá ser seguido por um número 
crescente de 1\u2019s. A máquina poderá conter uma 
ou duas fitas. Descreva-a em alto-nível 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes de Máquinas de Turing 
\uf0a7 Possíveis variações 
\u2022 A fita pode extender-se para ambos os lados 
\u2022 Mais de uma fita, e.g., uma fita para escrita e 
outra para leitura 
\u2022 Mais de uma cabeça le 
\u2022 Máquinas não-determinísticas 
\u2022 ... 
52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes de Máquinas de Turing 
\uf0a7 Todas variações produzem modelos 
computacionais diferentes 
\uf0a7 O modelo original da Máquina de Turing e 
todas suas variantes possuem o mesmo poder 
de expressão \u2013 todos modelos reconhecem a 
mesma linguagem 
\uf0a7 Com isso, dizemos que MTs são robustas 
53 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Toy Example 
\uf0a7 Considere a seguinte modificação na função 
de transição: 
\u2022 : Q \u393 Q \u393 {L, R, N} 
\uf0a7 N significa nenhum movimento da cabeça le 
\uf0a7 Poderíamos reconhecer linguagens adicionais 
com esta modificação, i.e., aumentariamos o 
poder do modelo original? 
54 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Toy Example (2) 
\uf0a7 Não. Podemos converter qualquer MT do 
novo modelo em uma MT do modelo original 
\u2022 Substitua todas transições envolvendo N por duas 
transições, um com R e outra com L 
55 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing Multi-fita 
\uf0a7 MT contendo mais de uma fita (F1, F2,..., Fk) 
\uf0a7 Cada fita possui sua própria cabeça le 
\uf0a7 Inicialmente a entrada está escrita apenas em 
uma fita (convenção: F1). As demais contém 
apenas símbolos brancos 
 
 
56 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing Multi-fita 
\uf0a7 Nova função de transição: 
\u2022 : Q \u393k Q \u393k {L, R}k, onde k é o 
número de fitas 
\u2022 (qi, a1,...,ak) = (qj, b1, ..., bk, L, R, ..., L) 
\u2022 A expressão acima significa que a MT está no 
estado qi quando ela lê os símbolos a1,...,ak para 
F1,...,Fk. A MT transita então para o estado qj 
escrevendo os símbolos b1,...,bk nas fitas fazendo 
os movimentos correspondentes 
 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
\uf0a7 Projete uma MT multi-fita que aceite palavras 
que são palíndromos 
58 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais 
\uf0a7 Teorema 3.1: Toda MT multi-fita possui uma 
MT equivalente com apenas uma fita 
\uf0a7 Prova (por construção): mostrar como 
converter uma MT multi-fita M em uma MT 
com apenas uma fita S 
\u2022 Idéia: mostrar como simular M com S 
59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais (2) 
\uf0a7 Armazene a informação de múltiplas fitas em 
uma única fita 
\uf0a7 Use um símbolo especial (e.g., #) para 
delimitar o conteúdo de cada fita 
\uf0a7 Acompanhe a posição da cabeça le de cada 
fita colocando uma marca especial sobre cada 
sobre o qual a cabeça está posicionada 
60 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
\u2fd 
Equivalência entre MTs Multi-fita e 
MT Convencionais (2) 
61 
M 
a b c \u2fd ... 
0 1 0 \u2fd ... 
a b \u2fd ... 
S # a b c # 1 0 0 # a b ... 
Símbolos com um ponto em 
cima podem ser interpretados 
como novos símbolos no 
alfabeto da fita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais (3) 
\uf0a7 Dado uma entrada p=p1,\u2026,pn, faça: 
1. Primeiramente, S formata a fita para representar 
todas k-fitas de M. O fomato é 
#p1p2\u2026pn#\u2fd#\u2fd#...# 
2. Um único movimento de M é simulado em dois 
passos sobre a fita. O primeiro passo determina os 
símbolos sobre as cabeças le virtuais. O segundo 
passo atualiza as fitas de acordo com o resultado da 
função de transição 
62 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
3. Se em algum ponto, S encontra algum # após algum 
movimento para a direita, isto significa que M 
movimentou sua cabeça para um ponto com 
símbolo branco da fita correspondente. Neste caso, 
todo o conteúdo restante da fita é movido para a 
direita em uma casa (mais especificamente, até o 
último #) e o símbolo branco é na posição da 
cabeça virtual 
 
63 
Equivalência entre MTs Multi-fita e 
MT Convencionais (3) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Reconhecíveis 
e MT Multi-fita 
\uf0a7 Corolário 3.1 : Uma linguagem é Turing 
reconhecível sse alguma MT Multi-fita a 
reconhece 
 
64 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquina de Turing 
Não-Determinística (MTND) 
\uf0a7 A qualquer ponto, a computação da máquina 
pode seguir caminhos diferentes 
\uf0a7 Função de transição: 
: 2Q \u393 {Q \u393 {L, R}} 
\uf0a7 A MTND aceita a entrada quando qualquer 
uma de suas ramificações de computação 
chega a uma configuração de aceitação 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência Entre MTs e MTNDs 
\uf0a7 Teorema 3.2: Toda MTND possui uma MT 
equivalente 
\uf0a7 Prova (Intuição): Demonstrar que nós 
podemos simular qualquer MTND N com uma 
MT D 
\u2022 D tenta todos os possíveis branches da 
computação não-determinística de N. Se D chega 
até uma configuração de aceitação em algum 
destes branches, então D aceita a entrada. Caso 
contrário a simulação de D não termina. 
66 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (2) 
\uf0a7 Assim como para AFNDs, a computação naõ-
determinística de N pode ser vista como uma 
árvore de possibilidades 
\u2022 Cada ramificação da árvore é uma ramificação de não-
determinismo 
\u2022 Cada nó é uma configuração de N 
\u2022 A raiz é a configuração de início 
\uf0a7 Idéia: M realiza uma busca nesta árvore pelo 
estado de aceitação 
\u2022 Qual melhor estratégia de busca? Busca em 
profundidade (depth-first) ou busca em largura 
(breadth-first)? 
67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (3) 
\uf0a7 Usando busca em profundidade podemos 
encontrar uma ramificação infinita 
\u2022 O algoritmo de busca nunca retorna 
\uf0a7 Melhor estratégia: busca em largura 
\u2022 Visita todos os nós no mesmo nível da árvore 
68 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (4) 
\uf0a7 Considere uma MT determinística com três 
fitas (de acordo com o Teorema 3.1 esta MT é 
equivalente a uma MT com uma única fita) 
\uf0a7 Cada fita possui uma finalidade específica: 
\u2022 Fita 1: Contém a palavra de entrada e nunca é 
alterada 
\u2022 Fita 2: Mantém a cópia da fita de N em alguma 
ramificação 
\u2022 Fita 3: Mantém informação sobre a posição de D 
na árvore de possiblidades 
 
 
69 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (5) 
\uf0a7 Considere Fita 3. Cada nó na árvore pode ter no 
máximo n filhos, onde n é o tamanho do maior 
conjunto de possíveis escolhas retornado pela função 
de transição de N 
\uf0a7 Atribua um endereço