Máquinas de Turing

Prévia do material em texto

Computabilidade e
Complexidade
(COM10014)
Profa. Juliana Pinheiro Campos Pirovani
E-mail: jupcampos@gmail.com
Sistemas de Informação
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Modelo de computação poderoso concebido pelo 
matemático britânico Alan Turing em 1936. 
Usa uma fita infinita como sua memória ilimitada. 
Essa fita é dividida em células. 
Tem um cabeçote que pode ler/ escrever 
símbolos e mover-se sobre a fita. 
Inicialmente a fita contém apenas a cadeia de 
entrada e está em branco em todo o restante. 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
As MT podem tanto ler quanto escrever sobre a 
fita.
O cabeçote pode se movimentar tanto para a 
esquerda quanto para a direita.
Os estados de aceitação e rejeição fazem efeito 
imediatamente (entrou em um estado de 
aceitação ou rejeição, a entrada nem continua a 
ser lida, a computação termina)
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Ex: MT M para reconhecer a linguagem L = {anbn | 
n >= 1}
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
 Definição formal: Uma MT é uma 7-upla, (Q, ∑, Γ, δ, q0, qaceita, 
qrejeita) onde:
Q é um conjunto finito de estados
∑ é o alfabeto de entrada sem o símbolo branco 
Γ é o alfabeto de fita, onde Є Γ e ∑Ϲ Γ
δ: Q x Γ -> Q x Γ x {E, D} é a função de transição. Se a máquina está 
num estado q e o cabeçote está sobre uma célula da fita com símbolo 
a e se δ(q,a) = (r, b, E), a máquina escreve o símbolo b substituindo o 
a e vai para o estado r. E indica que o cabeçote se move para a 
esquerda. 
q0 Є Q é o estado inicial. qaceita Є Q é o estado de aceitação e qrejeita Є 
Q é o estado de rejeição, onde qrejeita ≠ qaceita
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Vamos usar nessa disciplina a definição: Uma MT 
é uma 6-upla, (Q, ∑, Γ, δ, q0, F) onde F é o 
conjunto de estados finais (F C Q).
Computação em uma MT:
• É importante observar que a definição de MT não 
distingue os conceitos de programa e 
máquina. 
• É como se a δ fosse o programa da MT que 
determina o símbolo a ser gravado, o sentido do 
movimento da cabeça e o novo estado.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Computação em uma MT:
• Uma MT recebe sua entrada sobre as n células mais à 
esquerda da fita e o restante da fita está em branco. 
• A cabeça começa sobre a célula mais a esquerda da fita 
e a computação procede conforme as regras descritas 
pela função de transição. Se M em algum momento 
tenta mover seu cabeçote para a esquerda além da 
extremidade esquerda da fita, ela permanece no mesmo 
lugar. A computação continua até que ela entre em um 
estado de aceitação ou rejeição em cujo ponto ela para. 
Se nenhum desses ocorre, M continua para sempre.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Computação em uma MT:
• A medida que a MT computa, mudanças ocorrem 
no estado atual, no conteúdo atual da fita e na 
posição atual do cabeçote. 
• A computação de uma máquina de Turing é dada 
por uma seqüência de descrições instantâneas 
(configurações) 
 C1, C2, ..., Ck contendo cada uma um possível 
valor desses 3 itens.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Uma configuração é representada da seguinte 
forma: dado um estado q e duas cadeias u e v ∈ 
Γ*. 
uqv representa a configuração em que o estado 
atual é q, o conteúdo da fita é uv e a posição 
atual do cabeçote é o primeiro símbolo de v.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Exemplo: A figura abaixo representa MT com a 
configuração abcq3ac
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Suponha que tenhamos a, b e c em Γ, assim 
como u e v em Γ* e os estados qi e qj. Digamos 
que a configuração:
• uaqibv origina uqjacv se na função de transição 
δ(qi, b) = (qj, c, E); e
• uaqibv origina uacqjv se na função de transição 
δ(qi, b) = (qj, c, D);
• qibv origina qjcv se δ(qi, b) = (qj, c, E);
• uaqi é equivalente a uaqi 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
A configuração inicial da computação de uma 
MT sobre a entrada w é q0w. 
Uma MT M aceita a entrada w se uma sequencia 
de configurações C1, C2, ..., Ck existe, onde:
• C1 é a configuração inicial de M sobre a 
entrada w
• Cada Ci origina Ci+1
• Ck é uma configuração de aceitação (o estado 
da configuração é um estado final)
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Uma linguagem aceita por uma MT é dita Turing-
reconhecível ou Linguagem recursivamente 
enumerável – LRE (aceita alcançando estado 
final ou rejeita alcançando estado não final ou 
entrando em loop).
Uma linguagem é Turing-decidível ou 
linguagem recursiva - LRec, se alguma 
máquina de Turing M a decide (pára para 
qualquer entrada, nunca entra em loop):
 
