_______________________________________________________________________________________________________________ - 1 -

Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04

Cursos: Bacharelado em Cincia da Computao e
Bacharelado em Sistemas de Informao
Disciplinas: (1493A) Teoria da Computao e Linguagens Formais,
(4623A) Teoria da Computao e Linguagens Formais e
(1601A) Teoria da Computao
Professora: Simone das Graas Domingues Prado
e-mail: simonedp@[Link]
home-page: [Link]/~simonedp/[Link]




Apostila 04
Assunto: Mquina de Turing



Objetivo:
Estudar a Mquina de Turing




Contedo:
1. Introduo
2. Mquina de Turing como Reconhecedora
3. Mquina de Turing como Transdutores
4. Tese de Turing
5. Outros Modelos de Mquina de Turing


_______________________________________________________________________________________________________________ - 2 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
1. Introduo


Em 1936, Alan Turing introduziu um modelo matemtico do processo de computao conhecido
atualmente como Mquina de Turing. Sua estrutura simples e o principal modelo usado para o estudo
do que ou no computvel.

Ainda em 1936, Alonzo Church apresentou a sua Hiptese que afirma que qualquer funo computvel
pode ser processada por uma Mquina de Turing.

Existem vrios modelos de Mquinas de Turing. Nessa apostila veremos alguns destes modelos.

Um dos Objetivos da Disciplina estudar as Linguagens (Figura 1). Anteriormente foram estudadas as
Linguagens Regulares e as Linguagens Livres de Contexto. Para cada tipo de Linguagem foram estudados
formalismos para a seu reconhecimento e gerao.


Figura 1. Hierarquia de Chomsky

Para as Linguagens Regulares (tipo 03) foram estudados os formalismos:
Operacional ou reconhecedor Autmato Finito (determinstico, no determinstico, mnimo)
Axiomtico ou gerador Gramtica Regular
Denotacional Expresso Regular

Para as Linguagens Livres de Contexto (tipo 02) foram estudados dois formalismos:
Operacional ou reconhecedor Autmato com Pilha (determinstico, no determinstico)
Axiomtico ou gerador Gramtica Livre de Contexto

Para as Linguagens Sensveis ao Contexto (tipo 01) e Linguagens Enumerveis Recursivamente (tipo 0)
tambm sero usados formalismos: reconhecedor e gerador das mesmas.

Para as Linguagens Sensveis ao Contexto (tipo 01) sero usados os formalismos:
Operacional ou Reconhecedor Mquina de Turing com Fita Limitada
Axiomtico ou gerador Gramtica Sensvel ao Contexto

Para as Linguagens Enumerveis Recursivamente (tipo 0) sero estudados os formalismos:
Operacional ou Reconhecedor Mquina de Turing
Axiomtico ou gerador Gramtica Irrestrita
_______________________________________________________________________________________________________________ - 3 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Como a Mquina de Turing ser usada como um formalismo reconhecedor das Linguagens Sensveis ao
Contexto e Enumerveis Recursivamente, nessa apostila sero estudadas as Mquinas de Turing de uma
forma geral.

A Mquina de Turing consiste de basicamente trs partes (veja Figura 2): Uma fita, uma unidade de
controle e uma funo de transio. A fita usada como um dispositivo de entrada, sada e memria. Ela
dividida em clulas que armazenam um smbolo de cada vez. A unidade de controle reflete o estado
controle da mquina. Possui uma unidade de leitura e gravao que pode deslocar-se para a esquerda (L)
ou para a direita (R) da fita, podendo ler e/ou gravar um nico smbolo em cada movimento. A funo de
transio comanda as leituras e gravaes, o sentido de movimento da cabea e define o estado da
mquina.






...
Figura 2. Uma Mquina de Turing



Definio 1.

Uma Mquina de Turing definida como uma stupla
M = (Q, , , , q0, F)


Onde:
Q conjunto de estados internos
conjunto do alfabeto de entrada
conjunto finito de smbolos, chamado de alfabeto da fita
funo de transio, definida por : Q x Q x x {L, R}
q
0
estado inicial ( q
0
Q )
F conjunto de estados finais ( F Q )


Observao:
um smbolo especial chamado de branco ( )









Unidade de
Controle Fita
Cabea de
Leitura/Gravao
_______________________________________________________________________________________________________________ - 4 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Exemplo 01: Seja a funo de transio (q
0
,a) = (q
1
,d,R). Veja o que acontece na Figura 3.

q
0
q
1

a b c d b c
Figura 3. Uma funo de transio em uma Mquina de Turing

Ou seja, estando em q
0
, lendo o smbolo a da fita, ento troca a por d, vai uma casa para a direita e vai
para o estado q
1
.

