Máquina de Turing e
Computabilidade
•Máquinas de Turing são os autômatos mais potentes que estudaremos.
•Elas podem computar qualquer função computável;
•Há até quem acredite que tudo que é
efetivamente computável é computável por uma MT.
Outras noções de
computabilidade
•  - cálculo (Church 1933);
• Funções  - recusivas (Gödel 1936);
• Combinadores lógicos (Schönfinkel
1924, Curry 1929);
• Sistema de Post (Post 1943);
• Máquiinas de Turing (Turing 1936-7).
Tese de Church-Turing
Todos os sistemas acima captam a
noção de computável.
SIMULAÇÃO UNIVERSAL OU
PROGRAMAS COMO DADOS.
Máquina de Turing (Descrição Informal)
├
a
b
b
a
b
a
■
■
■
■
ambos sentidos, lê/escreve
Q
...
Máquina de Turing:
•conjunto finito de estados Q;
•uma fita semi-infinita, isto é, ela é
delimitada à esquerda pelo símbolo ├ e
infinita a direita;
•o cabeçote da fita pode se mover para a
direita e para esquerda da fita e pode
escrever símbolos sobre a fita;
•a entrada da fita é de tamanho finito e
inicialmente está logo após o ├ (à direita);
•as infinitas células a direita da cadeia de
entrada todas também contém o símbolo
especial nulo ■;
•funcionamento começa no estado inicial S
e o cabeçote sobre ├;
•a cada passo a MT lê o símbolo sobre o cabeçote, e dependendo deste símbolo e do
estado corrente, escreve um novo símbolo
nesta célula, move o cabeçote para a
direita ou para a esquerda e entra num novo
estado (função de transição );
•a MT aceita a cadeia de entrada indo para
um estado especial t e rejeita indo para um
estado especial r;
•para algumas cadeias de entrada a MT
pode funcionar infinitamente sem nunca
aceitá-la ou rejeitá-la.
Uma Máquina de Turing é uma 9-tupla
M = (Q,,,■,├,,s,t,r) onde:
•Q é o conjunto finito de estados;
• é o alfabeto de entrada (finito);
• é o alfabeto da fita contendo  como um
subconjunto (finito)
•u \ , símbolo nulo;
•├  \ , delimitador à esquerda
•: Qx  Qxx{L,R}, função de transição
•sQ, estado inicial
•tQ, estado de aceitação
•rQ, estado de rejeição
Restrições:
• Nunca escrever sobre├ e nunca se
mover para fora da fita à esquerda.
– Para todo pQ existe um qQ tal que
(p,├) = (q,├,R)
• Uma vez que a TM entra no estado
de aceitação/rejeição ela nunca sai.
– Para todo b existe c,c’ e
d,d’{L,R} tal que
 (t,b) = (t,c,d)
 (r,b) = (r,c’,d’)
EXEMPLO:
MT que aceita { anbncn / n 0}.
Informalmente:
•A MTcomeça no estado inicial S,
varre a entrada a direita, checando
se é da forma a*b*c*.
•Ela não escreve no seu caminho
(formalmente ela escreve o que leu).
•Até encontrar o primeiro ■, daí troca
este símbolo por um delimitador à
direita .
•Agora a MT varre a fita a esquerda
apagando o primeiro c que encontra,
então o primeiro b e também o primeiro
a.
•A MT varre a direita apagando um a,
um b, e um c.
•A MT continua indo da direita para
esquerda (e vice-versa) apagando uma
ocorrência de cada letra a cada passo.
• Se em algum passo ela encontra
uma ocorrência de um símbolo e
nenhuma de outra, ela rejeita a
cadeia.
• Senão, ela vai apagar todas as
letras e no passo final terá
somente nulos entre├ e , neste
ponto a MT aceita a cadeia.
Formalmente:
Q={s,q1,…,q10,t,r} ={a,b,c} ={,■,}
Função de transição:
S
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
├
a
(S,├,R) (S,a,R)
_
(r, _ , _ )
_
(r, _ , _ )
(t, _ , _ ) (r, _ , _ )
(r, _ , _ ) (r, _ , _ )
(r, _ , _ ) (q6,■,L)
(q7,├,R) (q6,a,L)
_
(q8,■,R)
_
(q8,a,R)
_
_
_
_
b
(q1,b,R)
(q1,b,R)
(r, _ , _ )
(r, _ , _ )
(q5,■,L)
(q5,b,L)
_
(r, _ , _ )
(q9,■,R)
(q9,b,R)
_
c
(r, _ , _ )
(q2,c,R)
(q2,c,R)
(q4,■, L)
(q4,c,L)
_
_
(r, _ ,_ )
(r, _ , _ )
(q10,■,R)
(q10,c,R)
■

