Aula 11 - Máquinas de turing

Prévia do material em texto

Informática Teórica 
Engenharia da Computação
MÁQUINAS DE TURING
Máquinas de Turing - História
 (1900) – David Hilbert
– Apresentou 23 problemas que deveriam ser 
resolvidos no próximo século.
– 10º problema: 
 Encontrar um processo com o qual é possível 
determinar se um polinômio tem uma raiz inteira, 
usando um número finito de operações;
 Algoritmo;
Máquinas de Turing - História
 Início do século XX: pesquisas com o objetivo de 
definir
– modelo computacional suficientemente genérico
– capaz de implementar qualquer função computável
Máquinas de Turing - História
 (1936) – Alan Turing
– Propôs um modelo matemático do processo de 
computação;
– Máquina de Turing;
– aceito como uma formalização de:
 procedimento efetivo
 algoritmo ou
 função computável
Máquinas de Turing - História
 (1936) – Alonzo Church
– Apresentou sua hipótese que qualquer função
computável pode ser processada por uma máquina de
Turing.
– existe um procedimento expresso na forma de uma 
máquina de Turing capaz de processar qualquer 
função computável;
– como a noção intuitiva de procedimentos não é 
matematicamente precisa
 impossível demonstrar formalmente se a máquina de 
Turing é, de fato, o mais genérico dispositivo de 
computação;
 mostrado: todos os demais modelos propostos possuem, 
no máximo, a mesma capacidade computacional;
Máquinas de Turing
 Resumidamente, uma Máquina de Turing
– Semelhante a um autômato;
– Mas com uma memória ilimitada e irrestrita;
– Utiliza uma fita que não possui tamanho máximo;
– Pode ser usada simultaneamente como dispositivo de 
entrada, de saída e de memória de trabalho;
Hierarquia de Chomsky
Linguagens Recursivamente Enumeráveis(0)
Linguagens Sensíveis ao Contexto (1)
Linguagens Livre de Contexto (2) 
Linguagens Regulares (3)
Hierarquia de Chomsky
Hierarquia Linguagem Gramática Reconhecedor
Tipo-0 [0] Linguagens
Recursivamente 
Enumeráveis 
Gramáticas
Irrestritas
Máquina de Turing
Tipo-1 [1] Linguagens Sensíveis
ao Contexto
Gramáticas 
Sensíveis ao 
Contexto
Máquina de Turing
Com fita limitada
Tipo-2 [2] Linguagens Livres de 
Contexto
Gramáticas 
Livres de 
Contexto
Autômato com Pilha
Tipo-3 [3] Linguagens Regulares Gramáticas 
Regulares
Autômato Finito
Linguagens Recursivamente Enumeráveis ou Tipo 0
 aceitas por uma máquina de Turing
 segundo a Hipótese de Church, a Classe das Linguagens 
Recursivamente Enumeráveis
– conjunto de todas as linguagens
– que podem ser reconhecidas mecanicamente 
– em um tempo finito
Linguagens Recursivamente Enumeráveis ou Tipo 0
 inclui algumas para as quais é
– impossível determinar mecanicamente
– se uma palavra não pertence à linguagem
 se L é uma destas linguagens, então
– para qualquer máquina de Turing M que aceita L
– existe pelo menos uma palavra w não pertencente a L que
– ao ser processada por M, a máquina entra em loop infinito
 ou seja
– se w pertence a L, M pára e aceita a entrada
– se w não pertence a L, M pode parar, rejeitando a palavra 
ou permanecer processando indefinidamente
Linguagens Recursivas
 subclasse da Classe das Linguagens Enumeráveis 
Recursivamente
 existe pelo menos uma máquina de Turing que para em 
qualquer entrada, aceitando ou rejeitando
Máquina de Turing
 Máquina de Turing (Alan Turing, 1936)
– mecanismo simples
– formaliza a ideia de uma pessoa que realiza cálculos
– lembra os computadores atuais
 embora proposta anos antes do primeiro computador digital
 Modelo máquina de Turing