Exemplo 02:
Considere a Mquina de Turing M = ({q
0
,q
1
}, {a,b}, {a,b,}, , q
0
, {q
1
}) com
(q
0
,a) = (q
0
,b,R),
(q
0
,b) = (q
0
,b,R),
(q
0
, )=(q
1
, ,L).

Assim,
(q
0
,a) = (q
0
,b,R): ao ler o smbolo a, a Mquina de Turing escreve o smbolo b, anda uma clula para a
direita e permanece no mesmo estado.


q
0


q
0


a B b b
Figura 4. Uma funo de transio em uma Mquina de Turing

(q
0
,b) = (q
0
,b,R): ao ler o smbolo b, mantm-se o smbolo b, anda uma clula para a direita e permanece
no mesmo estado.

q
0
q
0

b b b b
Figura 5. Uma funo de transio em uma Mquina de Turing


(q
0
, )=(q
1
, ,L) : ao ler o smbolo branco (), mantm-se o smbolo , anda uma clula para a esquerda
e muda para o estado q
1
, que o estado final. Ento o processo pra.

q
0
q
1

b B b b
Figura 6. Uma funo de transio em uma Mquina de Turing


Exemplo 03:
Considere a Mquina de Turing M = ({q
0
,q
1
}, {a,b}, {a,b,}, , q
0
, {}) com
(q
0
,a) = (q
1
,a,R),
(q
0
,b) = (q
1
,b,R),
(q
0
,)=(q
1
,,R),
(q
1
,a) = (q
0
,a,L),
(q
1
,b) = (q
0
,b,L),
(q
1
,)=(q
0
,,L).
Percebe-se que essa Mquina de Turing entrar em loop infinito, j que no tem estado final definido.
_______________________________________________________________________________________________________________ - 5 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04

A aceitao de uma cadeia pela Mquina de Turing acontece quando o estado final atingido
independente de onde a cabea est na fita. Se a Mquina de Turing pra em algum estado no final ou
simplesmente entrar em loop infinito, ento a cadeia no aceita.




1.2. Descrio instantnea

Qualquer configurao de uma Mquina de Turing completamente determinada pelo estado corrente da
unidade de controle, o contedo da fita e a posio da cabea de leitura-escrita. A configurao pode ser
dada pela notao: xqy

onde x e y o contedo da fita e q o estado da unidade de controle.

A mudana de configurao dada pelo smbolo , ento:
Movimento para a direita se (q,a) = (p,b,R), ento xqay xbpy
Movimento para a esquerda se (q,a) = (p,b,L), ento xcqay xpcby
Movimento para a direita, lendo um branco se (q,) = (p,b,R), ento xq xbp
Movimento para a direita, lendo um branco se (q,) = (p,b,L), ento xcq xpcb

Exemplo 04:
A ao da Mquina de Turing do exemplo 02 aplicada na cadeia aa pode ser representada por:
q
0
aa bq
0
a bbq
0
bq
1
b,
ou seja, q
0
aa * bq
1
b


Definio 2.
Seja uma Mquina de Turing M = (Q, , , , q
0
, F). Ento qualquer cadeia a
1
...a
k-1
q
1
a
k
a
k+1
...a
n
, com a
i

e q
i
Q uma descrio instantnea de M.

Um movimento a
1
...a
k-1
q
1
a
k
a
k+1
...a
n
a
1
...a
k-1
bq
2
a
k+1
...a
n

possvel se e somente se (q
1
,a
k
) = (q
2
,b,R).

Um movimento a
1
...a
k-1
q
1
a
k
a
k+1
...a
n
a
1
...q
2
a
k-1
ba
k+1
...a
n

possvel se e somente se (q
1
,a
k
) = (q
2
,b,L).

M dito estar no estado de interrupo para alguma configurao inicial x
1
q
i
x
2
se
x
1
q
i
x
2
* y
1
q
j
ay
2

para quaisquer q
j
e a, para os quais (q
j
,a) indefinida.


O caso especial onde a Mquina de Turing entra em loop infinito (veja Exemplo 03) pode ser representada
por: x
1
qx
2
*

_______________________________________________________________________________________________________________ - 6 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
2. Mquinas de Turing como reconhecedores


Uma linguagem aceita ou reconhecida por uma Mquina de Turing dada pela definio abaixo:


Definio 03

Seja uma Mquina de Turing M = (Q, , , , q
0
, F), ento a linguagem reconhecida por M :
L(M) = { w
+
: q
0
w * x
1
q
f
x
2
para algum q
f
F e x
1
,x
2
*}


Exemplo 05:
Para = {0,1}, a Mquina de Turing que aceita a linguagem denotada pela Expresso Regular ER = 0*
pode ser definida como:
M = ({q
0
,q
1
}, {0}, {0,}, , q
0
, {q
1
}) com
(q
0
,0) = (q
0
,0,R) e
(q
0
, ) = (q
1
,,R).