(q3,,L)
_
(r, _ , _ )
_
(q3,,L)
_
(q3,■,L)
_
(q4,■,L )
_
(q5,■,L)
_
(q6,■,L)
_
(q7,■,R) (t, _ _ )
(q8,■,R) (r, _ , _ )
(q9,■,R) (r , _, _ )
(q10,■,R) (q3,,L)
•Configuração inicial (S,├ x■,o)
•■ representa um número infinito de ■’s
•0 significa que a máquina está varrendo o
delimitador ├
•Uma MT aceita uma cadeia de entrada x*
se (S,├ x■,0) * (t,y,n) para algum y e n e
•rejeita se (S,├ x■,0)*(r,y,n) para algum y e
n.
•M pára para uma entrada x se ela aceita x
ou rejeita x. M pode ficar rodando infinitamente com a entrada x.
•O conjunto L(M) representa o conjunto de
todas as cadeias aceitas por M.
• Um conjunto de cadeias é Recursivamente Enumerável (RE) se é L(M)
para alguma máquina de Turing M, e
• Recursivo se é L(M) para alguma máquina de Turing M que pára em todas
as entradas.
Máquinas de Turing com múltiplas fitas
•Fitas extras não adicionam poder
computacional
├ a a b b b a ■ ■ ■ ...
├ b b a b b a a ■ ■ ...
├ a b b a b a a ■ ■ ...
Q
•Uma MT com 3 fitas é similar a MT
com uma fita exceto que a de 3 fitas
tem as 3 fitas e 3 cabeçotes de
leitura.
•Em cada passo a máquina lê os três
símbolos sobre seus cabeçotes, e
baseada nesta informação e no estado
corrente, ela imprime um símbolo em
cada fita, move os cabeçotes (eles
não precisam se mover na mesma
direção) e entra num novo estado.
• A função de transição é do tipo
 : Q x 3  Q x 3 x {L,R}3
• Chamemos a MT com 3 fitas de
M. Podemos construir uma
máquina de Turing com uma fita
N que simula M (EXERCÏCIO).
•Máquinas de Turing infinita dos dois
lados.
•Infinitude para ambos os lados não
adiciona poder computacional.
... a b a a b a a b b a a ...
├
a b b a a ...
a b a a b ...
quebre aqui
• Podemos quebrar a fita original
em qualquer lugar e simular a MT
em uma outra MT infinita só a
direita com duas fitas.
• A fita de cima é usada para simular a MT original quando seu
cabeçote está a direita da quebra,
e a trilha de cima é usada para
simular a MT original quando seu
cabeçote está a esquerda da
quebra, movendo-se na direção
oposta.
EXERCÍCIOS
1. Construir uma gramática livre de contexto
para a linguagem formada pelo conjunto de
cadeias sobre {a,b} que não são Palindromes.
Mostre que sua gramática está correta.
2. Construa uma gramática na forma Normal de
Chomsky para o conjunto não vazio de cadeias
com o número balanceado de parênteses ( ) e
colchetes [ ].
3. Descreva a MT N com uma fita que simula M
com três fitas (veja notas de aula).
Gramáticas Tipo 0
( Sem Restrição)
G = (V,T,P ,S) onde as produções de P
tem a forma  com  e  sendo
cadeias arbitrárias de símbolos da
gramática e   .
   quando   P.
