tin ukol3 (PDF)

´ uc
ˇen´ı technicke
´ v Brne
ˇ
Vysoke
ˇn´ıch technologi´ı
Fakulta informac

Teoretick´a informatika
Tˇret´ı u
´kol

2011

Jan Tr´avn´ıˇcek

1.
Tato u
´loha je ˇreˇsena Turingov´
ym strojem, kter´
y je zobrazen na obr´azku 1, kter´
y si m˚
uˇzeme rozdˇelit na
tˇri samostatn´e ˇc´
asti. Jednotliv´e ˇc´
asti jsou v obr´azku naznaˇceny pˇreruˇsovan´
ymi ˇcarami. V prvn´ı ˇc´asti se
prov´ad´ı pouze kontrola, zda je na vstupn´ı p´asce validn´ı vstup ve tvaru ∆A#B∆ω , kde A, B ∈ {0, 1}+ .
Ve druh´e ˇc´asti je vstup zarovn´
an tak, aby oba operandy byly zobrazeny na stejn´em poˇctu bit˚
u.
T´ımto si zjednoduˇs´ıme n´
asledn´e sˇc´ıt´
an´ı, kter´e m˚
uˇzeme prov´adˇet obecnˇeji a nemus´ıme tuto skuteˇcnost
oˇsetˇrovat pˇri samotn´em sˇc´ıt´
an´ı.
Ve tˇret´ı ˇc´asti je pak jiˇz provedeno pouze samotn´e sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel stejn´e d´elky. V´
ysledek
sˇc´ıt´an´ı je pak uloˇzen na p´
asce dle zad´
an´ı.

R

R

¬0,1

#

R
¬0,1,#

L
}

LΔ

¬0,1

¬0,1,#

R #L

R

}

ΔRΔL

}

ΔLΔωL

}

Δ

ΔRΔSRLΔ0L#RR

#

ΔRΔλL

Δ

}
ΔRΔSRLΔLSRLΔ0
RΔλL
# R R0L L Δ RS
L
Δ
#
0,1
} ω S R L 0,1 } λ S R
L

Δ

L

0 0R S L 0L
Δ R Δ
#
0 λ 1 1R S L 0L
Δ R Δ
#
0 ω 1 λ 0
1 0RΔSRLΔ1L#
0 λ 1
0 1R S L 0L
1 ω
Δ R Δ
#
1 λ 0 0R S L 1L
Δ R Δ
#
1 1R S L 1L
Δ R Δ
#
Obr´
azek 1: Turing˚
uv stroj reprezentuj´ıc´ı sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel.

1