Exemplo 06:
Para = {a,b}, a Mquina de Turing que aceita L = {a
n
b
n
| n 1} pode ser definida como:
M = ({q
0
,q
1
,q
2
,q
3
,q
4
}, {a,b}, {a,b,x,y,}, , q
0
, {q
4
}) com:
(q
0
,a) = (q
1
,x,R),
(q
1
,a) = (q
1
,a,R),
(q
1
,y) = (q
1
,y,R),
(q
1
,b) = (q
2
,y,L),
(q
2
,y) = (q
2
,y,L),
(q
2
,a) = (q
2
,a,L),
(q
2
,x) = (q
0
,x,R)
(q
0
,y) = (q
3
,y,R),
(q
3
,y) = (q
3
,y,R),
(q
3
,) = (q
4
,,R)

Figura 7. Simulando com o JFLAP
_______________________________________________________________________________________________________________ - 7 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04

Figura 8. Simulador Turing




Note que:
O estado q
0
ao encontrar a, escreve x (ou seja, marca a) e muda de estado (q
1
).
O estado q
1
responsvel por encontrar um b e marc-lo com y
A partir da, outro estado (q
2
) entra em ao. Ele volta na fita at encontrar x (o ltimo a
marcado)
Quando q
2
encontra o x, devolve o controle para o estado q
0
que recomea o processamento.
Quando q
0
encontra o y significa que j terminou de marcar os smbolos a. Ento, se no
houver mais b para serem marcados, a cadeia est correta.
Para isso, usado o estado q
3
para percorrer o restante da cadeia. Se encontrar s y e encontrar o
branco (), ento a cadeia est correta.
Se encontrar algum b, a Mquina de Turing pra (j que no existe uma transio (q
3
,b) = ... ) e
a cadeia no aceita.

Assim, na Mquina de Turing, os estados tm funes bem definidas a serem executadas.
q
0
responsvel em marcar o smbolo a e acionar q
1
ou se encontrar y, acionar q
3

q
1
responsvel por encontrar um b, marc-lo (y) e acionar o q
2
. Se ele encontrar um
branco(), significa que falta b nesta cadeia. A cadeia no ser aceita.
q
2
responsvel por voltar na fita at encontrar o ltimo a marcado, ou seja, um x. Ao
encontrar, aciona o q
0

q
3
responsvel pela verificao final da cadeia. Se encontrar s y e branco (), ento a cadeia
est correta e aciona o q
4
. Caso contrrio, a cadeia no aceita.
q
4
o estado final, indicando que a cadeia est correta.





_______________________________________________________________________________________________________________ - 8 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Seja w = aabb, ento:
q
0
aabb xq
1
abb xaq
1
bb xq
2
ayb q
2
xayb xq
0
ayb xxq
1
yb xxyq
1
b xxq
2
yy xq
2
xyy
xxq
0
yy xxyq
3
y xxyyq
3

xxyyq
4
xxyyq
4
.
Como q
4
F, ento w = aabb L(M).

Seja w = aab, ento:
q
0
aab xq
1
ab xaq
1
b xq
2
ay q
2
xay xq
0
ay xxq
1
y xxyq
1

Como no existe (q
1
,), ento w = aab no pertence L(M).

Seja w = aabbb, ento:
q
0
aabbb xq
1
abbb xaq
1
bbb xq
2
aybb q
2
xaybb xq
0
aybb xxq
1
ybb xxyq
1
bb xxq
2
yyb
xq
2
xyyb xxq
0
yyb xxyq
3
yb xxyyq
3
b
Como no existe (q
3
,b), ento w = aabbb no pertence L(M).


Exemplo 07:
Para = {a,b}, a Mquina de Turing que aceita L = {a
n
b
n
c
n
| n 1} pode ser definida como:
M = ({q
0
,q
1
,q
2
,q
3
,q
4
,q
5
}, {a,b,c}, {a,b,c,x,y,z,}, , q
0
, {q
5
}) com:
(q
0
,a) = (q
1
,x,R),
(q
1
,a) = (q
1
,a,R),
(q
1
,b) = (q
2
,y,R),
(q
2
,b) = (q
2
,b,R),
(q
2
,c) = (q
3
,z,L),
(q
3
,b) = (q
3
,b,L),
(q
3
,y) = (q
3
,y,L),
(q
3
,a) = (q
3
,a,L),
(q
3
,x) = (q
0
,x,R),
(q
1
,y) = (q
1
,y,R),
(q
2
,z) = (q
2
,z,R),
(q
3
,z) = (q
3
,z,L),
(q
0
,y) = (q
4
,y,R),
(q
4
,y) = (q
4
,y,R),
(q
4
,z) = (q
4
,z,R),
(q
4
,) = (q
5
,,R).