lin
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Definições alternativas (variantes) de MT:
• MT com marcador de início de fita;
• MT com fita infinita nas 2 direções;
• MT em que o cabeçote não se move em uma 
leitura/gravação;
• MT multifita;
• MT não determinísticas.
O modelo original e suas variantes tem todos o 
mesmo poder computacional. 
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
MT multifita:
• possui várias fitas, cada uma tem sua própria cabeça. 
• inicialmente a entrada aparece sobre a fita 1, e as outras 
iniciam em branco. 
• A δ permite ler, escrever e mover as cabeças em 
algumas ou todas as fitas simultaneamente.
 δ: Q x Γk → Q x Γk x {E, D}k, sendo k o nº de fitas. 
 δ(qi, a1, ..., ak) = (qj, b1, ..., bk, E, D, ..., E) significa que, se 
a máquina está no estado qi e as cabeças 1 a k estão 
lendo símbolos a1 a ak, a máquina vai para o estado qj, 
escreve os símbolos b1 a bk e direciona cada cabeça para 
mover para a esquerda ou direita, ou permanecer parada.
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Toda MT multifita tem uma MT de 1 única fita equivalente.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
MT não determinística:
• Em qualquer ponto em uma computação, a 
máquina pode proceder de acordo com várias 
possibilidades. 
• A função de transição tem a forma: 
Q x Γ -> P(Q x Γ x {E, D})
• A computação é uma árvore cujos ramos 
correspondem a diferentes possibilidades para a 
máquina. Se algum ramo leva ao estado de 
aceitação, a máquina aceita sua entrada. 
 
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Toda MT não determinística tem uma MT determinística 
equivalente (tenta todos os ramos da computação não 
determinística).
D
0 0 1 0 ...
x x # 0 1 x ... 
1 2 3 3 2 3 1 2 1 ... 
Fita de entrada
Fita de simulação
Fita de 
endereço
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Terminologias para descrever MT: 
• Descrição formal: especificação das 7 partes da 
MT
• Descrição de implementação: usa a língua 
natural escrita para descrever a maneira pela qual 
a MT move sua cabeça e a forma como ela 
armazena os dados sobre a fita. 
• Descrição de alto nível: usa a língua natural 
para descrever um algoritmo, ignorando os 
detalhes de implementação.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Ex: Para L = {anbn | n >= 1}
Descrição formal:
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Descrição no nível de implementação:
M = “Sobre a cadeia de entrada w:”
1. Se w for cadeia vazia, rejeite.
2. Faça um zigue-zague ao longo da fita indo e voltando 
entre os a's e b's, marcando um de cada até que todos 
os a's tenham terminado. Se todos os b's tiverem sido 
marcados e alguns a's permanecem, rejeite. Se 
aparecer algum a após algumb, rejeite. 
3. Quando todos os a's tiverem sido marcados, verifique 
a existência de algum simbolo remanescente. Se resta 
algum símbolo, rejeite; caso contrário, aceite.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Descrição de alto nível:
M = “Sobre a entrada w”:
Verifique se existe um b para cada a em w. Se não 
existir, rejeite. 
1. Se tiver mais b's do que a's, rejeite. Caso contrário, 
aceite.
TEORIA DA COMPUTAÇÃO
Máquinas de Turing (MT)
Chegamos em um momento decisivo no estudo da teoria da 
computação. Continuamos a falar de MT, mas nosso 
verdadeiro foco a partir de agora é em algoritmos. A 
MT simplesmente serve como um modelo preciso para 
definição de algoritmo. 
TEORIA DA COMPUTAÇÃO
Referências
Sipser, M.; Introdução à Teoria da Computação. Ed. 
Thomson, 2007. ISBN: 9878522104994.
Vieira, N. J.; Introdução aos Fundamentos da 
Computação: Linguagens e Máquinas. Ed. Thomson, 
2006. ISBN: 8522105081. 
Diverio, T. A.; Menezes, P. B.. Teoria da Computação: 
Máquinas Universais e Computabilidade. Porto 
Alegre: Sagra Luzzato, 2000.
Carnielli, W. A.; Epstein, R. L.; Computabilidade, 
funções computáveis, lógica e os fundamentos da 
matemática. 2.ed. São Paulo: Editora UNESP, 2009.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25