L(G) = {W| W  T* e S * W}
EXEMPLO: A gramática geradora de
{ai |i é uma potência positiva de 2}
1)SACaB
2)CaaaC
3)CBDB
4)CBE
5)aDDa
6)ADAC
7)aEEa
8)AE 
• A e B são delimitadores a direita e
a esquerda das formas sentenciais.
•C é um marcador que se move entre
A e B duplicando o número de a’s
pela produção 2.
•Quando C alcança o delimitador a
direita B ele se transforma em D ou E
pelas produções 3 ou 4.
•Se D é escolhido ele migra pela
produção S até chegar ao delimitador A.
• Neste ponto D se transforma em C
pela produção 6 e o processo começa novamente.
Se E é escolhido, o delimitador a direita é consumido. E migra para a
esquerda pela produção 7 e consome o delimitador a esquerda, resultando em uma cadeia de 2i a’s para
i > 0.
Equivalência entre
Gramáticas Tipo 0
e Máquinas de Turing
TEOREMA: Se L é L(G) para uma
gramática tipo 0 G=(V,T,P ,S), então
L é uma linguagem recursivamente
enumerável.
PROVA:
•Construiremos uma máquina de
Turing não-determinística com duas
fitas M para reconhecer L.
•A primeira fita é uma fita de entrada, onde a cadeia W será colocada.
•A segunda fita é usada para armazenar a forma sentencial  de G.
M inicializa  com S. Então M repetidamente faz:
1)seleciona, não deterministicamente,
uma posição i em , 1 i  |  |. Isto é,
começa na esquerda e repetidamente
se move para direita ou seleciona a
posição atual.
2)seleciona aleatoriamente uma produção  de G.
3)se  aparece começando na posição i
de , troque  por  nesta posição
(shifting over).
4)compare a forma sentencial resultante
com W na fita 1. Se a forma sentencial
for igual a W, aceita w como uma sentença de G. Senão volta para o passo 1.
Obs: Todas e somente as formas
sentenciais de G aparecem na fita
2 quando o passo 2 é executado
depois de algumas escolhas.
• L(M) = L(G) = L então L é
recursivamente enumerável.
q.e.d.
TEOREMA: Se L é uma linguagem
recursivamente enumerável,
então L = L(G) para alguma
gramática tipo 0 G.
• a prova é mais elaborada e é
omitida
Linguagens Sensíveis ao
Contexto
G = (V,T,P,S) onde as produções em P
tem a forma  com  e  sendo cadeias arbitrárias de símbolos da gramática,  e  tem que ser pelo menos
tão grande (longo) quanto .
•O nome sensível ao contexto vem da
forma normal para estas gramáticas
onde cada produção tem a forma
1A2 12 com .
Isto é, a variável A pode ser substituída pela cadeia  somente no
contexto 1 _ 2.
Obs: Quase todas as linguagens que
trabalhamos são sensíveis ao contexto. As únicas provas que certas
linguagens não são sensíveis ao
contexto são baseadas em diagonalização.
Autômatos Linearmente
Limitados (ALL)
Um ALL é uma máquina de Turing
não determinística satisfazendo as
seguintes condições:
1)o alfabeto de entrada inclui dois
símbolos especiais ¢ e s, delimitadores a esquerda e a direita.
2)o ALL não pode se mover a esquerda de ¢ e a direita de s, nem pode
trocar os símbolos ¢ e s na fita.
Obs: Um ALL é uma MT que,ao
invés de ter uma fita potencialmente infinita para computar,
tem somente uma porção da fita
contendo o símbolo x mais duas
células contendo os delimitadores.
Existe uma equivalência entre
ALL e gramáticas sensíveis ao
contexto.
HIERARQUIA DE CHOMSKY
TEOREMA:
(a) os conjuntos regulares estão contidos propriamente nas linguagens livres
de contexto.
(b) LLC não contendo a palavra vazia
estão contidas propriamente nas LSC.
(c) LSC estão propriamente contidas
nos conjuntos recursivamente enumeráveis.