Seja w = aabbcc, ento:
q
0
aabbcc xq
1
abbcc xaq
1
bbcc xayq
2
bcc xaybq
2
cc xayq
3
bzc xaq
3
ybzc xq
3
aybzc
q
3
xaybzc xq
0
aybzc xxq
1
ybzc xxyq
1
bzc xxyyq
2
zc xxyyzq
2
c xxyyq
3
zz
xxyq
3
yzz xxq
3
yyzz xq
3
xyyzz xxq
0
yyzz xxyq
4
yzz xxyyq
4
zz xxyyzq
4
z
xxyyzzq
4

xxyyq
5
xxyyq
5
.
Como q
5
F, ento w = aabbcc L(M).



_______________________________________________________________________________________________________________ - 9 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Exemplo 08:
Para = {a,b}, a Mquina de Turing que aceita L = {wcw
R
| w {a,b}* } pode ser definida como:
M = ({q
0
,q
1
,q
2
,q
3
,q
4
,q
5
,q
6
,q
7
}, {a,b,c}, {a,b,c,x,y,}, , q
0
, {q
7
}) com:
(q
0
,a) = (q
1
,x,R),
(q
1
,a) = (q
1
,a,R),
(q
1
,b) = (q
1
,b,R),
(q
1
,c) = (q
1
,c,R),
(q
1
,) = (q
3
,,L),
(q
1
,x) = (q
3
,x,L),
(q
1
,y) = (q
3
,y,L),
(q
3
,a) = (q
5
,x,L),

(q
0
,b) = (q
2
,y,R),
(q
2
,a) = (q
2
,a,R),
(q
2
,b) = (q
2
,b,R),
(q
2
,c) = (q
2
,c,R),
(q
2
,) = (q
4
,,L),
(q
2
,x) = (q
4
,x,L),
(q
2
,y) = (q
4
,y,L),
(q
4
,b) = (q
5
,y,L),

(q
0
,c) = (q
6
,c,R),
(q
6
,x) = (q
6
,x,R),
(q
6
,y) = (q
6
,y,R),
(q
6
,) = (q
7
,,L).

(q
5
,a) = (q
5
,a,L),
(q
5
,b) = (q
5
,b,L),
(q
5
,c) = (q
5
,c,L),
(q
5
,x) = (q
0
,x,R),
(q
5
,y) = (q
0
,y,R)




















_______________________________________________________________________________________________________________ - 10 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
3. Mquinas de Turing como transdutores


Definio 04

Uma funo f, com domnio D, dita ser Turing-Computvel ou simplesmente computvel se existe
alguma Mquina de Turing M = (Q, , , , q
0
, F) tal que
q
0
w *
M
q
f
f(w), q
f
F
para toda cadeia w D.




Exemplo 09:
Dados dois nmeros positivos x e y. Construa uma Mquina de Turing que calcule x + y.
Seja x = |z(x)| com z(x) {1}*, ou seja, o nmero ser representado pela quantidade de dgitos 1 (por
exemplo, 3 = 111).
A Mquina de Turing dever calcular: q
0
w = q
0
z(x) 0 z(y) * q
f
z(x + y) 0

Seja M = ({q
0
,q
1
,q
2
,q
3
,q
4
}, {1}, {1,0,}, , q
0
, {q
4
}) com:
(q
0
,1) = (q
0
,1,R),
(q
0
,0) = (q
1
,1,R),
(q
1
,1) = (q
1
,1,R),
(q
1
,) = (q
2
,,L),
(q
2
,1) = (q
3
,0,L),
(q
3
,1) = (q
3
,1,L),
(q
3
,) = (q
4
,,R).






seja 5 + 3, ento w = 111110111
q
0
111110111 * 11111q
0
0111 111111q
1
111 1111111q
1
11* 111111111q
1
11111111q
2
1
1111111q
3
10 * q
3
111111110 * q
4
111111110
z(11111111) = 8



Exemplo 10:
Dados dois nmeros positivos x e y. Construa uma Mquina de Turing que verifique se x y ou x < y.
Seja x = |z(x)| com z(x) {1}*, como no exemplo anterior.
A Mquina de Turing dever chegar
ao estado q
maior-igual
se x y , ou seja, q
0
w = q
0
z(x) 0 z(y) * q
maior-igual
z(x) 0 z(y)
ao estado q
menor
se x < y, ou seja, q
0
w = q
0
z(x) 0 z(y) * q
menor
z(x) 0 z(y)



