1/14
Máquinas de Turing
e Suas Variações
e Suas Variações
Seminário 3. Cicero Augusto Simões Costa, Bernardo Ferreira Dias, Artem Lavrinovich, Anastasiia Sipina, Italo Tadeu Pereira Almeida
MT com Cabeçote Imóvel
MT com Múltiplas Trilhas
MT com Múltiplas Fitas
MT Não Determinística
| História e Motivação
Por que precisamos de Máquinas de Turing?
|
A Ideia de Máquina Universal
Conceito Revolucionário
Conceito Revolucionário
As Máquinas de Turing estabeleceram os limites teóricos da computação. Elas definem o que é computável e o que não é, independente de avanços tecnológicos. Problemas não computáveis por uma MT não podem ser resolvidos por nenhum computador.
- Uma única máquina que pode simular qualquer outra máquina
- Equivalente aos computadores modernos de propósito geral
- Fundamento teórico da programação
Máquina de Turing Padrão - Componentes
Fita
ilimitada à direita, dividida em células
Cabeçote
lê e escreve símbolos na fita
Estados finitos
controle interno da máquina
Função de transição
determina próximo estado
Movimentos
L (esquerda), R (direita)
Definição Formal da MT
E
conjunto finito de estados
Σ
alfabeto de entrada
Γ
alfabeto da fita (Σ ⊂ Γ)
<
símbolo inicial
(marca início da fita)
(marca início da fita)
U
símbolo branco
δ
E × Γ → E × Γ × {L, R}
i
estado inicial (i ∈ E)
F
conjunto de estados finais
(F ⊆ E)
(F ⊆ E)
Configuração Instantânea
- Configuração InicialPara uma entrada w = w₁w₂...wₙ, a configuração inicial é:
[i, <w₁w₂...wₙ] - AceitaçãoUma palavra w é aceita se existe uma sequência de configurações:
[i, <w] ⊢ C₁ ⊢ C₂ ⊢ ... ⊢ [f, αaβ]
onde f ∈ F (estado final)
Função de Transição
- Exemplo de Transição
δ(q₀, a) = (q₁, b, R)Interpretação: Se a máquina está no estado q₀ e lê o símbolo 'a',
então ela escreve 'b', muda para o estado q₁ e move o cabeçote para a direita. - ObservaçõesObservações
- A função é parcial: pode não estar definida para alguns pares (e, a)
- Quando δ não está definida, a máquina para
- Aceita se parar em um estado final
MT com Cabeçote Imóvel
Definição:
Adiciona movimento I (Imóvel) à função de transição
δ: E × Γ → E × Γ × {L, R, I}
Cabeçote pode permanecer na mesma posição
Útil para operações que requerem múltiplas leituras/escritas na mesma célula
Teorema
Uma MT com cabeçote imóvel pode ser simulada por uma MT padrão.
L(MT) = L(MT com cabeçote imóvel)
Adiciona movimento I (Imóvel) à função de transição
δ: E × Γ → E × Γ × {L, R, I}
Cabeçote pode permanecer na mesma posição
Útil para operações que requerem múltiplas leituras/escritas na mesma célula
Teorema
Uma MT com cabeçote imóvel pode ser simulada por uma MT padrão.
L(MT) = L(MT com cabeçote imóvel)
- Exemplo de Usoδ(q₀, a) = (q₁, b, I)
δ(q₁, b) = (q₂, c, R)
A máquina pode modificar uma célula múltiplas vezes antes de avançar. - Estratégia de Simulação
- Cada movimento I é simulado por: R seguido de L
δ(q, a) = (q_aux, b, R)
δ(q_aux, x) = (q', x, L) para todo símbolo x- Resultado: mesmo poder computacional
- Prova: construção explícita da simulação
Exemplo usando duas técnicas para simular o cabeçote imóvel
-
Simulação com
movimentação à esquerda -
Simulação com
movimentação à direita
- Visualização (k=2)Trilha 1: | a | b | c | d |
Trilha 2: | 0 | 1 | 0 | 1 |
___________________________
Célula: |(a,0)|(b,1)|(c,0)|(d,1)|
Cada célula armazena um par ordenado de símbolos - Estratégia de SimulaçãoAlfabeto expandido: Γ' = Γ₁ × Γ₂ × ... × Γₖ
Cada símbolo de Γ' representa uma k-upla
Uma célula da MT padrão = uma célula da MT com k trilhas
Função de transição adaptada para trabalhar com k-uplas
Exemplo
Se Γ₁ = {a, b} e Γ₂ = {0, 1}, então:
Γ' = {(a,0), (a,1), (b,0), (b,1)}
MT com Múltiplas Trilhas
Conceito:
Teorema:
Uma MT com k trilhas pode ser simulada por uma MT padrão (1 trilha).
- Cada célula da fita contém uma k-upla de símbolos
- k trilhas paralelas simultâneas
- Um único cabeçote lê/escreve em todas as trilhas ao mesmo tempo
- Útil para armazenar informações auxiliares
Teorema:
Uma MT com k trilhas pode ser simulada por uma MT padrão (1 trilha).
MT com Múltiplas Fitas
Definição:
Função de Transição
δ: E × Γᵏ → E × Γᵏ × {L, R}ᵏ
Lê k símbolos (um de cada fita) e
escreve k símbolos com k movimentos
Estratégia com 3 Fitas
Uma MT com k fitas pode ser simulada por uma MT de 1 fita.
- k fitas independentes, cada uma com seu próprio cabeçote
- Todos os cabeçotes movem-se simultaneamente (mas podem em direções diferentes)
- A entrada está inicialmente na fita 1
- Outras fitas começam em branco
Função de Transição
δ: E × Γᵏ → E × Γᵏ × {L, R}ᵏ
Lê k símbolos (um de cada fita) e
escreve k símbolos com k movimentos
Estratégia com 3 Fitas
- Fita 1: contém a entrada original
- Fita 2: copia primeira metade (w)
- Fita 3: copia segunda metade (wᴿ) em reverso
- Compara fita 2 com fita 3 (devem ser iguais)
- Compara fita 2 com a terceira parte da fita 1
Uma MT com k fitas pode ser simulada por uma MT de 1 fita.
- Exemplo: Reconhecendo {wwᴿw}Linguagem
L = {wwᴿw | w ∈ {a,b}*}
Onde wᴿ é w reverso
Exemplos: abaaba, ε, abbaabba - Estratégia de SimulaçãoUsar 2k trilhas na fita única
k trilhas para conteúdo das k fitas
k trilhas para marcar posição dos k cabeçotes
Usar delimitadores # para separar conteúdos
Simular cada passo da MT k-fitas com múltiplas varreduras - Custo da SimulaçãoSe a MT k-fitas executa em tempo T(n), a simulação executa em O(T²(n)). Importante para teoria da complexidade!
- Modelo Mental
- Cada escolha não-determinística cria um ramo
- Forma uma árvore de configurações possíveis
- Cada caminho da raiz a uma folha = uma computação possível
- Alguns ramos param, outros continuam indefinidamente
- Critério de Aceitação
- Uma palavra w é aceita se existe pelo menos um ramo que leva a um estado final.
- Não importa se outros ramos rejeitam ou não param. Basta que exista um caminho de aceitação!
- Estratégia: Busca em Largura
- Usar 3 fitas: entrada, simulação, endereços
- Enumerar todas as computações possíveis sistematicamente
- Explorar árvore nível por nível (busca em largura)
- Se existe aceitação, será encontrada em tempo finito
- Importante: NÃO usar busca em profundidade (pode não terminar)
MT Não Determinística
Conceito:
δ(q₀, a) = {(q₁, b, R), (q₂, c, L)}
A máquina pode escolher ir para q₁ OU q₂
Duas computações paralelas possíveis
Teorema:
Toda MT não-determinística pode ser simulada por uma MT determinística.
Implicação
- A função de transição pode ter múltiplas escolhas
- δ: E × Γ → P(E × Γ × {L, R})
- P denota conjunto das partes (conjunto de todos os subconjuntos)
- A máquina "escolhe" uma transição não-deterministicamente
δ(q₀, a) = {(q₁, b, R), (q₂, c, L)}
A máquina pode escolher ir para q₁ OU q₂
Duas computações paralelas possíveis
Teorema:
Toda MT não-determinística pode ser simulada por uma MT determinística.
Implicação
- MT determinísticas e não-determinísticas reconhecem as mesmas linguagens!
- Mas a diferença de tempo pode ser exponencial (P vs NP).
Equivalência de Todas as Variações de MT
Teorema: Todas as variações de MT reconhecem exatamente as Linguagens Recursivamente Enumeráveis (LRE)
MT Padrão, Cabeçote Imóvel, Múltiplas Trilhas, Múltiplas Fitas e Não Determinística são computacionalmente equivalentes
Todas podem simular umas às outras
Mesma classe de linguagens reconhecidas
MT Padrão, Cabeçote Imóvel, Múltiplas Trilhas, Múltiplas Fitas e Não Determinística são computacionalmente equivalentes
Todas podem simular umas às outras
Mesma classe de linguagens reconhecidas
- Cabeçote
Imóvel - Múltiplas
Trilhas - Múltiplas
Fitas - Não
Determinística
Alan Turing
"Nem tudo que é verdadeiro pode ser provado, nem tudo que é descritível pode ser computado."