Informática Teórica
Engenharia da Computação
Máquinas de Turing




Agora nos voltamos para um modelo muito mais
poderoso, proposto por Alan Turing em 1936,
chamado máquina de Turing.
Semelhante a um autômato finito, mas com uma
memória ilimitada e irrestrita, uma máquina de Turing
é um modelo muito mais acurado de um computador
de propósito geral.
Uma máquina de Turing pode fazer tudo que um
computador real pode fazer.
Entretanto, mesmo uma máquina de Turing n˜ão pode
resolver certos problemas.
Modelo de Máquina de Turing





Usa uma fita infinita como sua memória ilimitada.
A fita tem uma cabeça que pode ler e escrever símbolos
e mover-se sobre a fita.
Inicialmente, a fita contem apenas a cadeia de entrada e
está em branco em todo o restante.
Se a máquina precisa armazenar informação, ela pode
escrevê-la sobre a fita.
Para ler a informação que ela escreveu, a máquina pode
mover sua cabeça de volta para a posição onde a
informação foi escrita.
Modelo de Máquina de Turing



A máquina continua a computar até que ela decida
produzir uma saída.
As saídas aceite e rejeite são obtidas entrando em
estados designados de aceitação e de rejeição.
Se não entrar num estado de aceitação ou de
rejeição, ela continuará para sempre, nunca parando.
MT  AFs
1.
Uma máquina de Turing pode tanto escrever sobre a
fita quanto ler a partir dela.
2.
A cabeça de leitura escrita pode mover-se tanto para
a esquerda quanto para a direita.
3.
A fita é infinita.
4.
Os estados especiais para rejeitar e aceitar fazem
efeito imediatamente.
MT
Exemplo

Seja B = {w#w | w  f{0,1}*}. Queremos que M1 aceite
se sua entrada é um membro de B e rejeite caso
contrário.
MT
Exemplo




Faça um zigue-zague ao longo da fita para posições
correspondentes sobre qualquer dos lados do símbolo
# para verificar se elas contem o mesmo símbolo.
Se eles não contem, ou se nenhum # for encontrado,
rejeite.
Marque os símbolos a medida que eles são verificados
para manter registro de quais símbolos têm
correspondência.
Quando todos os símbolos a esquerda do # tiverem
sido marcados, verifique a existência de algum
símbolo remanescente a direita do #. Se resta algum
símbolo, rejeite, caso contrário, aceite..
MT
Definição Formal

O coração da definifição de uma máquina de Turing é
a função de transição.

: QQ{E,D}.

Quando a MT está em um certo estado q e a cabeça
está sobre uma célula da fita contendo um 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. O terceiro
componente é E ou D e indica se a cabeça move para
a esquerda ou direita após escrever.
MT
Definição Formal

1.
2.
3.
4.
5.
6.
7.
Uma máquina de Turing é uma 7-upla, (Q,,,,q0,
qaceita, qrejeita), onde Q, ,  são todos conjuntos finitos
e
Q é o conjunto de estados,
 é o alfabeto de entrada não contendo o símbolo
em branco ᶸ
 é o alfabeto da fita, onde ᶸ   e  ,
: QQ{E,D} é 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, onde qrejeita  qaceita.
MT
Computação
Inicialmente M recebe sua entrada w = w1w2 ...wn *
sobre as n células mais a esquerda da fita, e o restante
da fita está em branco (i.e., preenchido com símbolos em
branco).


A cabeça começa sobre a célula mais à esquerda da
fita.

Note que  não contem o símbolo em branco, portanto
o primeiro branco aparecendo sobre a fita marca o fim
da entrada.
MT
Computação

M se move de acordo com a função de transição.

Se M em algum momento tentar mover sua cabeça
para a esquerda além da extremidade esquerda da
fita, a cabeça permanece no mesmo lugar para aquele
movimento, muito embora a função de transição
indique E.

A computação continua até que ela entra ou no estado
de aceitação ou de rejeição em cujo ponto ela pára.
Se nenhum desses ocorre, M continua para sempre.

MT
Configuração

A medida que uma máquina de Turing computa,
mudanças ocorrem no estado atual, no conteúdo atual
da fita e a posição atual da cabeça.

Um possível valor desses três itens é denominado
configuração da máquina de Turing.
MT
Configuração

Para um estado q e duas cadeias u e v sobre o
alfabeto da fita , escrevemos uqv para a
configuração na qual o estado atual é q, o conteúdo
atual da fita é uv e a posição atual da cabeça é sobre
o primeiro símbolo de v.

A fita contem apenas brancos após o último símbolo
de v.
MT
Configuração: exemplo

1011q01111

Representa a configuração quando a fita é
101101111, o estado atual é q, e a cabeça está
atualmente sobre o segundo 0.
q
1
0
1
1
0
1
1
1
1
ᶸ
ᶸ
...
MT
Computação: definição formal


Dizemos que a configuração C1 origina a configuração
C2, se a máquina de Turing puder ir de C1 para C2 em
um único passo.
Suponha que temos a, b e c em , u e v em * e os
estados qi e qj .

ua qi bv origina u qj acv se:

(qi,b) = (qj,c,E).

Isso cobre o caso em que a máquina de Turing move
para a esquerda.
MT
Computação: definição formal

Para um movimento para a direita, digamos que

ua qi bv origina uac qj v se:

(qi,b) = (qj,c,D).
MT
Computação: definição formal






Casos especiais ocorrem quando a cabeça estiver em
uma das extremidades da configuração.
Para a extremidade esquerda:
qi bv origina qj cv
Se a transição envolver um movimento para a
esquerda (porque cuidamos para que a máquina não
passe da extremidade esquerda da fita),
qi bv origina c qj v
para a transição que envolve um movimento para a
direita.
MT
Computação: definição formal

Para a extremidade direita:

ua qi é equivalente a ua qi ᶸ

porque assumimos que brancos vêm após a parte da
fita representada na configuração.
MT
Computação: definição formal

A configuração inicial de M sobre a entrada w é

qo w

A máquina está no estado inicial q0 com sua cabeça na
posição mais à esquerda sobre a fita.
MT
Computação: definição formal

Em uma configuração de aceitação, o estado da
configuração é qaceita.

Em uma configuração de rejeição, o estado da
configuração é qrejeita.

Configurações de aceitação e de rejeição são
configurações de parada e portanto não originam
configurações adicionais.
MT
Computação: definição formal

Uma MT M aceita a entrada w se uma sequência de
configurações C1, C2, ..., Ck existe, onde
1.
C1 é a configuração inicial de M sobre a entrada w,
cada Ci origina Ci+1 e
Ck é uma configuração de aceitação.
2.
3.

A coleção de cadeias que M aceita é a linguagem de
M, ou a linguagem reconhecida por M, denotada
L(M).
MT
Linguagem Recursivamente Enumerável

Chame uma linguagem de Turing-reconhecível (ou
recursivamente enumerável) se alguma máquina de
Turing a reconhece.
MT
Decisores

Quando iniciamos uma MT sobre uma entrada, três
resultados são possíveis. A MT pode aceitar, rejeitar,
ou entrar em loop.

As MTs que são chamadas de decisores, sempre
tomam uma decisão de aceitar ou rejeitar.

Um decisor que reconhece alguma linguagem também
é dito decidir essa linguagem.
MT
Linguagem Recursiva

Chame uma linguagem de Turing-decidível ou
simplesmente decidível se alguma máquina de Turing
a decide.