_______________________________________________________________________________________________________________ - 11 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
M = ({q
0
,q
1
,q
2
,q
3
,q
4
,q
f
,q
v
, q
>=
, q
<
}, {1,0}, {1,0,x,y,}, , q
0
, { q
>=
, q
<
}) com:
(q
0
,1) = (q
1
,x,R),
(q
0
,0) = (q
4
,0,R),
(q
1
,1) = (q
1
,1,R),
(q
1
,0) = (q
2
,0,R),
(q
2
,1) = (q
3
,y,L),
(q
2
,y) = (q
2
,y,R),
(q
2
,) = (q
v
,,L),
(q
3
,y) = (q
3
,y,L),
(q
3
,0) = (q
3
,0,L),
(q
3
,1) = (q
3
,1,L),
(q
3
,x) = (q
0
,x,R),
(q
4
,y) = (q
4
,y,R),
(q
4
,1) = (q
f
,1,L),
(q
4
,) = (q
v
,,L),
(q
f
,0) = (q
f
,0,L),
(q
f
,y) = (q
f
,1,L),
(q
f
,x) = (q
f
,1,L),
(q
f
,) = (q
<
,,R),
(q
v
,y) = (q
v
,1,L),
(q
v
,x) = (q
v
,1,L),
(q
v
,0) = (q
v
,0,L),
(q
v
,1) = (q
v
,1,L),
(q
v
,) = (q
>=
,,R).






Seja x = 5 e y = 3, ento w = 111110111
q
0
111110111 xq
1
11110111 * x1111q
1
0111 x11110q
2
111 x1111q
3
0y11 x111q
3
10y11
* q
3
x11110y11 xq
0
11110y11 xxq
1
1110y11* xx111q
1
0y11 xx1110q
2
y11
xx1110yq
2
11 xx1110q
3
yy1 xx111q
3
0yy1 xx11q
3
10yy1* xq
3
x1110yy1
xxq
0
1110yy1xxxq
1
110yy1* xxx11q
1
0yy1 xxx110q
2
yy1* xxx110yyq
2
1
xxx110yq
3
yy* xxx11q
3
0yyy xxx1q
3
10yyy* xxq
3
x110yyy xxxq
0
110yyy
xxxxq
1
10yyy xxxx1q
1
0yyy xxxx10q
2
yyy* xxxx10yyyq
2
xxxx10yyq
v1
y
* xxxx1q
v1
0111 xxxxq
v1
10111 xxxq
v1
x10111* q
v1
111110111
q
>=
111110111
Ento 5 3, j que se chegou a q
>=


Seja x = 2 e y = 3, ento w = 110111
q
0
110111 xq
1
10111 x1q
1
0111 x10q
2
111 x1q
3
0y11 xq
3
10y11 q
3
x10y11
xq
0
10y11 xxq
1
0y11 xx0q
2
y11xx0yq
2
11 xx0q
3
yy1 xxq
3
0yy1 xq
3
x0yy1
xxq
0
0yy1 xx0q
4
yy1* xx0yyq
4
1 xx0yq
f1
y1* xxq
f1
0111 xq
f1
x0111
* q
f1
110111 q
<
110111
Ento 2 < 3, j que se chegou a q
<

_______________________________________________________________________________________________________________ - 12 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Seja x = 2 e y = 2, ento w = 11011
q
0
11011 xq
1
1011 x1q
1
011 x10q
2
11 x1q
3
0y1 xq
3
10y1 q
3
x10y1
xq
0
10y1 xxq
1
0y1 xx0q
2
y1xx0yq
2
1 xx0q
3
yy xxq
3
0yy xq
3
x0yy
xxq
0
0yy xx0q
4
yy* xx0yyq
4
xx0yq
v1
y* q
v1
11011 q
>=
11011
Ento 2 = 2, j que se chegou a q
>=





Exemplo 11:
Dados dois nmeros positivos x e y. Construa uma Mquina de Turing que verifique calcule a funo:
y x se
y x se y x
y x f
<

