Exercícios sobre máquina de Turing do 2º/2012

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 4
Desenhe o diagrama de estados de uma ma´quina de Turing que compute a func¸a˜o f(n) = 2n,
onde n e´ um nu´mero natural. A ma´quina utiliza notac¸a˜o una´ria, i.e., o nu´mero n e´ representado
pela cadeia 1n. Suponha que, inicialmente, a fita da ma´quina de Turing conte´m @w, onde w e´ a
representac¸a˜o una´ria de n, e a cabec¸a da ma´quina esta´ sobre o s´ımbolo mais a esquerda de w. No
final da operac¸a˜o, a fita devera´ conter @u, onde u e´ a representac¸a˜o una´ria de 2n, e a cabec¸a da
ma´quina devera´ esta´r sobre o s´ımbolo mais a esquerda de u.
Resposta: Em aula vimos uma ma´quina de Turing que copia uma cadeia de entrada w,
produzindo w#w. A ma´quina de Turing para computar f(n) = 2n pode ser construida de
maneira muito similar:
q0 q1 q2 q3 q4
q5qacc
1 → x,D
1 → D
unionsq → #,D
1 → E
# → E
x → 1,D 1 → x,D
1 → D
# → D
unionsq → 1,E
# → 1,E
@ → D
1 → E
Um inteiro n ≥ 0 pode ser representado em base bina´ria como uma cadeia sobre o alfabeto {0, 1}.
Por exemplo, o nu´mero 13 e´ representado pela cadeia 1101. Tambe´m, um inteiro n > 0 pode
ser representado em base una´ria como uma cadeia sobre o alfabeto {1}, na forma 1n. Assim,
o nu´mero 13 e´ representado pela cadeia 1111111111111. Descreva uma ma´quina de Turing que
recebe como entrada a representac¸a˜o bina´ria de um nu´mero n > 0 e gera sua representac¸a˜o una´ria.
Explique o funcionamento da ma´quina claramente. A ma´quina de Turing pode usar mais de uma
fita. Na˜o e´ necessa´rio desenhar um diagrama de estado.
Resposta: Ha´ va´rias formas de construir essa ma´quina de Turing. Por exemplo, podemos
usar uma ma´quina com treˆs fitas. Na primeira fita, recebe a representac¸a˜o bina´ria de n. Na
segunda fita, a ma´quina gera cadeias de 1s, cujo comprimento e´ uma poteˆncia de 2. Na terceira
fita, a ma´quina gera a representac¸a˜o una´ria de n.
M= “Sobre a entrada w:
1. Marque o in´ıcio da primeira fita.
2. Desloque a cabec¸a da primeira fita ate´ o extremo direito de w.
3. Ate´ que atingir o in´ıcio da primeira fita, fac¸a:
4. Se a segunda fita estiver vazia, escreva 1. Se na˜o, duplique a quantidade de
1s nela.
5. Leia o s´ımbolo na primeira fita e desloque a cabec¸a a` esquerda. Se o s´ımbolo
lido for 1, concatene o conteu´do da segunda fita a` direita do conteu´do da
terceira fita.
6. Apague a primeira fita, copie o conteu´do da terceira fita na primeira, e pare.”
Descreva como construir uma ma´quina de Turing que enumere o conjunto de pal´ındromos sobre
{0, 1} em ordem lexicogra´fica. Por exemplo, em um momento dado, a fita da ma´quina de Turing
sera´
##0#1#00#11#000#010#101#111#0000#0110 . . .
Atenc¸a˜o: explique claramente o funcionamento dessa ma´quina de Turing.
Resposta: Podemos usar uma ma´quina com treˆs fitas. Na primeira fita, a ma´quina enumera
os pal´ıdromos. Na segunda, enumera todas as cadeias si ∈ {0, 1}∗, com i = 1, 2, 3, . . ., em
ordem lexicogra´fica (i.e., s1 = ε, s2 = 0, s3 = 1, s4 = 00 etc.), separadas pelo s´ımbolo #. Na
terceira fita, a ma´quina analisa cada cadeia enumerada na segunda fita para determinar se e´
um pal´ındromo ou na˜o.
Em cada etapa i, a ma´quina adiciona a cadeia #si a` direita do conteu´do da fita 2 (vimos em
aula uma ma´quina ENUM que faz isso). Seguidamente, apaga o conteu´do da fita 3, copia
nela si e verifica se a cadeia e´ um pal´ındromo. Para isso, a cabec¸a da ma´quina compara os
s´ımbolos correspondentes a partir de extremo direito e do extremo esquerdo de si (i.e., compara
os s´ımbolos situados a mesma distaˆncia de cada extremo, respectivamente). Se os s´ımbolos
sa˜o iguais, marca eles e continua com o pro´ximo par. Se sa˜o diferentes, enta˜o si na˜o e´ um
pal´ındromo e conclui esta etapa. Se todos os s´ımbolos de si foram marcados, exceto o s´ımbolo
do centro no caso de uma cadeia de comprimento ı´mpar, enta˜o si e´ um pal´ındromo. Nesse
caso, a ma´quina escreve # a` direita do conteu´do da primeira fita e adiciona si.
Desenhe o diagrama de estados de uma ma´quina de Turing que compute a func¸a˜o f(n) = n− 1,
onde n ≥ 1. Suponha que, inicialmente, a fita da ma´quina de Turing conte´m @w, onde w ∈ {0, 1}∗
e´ a representac¸a˜o de n em base bina´ria, e a cabec¸a da ma´quina esta´ sobre o s´ımbolo mais a esquerda
de w. No final da operac¸a˜o, a fita devera´ conter @u, onde u ∈ {0, 1}∗ e´ a representac¸a˜o de n− 1
em base bina´ria, e a cabec¸a da ma´quina devera´ esta´r sobre o s´ımbolo mais a esquerda de u.
Resposta: A ma´quina de Turing que computa f(n) = n − 1 e´ muito similar a` que computa
f(n) = n+ 1, vista em aula.
q0 q1 q2 q3 q4
qaccq5
q6 q7 q8
q9
unionsq → E
¬unionsq → D
1 → 0,E
0 → 1,E
@ → D 1 → D
→ E0 → D
¬@ → E
unionsq → E
1 → D
¬unionsq → D unionsq → E 1 → unionsq,E
¬@ → E
@ → D
→ 1,D
Os estados q0, q1, q2 e q3 fazem a substrac¸a˜o. Os estados restantes eliminam um 0 a` esquerda,
se for o caso.
Suponha que tem uma ma´quina de Turing M que decide a linguagem L. Explique como construir
uma ma´quina de Turing na˜o determin´ıstica N que decida L∗. Atenc¸a˜o: explique claramente o
funcionamento de N .
Resposta:
N= “Sobre a entrada w:
1. Na˜o deterministicamente, corte w em subcadeias de forma que w = w1w2 . . . wn.
Para cada poss´ıvel corte:
2. Rode M sobre wi, com i = 1, 2, . . . , n. Se M aceita cada uma das
subcadeias wi, aceite; se na˜o, rejeite.
Suponha que L1 e L2 sa˜o subconjuntos de Σ
∗ e que M1 e M2 sa˜o ma´quinas de Turing que
reconhecem L1 e L2, respectivamente. Explique como construir uma ma´quina de Turing na˜o
determin´ıstica que reconhec¸a L1L2. Atenc¸a˜o: explique claramente o funcionamento dessa ma´quina
de Turing.
Resposta:
N= “Sobre a entrada w:
1. Na˜o deterministicamente, corte w em duas subcadeias de forma que w = w1w2.
Para cada poss´ıvel corte:
2. Rode M1 sobre w1. Se M1 para e rejeita, rejeite; se aceita, va ao passo 3.
3. Rode M2 sobre w2. Se M2 para e rejeita, rejeite; se aceita, aceite.”