2.
Tˇr´ıdu jazyk˚
u pˇrij´ıman´
ych turingov´
ym strojem oznaˇcme LT S . Tˇr´ıdu jazyk˚
u pˇrij´ıman´
ych dvojz´
asobn´ıkov´
ym automatem oznaˇcme LDA . Jsou-li tyto dvˇe tˇr´ıdy jazyk˚
u ekvivalentn´ı, je tˇreba dok´azat obˇe
inkluze LT S ⊆ LDA a LDA ⊆ LT S .
• Prvn´ı inkluzi LT S ⊆ LDA dok´
aˇzeme algoritmem, kter´
y k turingovu stroji sestroj´ı odpov´ıdaj´ıc´ı
dvojz´asobn´ıkov´
y automat. Idea tohoto algoritmu je pops´ana slovnˇe.
– Zvolme Z0 = #. Bez ujmy na obecnosti m˚
uˇzeme prohl´asit, ˇze # ∈
/ Σ. Symbol # je tedy
dno z´
asobn´ıku.
– Vstup dvojz´
asobn´ıkov´eho automatu odpov´ıd´a ˇretˇezci w, kter´
y odpov´ıd´a ˇretˇezci neblankov´
ych symbol˚
u poˇc´
ateˇcn´ı konfigurace p´asky turingova stroje, kter´a je ve tvaru ∆w∆ω .
– Na prvn´ı z´
asobn´ık vloˇz´ıme symbol ∆. Vrchol prvn´ıho z´asobn´ıku odpov´ıd´a pozici hlavy
simulovan´eho turingova stroje.
– D´ale je tˇreba definovat operace, kter´e umoˇzn
ˇuje turing˚
uv stroj, tedy z´apis, posun doprava
a posun doleva.
– Pˇri posunu doprava je tˇreba rozliˇsovat tˇri moˇzn´e varianty, kter´e mohou nastat. Pokud je
na druh´em z´
asobn´ıku pouze symbol # (dno z´asobn´ıku) a vstup dvojp´askov´eho z´asobn´ıku
obsahuje jeˇstˇe nepr´
azdn´
y ˇretˇezec, pˇreˇcteme symbol z p´asky a uloˇz´ıme jej na vrchol prvn´ıho
z´asobn´ıku. Pokud je na druh´em z´asobn´ıku pouze symbol # a na vstupu automatu je jiˇz
pr´azdn´
y ˇretˇezec, vloˇz´ıme na vrchol prvn´ıho z´asobn´ıku symbol ∆. Pokud je na druh´em
z´asobn´ıku mimo symbol # jeˇstˇe jin´
y symbol, vezmeme symbol z vrcholu druh´eho z´asobn´ıku,
odebereme ho z druh´eho z´
asobn´ıku a uloˇz´ıme ho na vrchol prvn´ıho z´asobn´ıku.
– Pˇri posunu doleva se pˇreˇcte symbol z vrcholu prvn´ıho z´asobn´ıku a pˇresune se na druh´
y
z´asobn´ık. Pokud je na vrcholu prvn´ıho z´asobn´ıku symbol dna z´asobn´ıku #, pˇredstavuje to
situaci, kdy bˇeh odpov´ıdajic´ıho turingova stroje posunul ˇctec´ı hlavu doleva pˇred zaˇc´
atek
p´asky.
– Pˇri z´
apisu znaku na m´ısto ˇctec´ı hlavy (vrchol prvn´ıho z´asobn´ıku) je znak z vrcholu odebr´
an
a nahrazen nov´
ym zpˇet na vrchol prvn´ıho z´asobn´ıku.
– Pˇri simulaci TS pˇri pˇrechodu mezi stavy se znak z prvn´ıho z´asobn´ıku pˇreˇcte a vr´at´ı zpˇet.
– Pˇri ˇr´
adne formalizaci popsan´eho algoritmu pak nen´ı teˇzk´e uk´azat, ˇze v´
ysledn´
y dvojz´
asobn´ıkov´
y automat simuluje turing˚
uv stroj.
• Druhou inkluzi LDA ⊆ LT S dok´
aˇzeme slovn´ım popisem algoritmu simulace dvojz´asobn´ıkov´eho
automatu pomoc´ı turingova stroje.
– Pouˇzijeme tˇr´ıp´
askov´
y turingov´
y stroj, kde na prvn´ı p´asku poloˇzme vstupn´ı ˇretˇezec dvojz´asobn´ıkov´eho automat. Druhou a tˇret´ı p´asku budeme povaˇzovat za dva z´asobn´ıky. Jiˇz
bylo dok´
az´
ano, ˇze v´ıcep´
askov´e turingovy stroje nezvyˇzuj´ı s´ılu a tud´ıˇz jsou ekvivalentn´ı s
jednop´
askov´
ymi turingovy stroji.
– Druhou a tˇret´ı p´
asku, budeme pouˇz´ıvat tak, jak jsme zvykl´ı z pr´ace se z´asobn´ıky. Budeme tedy vˇzdy pracovat pouze s posledn´ım symbolem, kter´
y pˇredstavuje vrchol z´asobn´ıku.
Z´asobn´ıkov´e“ operace jistˇe lze prov´adˇet pomoc´ı turingova stroje.
”
– Pˇri ˇr´
adn´e formalizaci popsan´eho postupu m˚
uˇzeme dok´azat, ˇze dvojz´asobn´ıkov´
y automat
lze simulovat tˇr´ıp´
askov´
ym turingov´
ym strojem, tedy i jednop´askov´
ym turingov´
ym strojem.
• Tˇr´ıdy jazyk˚
u LT S a LDA jsou tedy ekvivalentn´ı, jak bylo dok´azano neform´aln´ım popisem obou
stran inkluze.

2