+
=
, 0
,
) , (

Seja x = |z(x)| com z(x) {1}*, como nos exemplos anteriores.

A Mquina de Turing passar por duas etapas (veja a figura 04):
A primeira etapa verifica se x y ou x < y (como no Exemplo 09)
A segunda etapa recebe um sinal da etapa anterior
Se sinal que x y, ento faz x + y (como no Exemplo 08)
Se sinal que x < y, ento coloca na fita 0












Figura 9. Uma MT complexa

Se x = 3 e y = 2, w = 111011, f(x,y) = 11111
Se x = 2 e y = 3, w = 110111, f(x,y) = 0

Obs: Para enviar um sinal deve-se mudar de estado.


A Mquina de Turing dever fazer:

1
a
. Etapa:
q
C0
z(x) 0 z(y) * q
S0
z(x) 0 z(y) se x y
q
C0
z(x) 0 z(y) * q
A0
z(x) 0 z(y) se x < y
Comparador
Somador
Apagador
_______________________________________________________________________________________________________________ - 13 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
2. Etapa:
q
S0
z(x) 0 z(y) * q
Sf
z(x + y) 0 ou
q
A0
z(x) 0 z(y) * q
Af
0

q
C0
= estado inicial do comparador
q
S0
= estado final do comparador quando x y, e tambm o estado inicial do somador
q
A0
= estado final do comparador quando x < y, e tambm o estado inicial do apagador
q
Sf
= estado final do somador
q
Af
= estado final do apagador
Veja como fica a Mquina de Turing:

M = ({q
0
,q
1
,q
2
,q
3
,q
4
,q
f
,q
v
,q
0s
,q
1s
,q
2s
,q
3s
,q
4s
,q
0a
,q
1a
,q
2a
,q
3a
,q
4a
}, {1,0}, {1,0,x,y,}, , q
0
, { q
4s
, q
4a
}) com:

Comparador:
(q
0
,1) = (q
1
,x,R),
(q
0
,0) = (q
4
,0,R),
(q
1
,1) = (q
1
,1,R),
(q
1
,0) = (q
2
,0,R),
(q
2
,1) = (q
3
,y,L),
(q
2
,y) = (q
2
,y,R),
(q
2
,) = (q
v
,,L),
(q
3
,y) = (q
3
,y,L),
(q
3
,0) = (q
3
,0,L),
(q
3
,1) = (q
3
,1,L),
(q
3
,x) = (q
0
,x,R),
(q
4
,y) = (q
4
,y,R),
(q
4
,1) = (q
f
,1,L),
(q
4
,) = (q
v
,,L),
(q
f
,0) = (q
f
,0,L),
(q
f
,y) = (q
f
,1,L),
(q
f
,x) = (q
f
,1,L),
(q
f
,) = (q
0a
,,R),
(q
v
,y) = (q
v
,1,L),
(q
v
,x) = (q
v
,1,L),
(q
v
,0) = (q
v
,0,L),
(q
v
,1) = (q
v
,1,L),
(q
v
,) = (q
0s
,,R).

Somador:
(q
0s
,1) = (q
0s
,1,R),
(q
0s
,0) = (q
1s
,1,R),
(q
1s
,1) = (q
1s
,1,R),
(q
1s
,) = (q
2s
,,L),
(q
2s
,1) = (q
3s
,0,L),
(q
3s
,1) = (q
3s
,1,L),
(q
3s
,) = (q
4s
,,R).
_______________________________________________________________________________________________________________ - 14 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Apagador:
(q
0a
,1) = (q
1a
,0,R),
(q
0a
,0) = (q
1a
,0,R),
(q
1a
,1) = (q
1a
,,R),
(q
1a
,0) = (q
1a
,,R),
(q
1a
,) = (q
2a
,,L),
(q
2a
,) = (q
2a
,,L),
(q
2a
,0) = (q
3a
,0,L),
(q
3a
,) = (q
4a
,,R),





Seja x = 5 e y = 3, ento w = 111110111
q
0
111110111 xq
1
11110111 * x1111q
1
0111 x11110q
2
111 x1111q
3
0y11 x111q
3
10y11
* q
3
x11110y11 xq
0
11110y11 xxq
1
1110y11* xx111q
1
0y11 xx1110q
2
y11
xx1110yq
2
11 xx1110q
3
yy1 xx111q
3
0yy1 xx11q
3
10yy1* xq
3
x1110yy1
xxq
0
1110yy1xxxq
1
110yy1* xxx11q
1
0yy1 xxx110q
2
yy1* xxx110yyq
2
1
xxx110yq
3
yy* xxx11q
3
0yyy xxx1q
3
10yyy* xxq
3
x110yyy xxxq
0
110yyy
xxxxq
1
10yyy xxxx1q
1
0yyy xxxx10q
2
yyy* xxxx10yyyq
2
xxxx10yyq
v1
y
* xxxx1q
v1
0111 xxxxq
v1
10111 xxxq
v1
x10111* q
v1
111110111
q
0s
111110111
* 11111q
0s
0111 111111q
1s
111 1111111q
1s
11* 111111111q
1s
11111111q
2s
1
1111111q
3s
10 * q
3s
111111110 * q
4s
111111110

Sabendo que z(111111110) = 8, temos que: f(5,3) = 8




_______________________________________________________________________________________________________________ - 15 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
Seja x = 2 e y = 3, ento w = 110111
q
0
110111 xq
1
10111 x1q
1
0111 x10q
2
111 x1q
3
0y11 xq
3
10y11 q
3
x10y11
xq
0
10y11 xxq
1
0y11 xx0q
2
y11xx0yq
2
11 xx0q
3
yy1 xxq
3
0yy1 xq
3
x0yy1
xxq
0
0yy1 xx0q
4
yy1* xx0yyq
4
1 xx0yq
f1
y1* xxq
f1
0111 xq
f1
x0111
* q
f1
110111 q
0a
110111
0q
1a
10111 0q
1a
0111 *0q
1a
0q
2a
* q
2a
0 0q
3a
q
4a
0



Exemplo 12:
Considere a macroinstruo:
if a
then q
j

else q
k

ou seja, a Mquina de Turing ao ler o smbolo a, move-se para o estado q
j
sem alterar o contedo da fita e
sem alterar a posio da cabea de leitura/escrita. Caso contrrio, move-se para q
k
sem causar nenhuma
alterao.

Ento podem ser escritas as seguintes funes de transio:
(q
i
, a) = (q
j0
, a, R) para todo q
i
Q
(q
i
, b) = (q
k0
, b, R) para todo q
i
Q, todo b -{a}
(q
j0
, c) = (q
j
, c, L) para todo c
(q
k0
, c) = (q
k
, c, L) para todo c

Ao ler o smbolo a, estando em qualquer estado, vai-se para o estado q
j0
(estado auxiliar) que volta uma
posio e passa para o estado q
j
. Dessa forma, a cabea da fita volta na clula que tem o smbolo a no
estado q
j
.



q
i


q
j0

q
j


a c a c a c

Ao ler qualquer outro smbolo (b, por exemplo), a cabea da fita vai para a direita e muda o estado para
q
k0
(tambm um estado auxiliar). Estando no estado q
k0
, a cabea da fita move-se para a esquerda e fica no
estado q
k
.

q
i
q
k0
q
k

b c b c b c


Fazendo isso, a Mquina de Turing consegue resolver a macroinstruo if a then q
j
else q
k







_______________________________________________________________________________________________________________ - 16 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
OBSERVAO

possvel trabalhar com subprogramas nas Mquinas de Turing. A idia que uma Mquina de Turing
(MT-A) possa invocar outra Mquina de Turing (MT-B) para executar um subprograma. Isso ir requerer
uma nova caracterstica: as duas trocaro informaes. Para simular isso, basta que se reserve uma regio
da fita para fazer a troca de informao.




4. Tese de Turing


Qualquer computao que pode ser executada por meios mecnicos pode ser
executada por uma Mquina de Turing





Definio 05

Um algoritmo, para uma funo f: D R, uma Mquina de Turing M, M = (Q, , , , q
0
, F), se para
uma entrada qualquer w D, a mquina de Turing encontra a resposta correta f(d) R tal que
q
0
w *

q
f
f(w), q
f
F
para toda cadeia w D.




5. Outros modelos de Mquinas de Turing


5.1. Mquina de Turing com opo de parada

Essa Mquina de Turing acrescenta, na sua funo de transio, a possibilidade de no mover a cabea da
fita a cada movimento. Assim, a definio como Mquina de Turing (Definio 01) s altera a definio
da funo de transio para:

: Q x Q x x {L, R, S}

onde aparece, alm dos smbolos L e R, o smbolo S (Stay-ficar)

Essas Mquinas de Turing so equivalentes s Mquinas de Turing vistas anteriormente.



_______________________________________________________________________________________________________________ - 17 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
5.2. Mquina de Turing com fita semi-infinita

Uma Mquina de Turing pode ter uma fita infinita esquerda e/ou direita. Se a fita ilimitada
esquerda e direita ento temos uma Mquina de Turing padro. Caso haja um limite na fita direita ou
esquerda ela chamada de Mquina de Turing com fita semi-infinita. Dessa forma, em uma direo da
fita os movimentos so restritos. No se pode mover para fora da fita.

Se nas duas direes h restries de movimento ento estaremos trabalhando com uma Mquina de
Turing com fita limitada. Essa tambm chamada de Autmato Limitado Linearmente ou Autmato de
Fita limitada. Essa Mquina de Turing ser vista posteriormente.



5.3. Mquina de Turing com mltiplas fitas

Essa Mquina de Turing possui mais que uma fita e para cada uma dessas fitas existe uma cabea de
leitura/escrita. A sua definio segue a Definio 01 com a modificao da funo de transio para:

: Q x
n
Q x
n
x {L, R}
n


onde n a quantidade de fitas na Mquina de Turing.

Suponha n = 2 e a funo de transio: (q
0
, a, b) = (q
1
, x, y, L, R),
Pode-se ler: estando no estado q
0
- ao ler na Fita01 o smbolo a e na Fita02 o smbolo b ento vai para o
estado q
1
, escreve x na Fita01, y na Fita02 e move-se para a esquerda na Fita01 e para a direita na Fita02.






5.4. Mquina de Turing com mltiplas cabeas

Essa Mquina de Turing possui uma nica fita e k ( k > 1) cabeas de leitura/gravao sobre a mesma
fita. O processamento depender do estado corrente e do smbolo lido em cada uma das cabeas.





5.5. Mquina de Turing com mltiplas trilhas

Essa Mquina de Turing possui uma nica fita e uma cabea de leitura/gravao, s que possui mltiplas
trilhas na fita. Isso implica em ter mais de um smbolo em cada posio de leitura/escrita da cabea da fita.
Por exemplo, pode conter pares de elementos de . Assim as triplas como smbolos (a
1
,b
1
,c
1
), (a
2
,b
2
,c
2
),
..., (a
n
,b
n
,c
n
) podem ser vistos como n smbolos ou como combinao de trs cadeias, uma em cada trilha:
a
1
b
1
c
1
, a
2
b
2
c
2
, ..., a
n
b
n
c
n


_______________________________________________________________________________________________________________ - 18 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04
5.6. Mquina de Turing Multidimensional

Nessa Mquina de Turing a fita substituda por uma estrutura m-dimensional, infinita em todas as suas
direes. Por exemplo, numa Mquina de Turing bidimensional a cabea de leitura/gravao da fita pode
ir para esquerda, direita, acima e abaixo e funo de transio pode ser definida como:

: Q x Q x x {L, R, U, D}

onde U (up) para cima e D (down) para baixo



5.7. Mquina de Turing No Determinstico


Definio 06

Uma Mquina de Turing No Determinstica, M = (Q, , , , q
0
, F), aquela em que a funo de
transio definida da forma:
: Q x 2
Q x x {L, R}



Assim, a funo de transio poder gerar subconjuntos, ou seja, vrias possibilidades a partir de um
estado e um smbolo lido.

Suponha a funo de transio: (q
0
,a) = {(q
1
, x, R), (q
2
, y, L)}
Os movimentos q
0
aaa xq
1
aa e q
0
aaa q
1
yaa so possveis.

OBS: As Mquinas de Turing No Determinsticas so equivalentes s Mquinas de Turing
Determinsticas (Definio 01).



5.8. Mquina de Turing com fita limitada ou Autmato Limitado Linearmente

A Mquina de Turing tem uma fita ilimitada. Para fazer a restrio de limites nas duas direes, a fita ir
possuir um nmero de clulas que conter a entrada mais duas clulas. Essas duas clulas a mais
armazenaro os smbolos especiais: [ e ] que simbolizam o incio e o final da entrada.


Definio 07

Um Autmato Limitado Linearmente uma Mquina de Turing No Determinstica,
M = (Q, , , , q
0
, F), onde:
a) deve conter os smbolos [ e ]
b) (q
i
, [) = (q
j
, [, R)
c) (q
i
, ]) = (q
j
, ], R)
_______________________________________________________________________________________________________________ - 19 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04

