Universidade Federal da Paraíba
Programa de Pós-Graduação em Informática
Teoria da Computação – 2013.1
Máquinas de Turing
SIPSER – Capítulo 3: A tese de Church-Turing
Ana Paula Nunes Guimarães
Glauco de Sousa e Silva
Sarah Soares de Oliveira
Professor:Andrei Formiga
Até agora
Autômatos finitos são bons modelos para
dispositivos que têm uma quantidade pequena
de memória
 Autômatos com pilha são bons modelos para
dispositivos que possuem memória ilimitada,
desde que
seja utilizada de apenas uma
maneira:
◦ LIFO
 Agora veremos um modelo mais poderoso:
◦ Máquinas de Turing (MTs)

2
Máquinas de Turing
Proposta por Alan Turing em 1936
 Semelhante a um autômato finito
◦ Mas com memória ilimitada e irrestrita
 É um modelo de um computador de propósito
geral

3
Máquinas de Turing
4
Máquinas de Turing
Um detalhe importante é a aceitação, ou
rejeição da entrada
 Diferente dos autômatos, ela possui um estado
de aceitação, e outro de rejeição
◦ Ambos necessariamente finais
 Quando um destes estados é alcançado, a
computação termina imediatamente

5
Máquinas de Turing

Para entender o procedimento executado por
uma máquina de Turing, vamos considerar a
seguinte linguagem:
◦ L1 = { w#w | w ∈ {0,1}* }
Exemplos de palavras da linguagem L1:
w1=010#010
w2=0011#0011
6
Máquinas de Turing

Algoritmo para reconhecer L = {w#w | w ∈{0,1}*}
1. Faça um zigue-zague ao longo da fita checando
posições correspondentes de ambos os lados
do símbolo # para verificar se elas contêm o
mesmo símbolo. Se a fita não contêm, ou se
nenhum # foi encontrado, então rejeite;
2. À medida que os símbolos vão sendo
verificados, marque-os;
3. Quando todos os símbolos a esquerda de #
forem marcados, verifique se existe algum
símbolo não marcado a direita. Se existir,
rejeite. Se não existir, aceite a entrada.
7
Entrada: 011000#011000
0 1 1 0 0 0 # 0 1 1 0 0 0 □ ...
x 1 1 0 0 0 # 0 1 1 0 0 0 □ ...
x11000#x11000 □
...
x11000#x11000 □
xx1000#x11000 □
...
x x x x x x # x x x x x x x □ ...
aceita
8
Definição formal de uma Máquina de Turing


Uma MT é definida como uma 7-upla:
M = (Q, Σ, Γ, δ, q0, qaceita,qrejeita)
Onde:
◦ Q é o conjunto de estados,
◦ Σ é o alfabeto de entrada sem o símbolo em
branco (□),
◦ Γ é o alfabeto da fita, onde □ ϵ Γ e Σ ⊆ Γ,
◦ δ : Q x Γ→ Q x Γ x {L, R} é a função de transição,
◦ q0 ϵ Q é o estado inicial,
◦ qaceita ϵ Q é o estado de aceitação e,
◦ qrejeita ϵ Q é o estado de rejeição (qaceita ≠ qrejeita ).
9
Iniciando uma Máquina de Turing

Entrada w = ABCD
Unidade de
controle
A
B
C
D
□
10
Exemplo de função de transição

δ(q0, A) = (q1,X,R)
q0
A
B
C
D
□
11
Exemplo de função de transição

δ(q0, A) = (q1,X,R)
q1
X
B
C
D
□
12
Configurações da Máquina de Turing
Configurações de uma MT são mudanças que
ocorrem no estado atual, no conteúdo atual e
na posição atual da cabeça.
 Exemplo: ABqCD

q
A
B
C
D
□
13
Configurações da Máquina de Turing

Casos especiais:
◦
◦
◦
◦
◦

Começo da cadeia com movimento para a esquerda
Fim da cadeia com movimento para a direita
Configuração inicial (q0w)
Configuração de aceitação (qaceita)
Configuração de rejeição (qrejeita)
Uma MT aceita uma aceita a entrada w se uma
sequência de configurações C1, C2, ..., Ck existe.
14
Linguagens e Máquinas de Turing

Linguagem da MT: coleção de cadeias que são
aceitas

Linguagem Turing-reconhecível

Linguagem Turing-decidível
15
Exemplos de Máquinas de Turing

L = {anbn | n ≥1}
16
Exemplos de Máquinas de Turing

L = {anbn | n ≥1}

O estado q0 ao encontrar “a” escreve “x” (ou seja,
marca “a”), muda de estado (q1) e vai para a direita.
O estado q1 é responsável por encontrar um “b” e
marcá-lo com “y”.
A partir daí, outro estado (q2) entra em ação. Ele
volta na fita até encontrar “x” (o último “a”
marcado).
Quando q2 encontra o “x” devolve o controle para
o estado q0, que recomeça o processamento.



17
Exemplos de Máquinas de Turing



Quando q0 encontra o “y”, significa que já
terminou de marcar os símbolos “a”. Então, se
não houverem mais “b” para serem marcados, a
cadeia está correta.
Para isso é usado o estado q3, para percorrer o
restante da cadeia. Se encontrar só “y” e o □,
então a cadeia está correta.
Se encontrar algum “b”, a MT para (já que não
existe uma transição δ(q3, b) e a cadeia não é
aceita).
18
Exemplos de Máquinas de Turing

L = {anbn | n ≥1}
19
Exemplos de Máquinas de Turing

L = {anbn | n ≥1} – cadeia: w = aabb
20
Exemplos de Máquinas de Turing

L = {w#w | w ϵ {0,1}*}
21
Variantes de Máquinas de Turing
Variantes
◦ Máquinas de Turing Multifita
◦ Máquinas de Turing Não-Determinísticas
◦ Enumeradores
 Poder computacional
◦ Reconhecem a mesma classe de linguagens
 Robustez

22
Variantes de Máquinas de Turing
E se permitíssemos que o cabeçote de uma MT
ficasse parado?
1. Função de transição de uma MT padrão

2.
Função de transição de uma MT estendida

Essa característica pode permitir que essas MT
reconheçam linguagens adicionais, incrementando
assim o poder desse modelo?
Equivalência entre modelos

23
Máquinas de Turing Multifita


Máquinas de Turing Multifita
A função de transição é modificada para permitir
ler, escrever e mover as cabeças em todas as fitas
simultaneamente
1. Função de transição de uma MT padrão
2. Função de transição de uma MT estendida
24
Máquinas de Turing Multifita

Poder computacional
25
Máquinas de Turing Multifita
Teorema: toda MT mulifita tem uma MT de uma
única fita que lhe é equivalente
 Prova: Devemos mostrar como converter uma
MT multifita M em uma equivalente S, com
apenas uma fita

26
Máquinas de Turing Multifita

Cabeçotes e fitas virtuais
27
Máquinas de Turing Não-Determinísticas

Em qualquer ponto, a máquina pode proceder de
acordo com várias possibilidades
1.
Função de transição de uma MT padrão
2.
Função de transição de uma MT estendida


A computação é uma árvore
◦ Os
nós
correspondem
possibilidades
às
diferentes
Poder computacional
28
Máquinas de Turing Não-Determinísticas




Teorema:Toda MTND tem uma MTD que lhe é
equivalente
Idéia da prova: Podemos simular qualquer MTND
M, através de uma MT determinística S
Vemos a computação de M sobre uma entrada w
como uma árvore de possibilidades
Cada nó da árvore é uma
configuração de M
29
Máquinas de Turing Não-Determinísticas
A raiz é a configuração inicial
◦ Cada nó tem no máximo b filhos
 Buscar um estado de aceitação
 Não fazer busca em profundidade, fazer busca
em largura!
◦

30
Simulação da MTND

Prova:
◦ A MT simuladora S posui três fitas:
31
Máquinas de Turing Não-Determinísticas

Uma linguagem é Turing-reconhecível se, e
somente se alguma MTND a reconhece
Chamamos uma MTND de decisor se todos os
nós param sobre todas as entradas
 Uma linguagem é decidível se e somente se
alguma MTND a decide

32
Enumeradores
Um enumerador pode ser visto como uma MT
com uma impressora anexa
 A MT pode usar essa impressora como um
dispositivo de saída para imprimir cadeias

33
Equivalência com outros modelos
Existem vários modelos de computação de
propósito geral
 Todos
os
modelos
compartilham
a
característica essencial de máquinas de Turing
◦ Acesso irrestrito a memória ilimitada
 Linguagens de programação
◦ Descrevem exatamente a mesma classe de
algoritmos

34
Tese de Church-Turing
"A capacidade de computação representada
pela Máquina de Turing é o limite máximo que
pode ser atingido por qualquer dispositivo de
computação"
 Supondo verdadeira a hipótese de Church

◦ Função computável: é possível construir uma
Máquina de Turing (ou formalismo equivalente) que
compute a função
◦ Função Não-Computável: não existe Máquina de
Turing (ou formalismo equivalente) que compute a
função
35
Terminologia para descrever MT’s
A entrada da MT é uma cadeia
 E se quisermos fornecer como entrada um
objeto?
◦ Representar o objeto como uma cadeia
◦ Grafos, polinômios, gramáticas, autômatos...
 Notação <O>

36
Universidade Federal da Paraíba
Programa de Pós-Graduação em Informática
Teoria da Computação – 2013.1
Máquinas de Turing
SIPSER – Capítulo 3: A tese de Church-Turing
Ana Paula Nunes Guimarães
Glauco de Sousa e Silva
Sarah Soares de Oliveira
Professor:Andrei Formiga