– no mínimo, mesmo poder computacional
– de qualquer computador de propósito geral
Máquina de Turing
 Modelo muito mais preciso de um computador de propósito 
geral;
 Pode fazer tudo que um computador real pode fazer;
– Entretanto, não pode resolver alguns problemas
 Estão além dos limites teóricos da computação.
Máquina de Turing
 Usa uma fita infinita com sua memória ilimitada;
 Ela tem uma cabeça que pode ler e escrever símbolos e 
mover sobre a fita;
 Inicialmente a fita contém somente a cadeia de entrada e está 
em branco em todo o restante;
 Poder ler ou escrever informação na fita;
Máquina de Turing - Modelo
 Constituído de três partes
 Fita, usada simultaneamente como dispositivo de
– entrada, saída e memória de trabalho
 Unidade de Controle
– reflete o estado corrente da máquina
– possui uma unidade de leitura e gravação (cabeça da fita)
– acessa uma célula da fita de cada vez
– se movimenta para a esquerda ou para a direita
 Programa, Função Programa ou Função de Transição
– define: estado da máquina
– comanda: leituras, gravações e sentido de movimento (cabeça)
Máquina de Turing - Modelo
 Fita: finita à esquerda e infinita à direita
– infinita: “tão grande quanto necessário”
– dividida em células, cada uma armazenando um símbolo
 Símbolos podem
– pertencer ao alfabeto de entrada
– pertencer ao alfabeto auxiliar
– ser "branco"
Máquina de Turing - Modelo
Máquina de Turing
 Unidade de controle
– número finito e predefinido de estados
– cabeça da fita
 lê um símbolo de cada vez e grava um novo símbolo
 move uma célula para a direita ou para a esquerda
– símbolo gravado e o sentido do movimento
 definidos pelo programa
Máquina de Turing - Exemplo
 Seja B = {w#w | w  {0,1}*}. Queremos que M1 aceite se sua 
entrada é um membro de B e rejeite caso contrário.
– Ela realiza múltiplas varridas sobre a cadeia de entrada com a 
cabeça de leitura-escrita. 
– A cada passagem ela emparelha um dos caracteres em cada lado 
do símbolo #. 
– Para manter registro de quais símbolos já foram verificados, M1
deixa uma marca sobre cada símbolo à medida que ele é 
examinado. 
– Se ela marca todos os símbolos, isso significa que tudo emparelhou 
de forma bem sucedida, e M1 vai para um estado de aceitação;
– Se ela descobre uma sobra, ela entra em um estado de rejeição.
Máquina de Turing - Exemplo
 Em resumo, o algoritmo de M1 é o seguinte:
– 1. Faça um varredura na entrada para assegurar que ela contém 
uma única ocorrência do símbolo #. Se não, rejeite.
– 2. Faça um zigue-zague na fita para fazer corresponder posições
nos dois lados do símbolo # para verificar se essas posições contém 
o mesmo símbolo. Se elas não contêm, rejeite. Marque os símbolos 
à medida que eles são verificados para manter registro de quais 
símbolos têm correspondência.
– 3. Quando todos os símbolos à esquerda do # foram marcados, 
verifique se existe algum símbolo remanescente à direita do #. Se 
quaisquer símbolos restam, rejeite; caso contrário, aceite.
Máquina de Turing - Exemplo
Máquina de Turing – Definição Formal
 M = (Q, Σ, Γ, δ, q0,qa, qr)
– Q - conjunto de estados possíveis da máquina (finito)
– Σ - alfabeto (de símbolos) de entrada
 Não contém o símbolo especial Branco (β)
– Γ - alfabeto da fita
 Onde β ϵ Γ e Σ C Γ
– δ - (função) programa ou função de transição 
 δ: Q × Γ → Q × Γ × { E, D }
 transição da máquina: δ(p, x) = (q, y, E)
– q0 - estado inicial
– qa – estado de aceitação
– qr – estado de rejeição
Máquina de Turing – Definição Formal
 Função de Transição
– É o coração da definição de uma MT;
– Ela diz como a máquina vai de um estado para outro;
 δ(p, x) = (q, y, E)
– δ(p, x) considera
 estado corrente
 símbolo lido da fita
– (q, y, E) determina
 novo estado
 símbolo a ser gravado
 sentido de movimento da cabeça (E e D)
Máquina de Turing – Definição Formal
 Função de Transição
– suponha a transição δ(p, x) = (q, y, m)
Máquina de Turing – Exemplo Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | 
n ≥ 0 }
– Estratégia: a MT trocará um a por um A, e depois um b por um B, 
até todos os a’s e b’s terem sido comparados.
– Em cada passo, da esq. para dir., ela troca um a por A e vai para 
a direita, ignorando a’s e B’s até encontrar b. Troca esse b por B
e se move para a esquerda, ignorando B’s e a’s, até encontrar um 
A. Procura um a a direita e troca por A, repetindo o processo.
– Se a entrada não estiver em 𝒂𝒏𝒃𝒏 eventualmente a MT não vai 
ter um movimento previsto e vai parar sem aceitar.
– Se, por outro lado, na busca por mais um a, ela só encontrar A’s
e B’s, então ela descobre que deve aceitar a entrada.
Máquina de Turing – Exemplo
 Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | 