3.
1. Nerozhodnutelnost
• Redukc´ı z probl´emu zastaveni TS.
• Probl´em zastaven´ı lze charakterizovat jazykem HP = {<M >#<w>|M je TS takov´
y, ˇze
zastav´ı, je-li spuˇstˇen na ˇretˇezci w}.
• Probl´em, zda jazyk dan´eho TS obsahuje alespoˇ
n jedno slovo z jazyka L3 = {ww|w ∈
∗
{a, b} }, lze charakterizovat jazykem P = {<M >|(L(M ) ∩ L3 ) 6= ∅}.
• Sestroj´ıme redukci σ : {0, 1, #}∗ → {a, b}∗ z jazyka HP na jazyk P .
• TS Mσ vyˇc´ıslujic´ı σ pˇriˇrad´ı kaˇzd´emu vstupu x ∈ {0, 1, #}∗ ˇretˇezec <Mx >, kde Mx je TS,
kter´
y na vstupu w ∈ {a, b}∗ pracuje tatko:
(a) Mx smaˇze ˇretˇezec w ze sv´eho vstupn´ı p´asky.
(b) Na vstupn´ı p´
asku zap´ıˇse ˇretˇezec x.
(c) Mx ovˇeˇr´ı, zda x m´
a strukturu x1 #x2 , kde x1 je k´od TS a x2 k´od jeho vstupu. Nem´
a-li
tuto strukturu, odm´ıtne.
(d) Mx odsimuluje na sv´e p´
asce bˇeh TS s k´odem x1 na ˇretˇezci s k´odem x2 . Vede-li simulace
k zastaven´ı, pˇrijme, jinak cykl´ı.
• Mσ lze zˇrejmˇe realizovat jako u
´pln´
y TS – jedn´a se o v´
ypis pˇredpˇripraven´
ych komponent TS
(body a, c, d) a o k´
od TS, tker´
y pˇrep´ıˇse zadan´
y ˇretˇezec x na p´asku (bod b).
• Pro jazyk TS Mx plat´ı:
– L(Mx ) = ∅ ⇔ (L(Mx ) ∩ L3 ) = ∅ ⇔ x nen´ı platnou instanc´ı probl´emu zastaven´ı nebo
pokud x = x1 #x2 a TS s k´odem x1 nezastav´ı na ˇretˇezci s k´odem x2 (x ∈
/ HP ).
– L(Mx ) = {a, b}∗ ⇔ (L(Mx ) ∩ L3 ) 6= ∅ ⇔ x = x1 #x2 a TS s k´odem x1 zastav´ı na ˇretˇezci
s k´
odem x2 ⇔ x ∈ HP .
ˇ asteˇcnou rozhodnutelnost nen´ı ze zad´an´ı tˇreba dokazovat.
2. C´

3

4.
Turingovu stroji M4 odpov´ıd´
a gramatika G4 = ({S, A, B}, {a, b}, P, S), kde P je koneˇcn´a mnoˇzina
pravidel definov´
an´
ych n´
asledovnˇe
P: S −→ a | aA
A −→ bB
B −→ bB | aS
Mˇejme ˇretˇezec w = abbbaabaa, pro kter´
y jistˇe plat´ı, ˇze w ∈ L(M4 ). Bˇeh stroje M4 pro tento ˇretˇezec
po t´e vypad´a n´
asledovnˇe pro poˇc´
ateˇcn´ı konfiguraci p´asky ∆w∆ω .
(0, ∆abbbaabaa∆ω , 1) ` (1, ∆abbbaabaa∆ω , 2) ` (2, ∆abbbaabaa∆ω , 3) `
(3, ∆abbbaabaa∆ω , 4) ` (3, ∆abbbaabaa∆ω , 5) ` (3, ∆abbbaabaa∆ω , 6) `
(1, ∆abbbaabaa∆ω , 7) ` (2, ∆abbbaabaa∆ω , 8) ` (3, ∆abbbaabaa∆ω , 9) `
(1, ∆abbbaabaa∆ω , 10) ` (2, ∆abbbaabaa∆ω , 11) ` (5, ∆abbbaabaa∆ω , 10) `
(6, ∆abbbaaba∆ω , 10) ` (5, ∆abbbaaba∆ω , 9) ` (6, ∆abbbaab∆ω , 9) `
(5, ∆abbbaab∆ω , 8) ` (6, ∆abbbaa∆ω , 8) ` (5, ∆abbbaa∆ω , 7) ` (6, ∆abbba∆ω , 7) `
(5, ∆abbba∆ω , 6) ` (6, ∆abbb∆ω , 6) ` (5, ∆abbb∆ω , 5) ` (6, ∆abb∆ω , 5) `
(5, ∆abb∆ω , 4) ` (6, ∆ab∆ω , 4) ` (5, ∆ab∆ω , 3) ` (6, ∆a∆ω , 3) `
(5, ∆a∆ω , 2) ` (6, ∆∆ω , 2) ` (5, ∆∆ω , 1) ` (7, ∆∆ω , 2) ` (8, ∆Y ∆ω , 2) ` (8, ∆Y ∆ω , 1)
Dan´e slovo w je generov´
ano gramatikou G4 n´asleduj´ıc´ı posloupnost´ı derivac´ı:
S ⇒ aA ⇒ abB ⇒ abbB ⇒ abbbB ⇒ abbbaS ⇒ abbbaaA ⇒ abbbaabB ⇒ abbbaabaA ⇒ abbbaabaa.

4