Definio 08

Uma cadeia aceita por um Autmato Limitado Linearmente se existe uma seqncia possvel de
movimentos
q
0
[w] *

[ x
1
q
f
x
2
]
para algum q
f
F e x
1
,x
2
*.

A linguagem aceita por um Autmato Limitado Linearmente o conjunto de todas as cadeias aceitas.


Exemplo 12:
A linguagem L = {ww | w uma cadeia de {a,b}*} tem o Autmato Limitado Linearmente M:
M = ({q
0
,q
1
,...,q
11
,q
f
), {a,b,[,]}, {a,b,x,y}, , q
0
, {q
f
}) onde
(q
0
, [) = {(q
1
, [, R)},
(q
1
, a) = {(q
2
, x, R)},
(q
1
, b) = {(q
3
, x, R)},
(q
1
, ]) = {(q
f
, ], L)},
(q
2
, a) = {(q
2
, a, R), (q
4
, y, L)}
(q
2
, b) = {(q
2
, b, R)},
(q
3
, a) = {(q
3
, a, R), (q
4
, y, L)}
(q
3
, b) = {(q
3
, b, R)},
(q
4
, a) = {(q
4
, a, L)},
(q
4
, b) = {(q
4
, b, L)},
(q
4
, x) = {(q
5
, x, R)},
(q
5
, a) = {(q
6
, x, R)},
(q
5
, b) = {(q
8
, x, R)},
(q
5
, y) = {(q
11
, y, R)},
(q
6
, a) = {(q
6
, a, R)},
(q
6
, b) = {(q
6
, b, R)},
(q
6
, y) = {(q
7
, y, R)},
(q
8
, a) = {(q
8
, a, R)},
(q
8
, b) = {(q
8
, b, R)},
(q
8
, y) = {(q
9
, y, R)},
(q
7
, a) = {(q
10
, y, L)},
(q
7
, y) = {(q
7
, y, R)},
(q
9
, b) = {(q
10
, y, L)},
(q
9
, y) = {(q
9
, y, R)},
(q
10
, a) = {(q
10
, a, L)},
(q
10
, b) = {(q
10
, b, L)},
(q
10
, y) = {(q
10
, y, L)},
(q
10
, x) = {(q
5
, x, R)},
(q
11
, y) = {(q
11
, y, R)},
(q
11
, ]) = {(q
f
, ], L)}.

_______________________________________________________________________________________________________________ - 20 -
Teoria da Computao e Linguagens Formais - Simone Domingues Prado Apostila 04