n ≥ 0 }
– M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B,β}, δ, q0, {qa})
Estado a b A B β
q0 (q1,A,D) (q3,B,D) (qa, β, D)
q1 (q1,a,D) (q2,B,E) (q1,B,D)
q2 (q2,a,E) (qo,A,D) (q2,B,E)
q3 (q3,B,D) (qa, β,D)
qa
Máquina de Turing – Exemplo
 Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | 
n ≥ 0 }
– M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa})
(B, B, D)
(β, β, D)
q0
(a, A, D)
q1
(a, a, D)
(B, B, D)
q2
(b, B, E)
(a, a, E) 
(B, B, E)
(A, A, D)
q3
(B, B, D)
qa
(β, β, D)
Máquina de Turing – Exemplo
B  D
ᶸ  D
q0
a A , D
q1
a,B  D
q2
b  B,E
a,B  E
A  D
q3
B  D
qa
ᶸ  D
 Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | 
n ≥ 0 }
– M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa})
Máquina de Turing – Exemplo
 Descreva uma MT que reconheça a linguagem L = { 𝒂𝒏𝒃𝒏 | 
n ≥ 0 }
– M = ({q0,q1,q2,q3,qa}, {a,b}, {a,b,A,B, β}, δ, q0, {qa})
(β, β, D)
(a, A, D)
(a, a, D)
(B, B, D)
(b, B, E)
(a, a, E) 
(B, B, E)
(A, A, D)
(B, B, D)
a  A , D
a,B  E
b  B,E
a,B  D
A  D
B  D
β  D
Máquina de Turing – Configuração
 Quando uma MT computa, mudanças ocorrem:
– No estado atual;
– No conteúdo da fita;
– E na localização da cabeça;
 A combinação dessas três informações é chamada 
configuração de uma MT.
– Para um estado q e duas cadeias u e v sobre o alfabeto da fita Γ,
– Escrevemos uqv para a configuração onde 
 o estado atual é q, 
 o conteúdo da fita é uv, 
 e a localização da cabeça é o primeiro símbolo de v.
Máquina de Turing – Configuração
 Configuração inicial de uma MT M – q0w
– Sobre a entrada w
 Configuração de aceitação -> qaceita
 Configuração de rejeição -> qrejeita
 Uma MT aceita a entrada w, se uma sequência de configurações 𝑪𝟏, 
𝑪𝟐, ..., 𝑪𝒌 existe, onde:
1. 𝑪𝟏 é a configuração inicial de M sobre a entrada w
2. Cada 𝑪𝒊 produz 𝑪𝒊+𝟏, e;
3. 𝑪𝒌 é uma configuração de aceitação
Máquina de Turing – Configuração
 Exemplo: configuração 1011q701111
 1011q701111
Exemplo
 Uma MT para aceitar {anbn | n  0}
a ᶸbba ᶸ ...
B  D
ᶸ  D
q0
a A , D
q1
a,B  D
q2
b  B,E
a,B  E
A  D
q3
B  D
qa
ᶸ  D
qoaabb
Aq1abb
Aaq1bb
Aq2aBb
q2AaBb
Aq0aBb
AAq1Bb
AABq1b
Aq2ABB
AAq2BB
AAq0BB
AABq3B
AABBq3
AABBqa
Exemplo
 Uma MT para aceitar {anbn | n  0}
a ᶸbba ᶸ ...
Máquina de Turing – Definição
 Definição: Chame uma linguagem Turing-reconhecível ou 
Recursivamente Enumerável se alguma máquina de Turing 
a reconhece.
 Quando iniciamos uma MT sobre uma entrada, três resultados 
são possíveis. A máquina pode 
– Aceitar;
– Rejeitar;
– ou entrar em loop.
 Uma MT pode falhar em aceitar uma cadeia entrando no estado 
qrejeita e rejeitando, ou entrando em loop.
 Distinguir uma MT que está em loop de uma que está levando um 
tempo longo é difícil.
Máquina de Turing – Definição
 Por essa razão preferimos MT’s que parem sobre todas as 
entradas;
– Tais MT’s nunca entram em loop
 Essas máquinas são chamadas decisores, pois sempre 
tomam uma decisão de aceitar ou rejeitar.
– Um decisor que reconhece uma linguagem é dito decidir aquela 
linguagem.
 Definição: Chame uma linguagem Turing-decidível ou 
simplesmente decidível se alguma máquina de Turing a 
decide;
– Também chamada de linguagem recursiva;
Máquina de Turing – Exemplo
 Uma MT que reconheça a linguagem L = {02
𝑛
| 𝑛 ≥ 0}
 Estágios para a resolução:
– 0. Marque o primeiro zero com Y;
– 1. Atravesse da esquerda para direita marcando um zero 
sim outro não com um X;
– 2. Se no estágio 1. a fita contém 1 único 0 aceite. Se 
contiver mais do que 1 zero e o número for impar, rejeite.
– 3. Retorne ao marcador Y;
– 4. Vá para o estágio 1;
Máquina de Turing – Exemplo
 M2 = (Q, Σ, Γ, δ, q1,qaceita, qrejeita)
 Q = {q1, q2 , q3 , q4 , q5 , qaceita, qrejeita},
 Σ = {0}, e
 Γ = {0, X, Y, }
П
q2
qaceitaqrejeita
q3
0  X , D
q5
0  D
q1
0  Y , D X  D
q4 X  D
Máquina de Turing – Exercício
 Uma MT que reconheça a linguagem L = {02
𝑛
| 𝑛 ≥ 0}
0  X, Dᶸ  D
0  E
X  E
X  D
ᶸ  D
X  D
ᶸ  D
Máquina de Turing – Exemplo
 Uma MT que reconheça a linguagem L = {02
𝑛
| 𝑛 ≥ 0}
 Exercício: mostre as configurações da MT acima para a 
entrada 0000
 Exercício: mostre as configurações da MT acima para a 
entrada 00000
Máquinas de Turing
 Descrevemos uma MT M1 bem simples que faz a 
concatenação de dois inteiros positivos, 
representados por * e separados por um branco na 
fita. 
* ᶸ***ᶸ**** ᶸ ...
Exemplo
 q0 Ler os * movendo a fita para a direita, ao 
encontrar o branco escrever *, move para a direita, 
vai para estado q1
 q1 Ler os * ,move para a direita, continuar no estado 1 
até encontrar um branco (fim da fita), mover para 
esquerda, ir para estado 2
 q2 Apagar * e ir para um estado de aceitação.
* ᶸ***ᶸ**** ᶸ ...
q0
*  D
ᶸ * , D
q1
*  D
ᶸ  E
q2
*  ᶸ , D
qa
 Vídeo: 
https://www.youtube.com/watch?v=E3keLeMwfHY