IB107 Vyčíslitelnost a složitost
opakování, Turingovy stroje a redukce, Postův korespondenční problém*
Jan Strejček
Fakulta informatiky Masarykova univerzita
vyčíslitelnost funkcí
■ funkce f: Nk -> N je vyčíslitelná když
■ funkce f je totálně vyčíslitelná, je-li vyčíslitelná a dom(f)
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
numerace vyčíslitelných funkcí
pro každé k > 0 lze všechny vyčíslitelné funkce typu f(k) . N/c    N -očíslovat" jako
(k)    (k) (k)
tak, aby platily
věta o numeraci
věta o parametrizaci
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
3/26
vyčíslitelné vlastnosti množin
■ množina A c Nk je rekurzivní, je-li její charakteristická funkce Xa • ^k -> N vyčíslitelná, kde
■ množina A c Nk je rekurzivně spočetná (r.e.), pokud
A = dom(f) pro nějakou vyčíslitelnou funkci ř:     -> N
■ problém zastavení /C
■ doplněk problému zastavení (problém nezastavení) K
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
4/26
numerace r.e. množin a uzáverové vlastnosti
■ pro každé k > 0 lze všechny r.e. podmnožiny Nk "očíslovat" jako
l/l/0(/c), w\k\ l/l/2(/c\...
	třída rek.	třída r.e.
	množin	množin
u, n aplikované na relace stejné arity		
doplněk		
kartézský součin x		
projekce		
řez		
vzor při tot. vyčíslitelném zobrazení		
vzor při vyčíslitelném zobrazení		
obraz při (tot.) vyčíslitelném zobrazení		
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
5/26
další vlastnosti r.e. množin
■ věta o projekci
■ 1. Riceova věta
■ 2. a 3. Riceova věta
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém* 6/26
redukce
A<mB
O B je rekurzivní =4> A je rekurzivní
B A není rekurzivní =4> B není rekurzivní
B 6 je rekurzivně spočetná =4> /A je rekurzivně spočetná
□ A není rekurzivně spočetná =4> 6 není rekurzivně
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
7/26
množiny a problémy: přehled terminologie
problém	množina
Má objekt 0 vlastnost V?	A = {(0)\Omá vlastnost V] Q N
je rozhodnutelný	A je rekurzivní, tj. xa j^ totálně vyčíslitelná, ? tj. 3 program rozhodující x e A
je nerozhodnutelný	A není rekurzivní
je částečně rozhodnutelný neboli semirozhodnutelný	A je rekurzivně spočetná, tj. A = dom(f) pro nějakou VF f, tj. 3 program, který zastaví jen na vstupech z a, tj. 3 program, který generuje A
je rozhodnutelný <=^> je částečně rozhodnutelný a jeho doplněk taky	A je rekurzivní <^> A je rekurzivně spočetná a její doplněk taky
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
8/26
Tu ringů v stroj
Definice (Turingův stroj)
(Deterministický) Turingův stroj (Tu ring M ach i ne, TM) je devftice
M = (Q, Z, ľ, >, U, Ô, Cfo, Qacc, fafe
■ Q ye konečná množina, jejíž prvky nazýváme stavy,
■ Z ye konečná množina, tzv vstupní abeceda,
■ r ye konečná množina, tzv pracovní abeceda, icr,
■ > e I" \ Z ye levá koncová značka,
■ u e r \ Z ye symbol označující prázdné políčko,
■ ô : (Q \ {Qacc, Qrey}) x ľ -> Q x ľ x {/_, fí}
ye totální přechodová funkce, m q0 e Q je počáteční stav,
■ Qacc e Q y© akceptující stav,
■ Qrey g Q ye zamítající stav.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
9/26
Tu ringů v stroj
Dále požadujeme, aby pro každé q e Q \ {qacc, q rej} existoval
p e Q takový, že 5(q, >) = (p, >, f?) (tj. nelze sjet hlavou z pásky ani
přepsat >).
Notace: uw = uuuuuu...
Definice (konfigurace Turingova stroje)
Konfigurace Turingova stroje je trojice
(g, z, n) g Q x {yu^ | y g P} x N, taře
■ q ye stóK
■ yuu je obsah pásky,
m n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup i^gF je trojice (g0, >wuUJ, 0). Akceptující konfigurace je každá trojice tvaru (qaCc, z,n). Zamítající konfigurace je každá trojice tvaru (grey, z, n).
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
10/26
krok výpočtu Tu ringová stroje
Definice (krok výpočtu)
Na množině všech konfigurací stroje M definujeme binární relaci
krok výpočtu
M
jako
M
<
(g, z', n + 1) pokud 6(p, zn) = (g, ď, fí) (g, z;, n - 1)    pokud 5{p, zn) = (g, ď, L)
kde zn je n-tý znak z (přičemž z0 je nejlevější znak z) a z1 vznikl ze z nahrazením znaku zn znakem b.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
11/26
výpočet Tu ringová stroje
Definice (výpočet)
Výpočet TM M na vstupu w je maximální (konečná nebo nekonečná) posloupnost konfigurací K0, Kí, K2,..kde K0 je
počáteční konfigurace pro w aK, \— K/+1 pro všechna i > 0
■ stroj M akceptuje slovo w, právě když výpočet M na w je konečný a jeho poslední konfigurace je akceptující
■ stroj M zamítá slovo w, právě když výpočet M na w je konečný a jeho poslední konfigurace je zamítající
■ stroj M pro vstup w cyklí, právě když výpočet M na w je nekonečný
■ jazyk akceptovaný strojem M definujeme jako množinu L(M) = {w g 51* | .M akceptuje 1/1/}
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
12/26
vícepáskový Turingův stroj
Věta
Pro každý vícepáskový Turingův stroj existuje (jednopáskový) Turingův stroj akceptující stejný jazyk.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
13/26
nedeterministický Turingův stroj
Definice 4.8 (nedeterministický Turingův stroj)
Nedeterministický Turingův stroj M je definován stejně jako det. TM s výjimkou přechodové funkce S, která je definována jako totální
funkce ô : (Q\ {QaccQrey}) X l~ 2°^^R\
■ většina pojmů se definuje stejně jako u deterministického TM
■ v definici kroku výpočtu |— píšeme (q, b, R) e 5(p, zn)
namísto 5(p, zn) = (q, ď, f?) a podobně pro (q, ď, L)
■ stroj .M akceptuje slovo w, právě když existuje výpočet M na i/i/, který je konečný a jeho poslední konfigurace je akceptující
Věta 4.9
Pro každý nedeterministický TM existuje deterministický TM akceptující stejný jazyk.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
14/26
Turingovy stroje a třídy jazyků
Věta 4.20
Jazyk L je rekurzivně spočetný neboli re. (tj. generovaný gramatikou typu 0) <=^> L je akceptovaný nějakým Turingovým strojem.
Definice (úplný Turingův stroj, rekurzivní jazyk)
Turingův stroj se nazývá úplný, je-li každý jeho výpočet konečný (akceptující nebo zamítající). Jazyk se nazývá rekurzivní, pokud je akceptovaný nějakým úplným Turingovým strojem.
Terminologie
■ (obecný) TM M akceptuje/rozpoznává/přijímá jazyk L(M)
■ úplný TM M rozhoduje jazyk L(M)
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
15/26
uzáverové vlastnosti rekurzivních a r.e. jazyků
	třída rek.	třída r.e.
	jazyků	jazyků
u, n		
zřetězení, mocniny		
(pozitivní) iterace		
doplněk		
Věta 4.17
Jazyk L je rekurzivní, právě když jsou jazyky La L r.e.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
16/26
kódování a univerzální Turingův stroj
■ každý TM M lze zakódovat do řetězce (M) e {0,1 }*
■ každé slovo w lze zakódovat do řetězce (w) e {0,1 }*
■ dvojice (M, w) lze zakódovat jako {M, w) = (M)#(w)
Věta
Existuje univerzální Turingův stroj U, který dokáže simulovat libovolný zadaný TM na zadaném vstupu w:
U akceptuje (M, w) M akceptuje w
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
17/26
problém zastavení (halting problem)
Definice (problém zastavení)
Problém zastavení je problém rozhodnout, zda daný TM M má na daném slově w nad jeho vstupní abecedou konečný výpočet. Problém ztotožníme s jazykem
H ALT = {{M,w) | M je TM a výpočet M na w je konečný}.
Věta
Problém zastavení je částečně rozhodnutelný.
Věta 5.6
Problém zastavení je nerozhodnutelný.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
18/26
Tu ringový stroje a funkce
■ obsah páskyjednopáskového deterministického Turingova stroje po skončení výpočtu lze vnímat jako jeho výstup
■ pokud stroj M na vstupu w zastaví s obsahem pásky >yuu (kde y nekončí na u), pak y je jeho výstupem značeným M(w)
Definice ((totálně) vyčíslitelná funkce)
Funkce f: Z*    <t>* je vyčíslitelná, pokud existuje TM M, který zastaví právě na vstupech z dom(f) a pro každé slovo w e dom(f) platíM(w) = f(w).
Funkce je totálně vyčíslitelná, pokud je vyčíslitelná a totální
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
19/26
redukce jazyků
Definice 5.7 (m-redukce)
NechíA c z* a B c <t>* /sol/ jazyky. Řekneme, že A se m-redukuje na B, píšeme A<m B, právě když existuje totálně vyčíslitelná funkce f: Z* -> <t>* taková, že
w e A <=^> f(w) e B.
Funkci f nazveme redukcí A na B.
Věta 5.8
Necht A c Z* a B c 0* ysoi/ yazy/cy a/l<m B. O 6 ye rekurzivní =4> /A ye rekurzivní B 6 ye rekurzivně spočetný =4> /A ye rekurzivně spočetný
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
20/26
problém akceptování
Definice (problém akceptování)
Problém akceptování je problém rozhodnout, zda daný TM M akceptuje dané slovo w nad jeho vstupní abecedou. Problém ztotožníme s jazykem
ACC = {(M. w) | M je TM a M akceptuje w}.
Věta 5.3
Problém akceptování je nerozhodnutelný.
Důkaz: HALT <m ACC
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
21/26
nerozhodnutelnost problému akceptování
HALT <m ACC:
HALT = {(M, w) | M je TM a výpočet M na w je konečný} ACC = {{M, w) | M je TM a M akceptuje w}
Platí také ACC <m HALT a tudíž HALT =m ACC.
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
Postův systém
Definice (Postův systém)
Postův systém P nad ebecedou Z je konečna množina dvojic
p={
OL\
a
Pi e E*,1 < / < n}
Řešením systému P je konečná neprázdná posloupnost přirozených čísel /-i, /2,... Á taková, že 1 < /) < n a
OL\A QLj2 . . . OL\k — f3j^       • • • ft\k •
Příklad:
c		ca		a		ab
abc		b	i	ca		a
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
23/26
Postův korespondenční problém (PCP)
Definice (Postův korespondenční problém (PCP))
Postův korespondenční problém (PCP) je problém rozhodnout, zda má Postův systém P nějaké řešení
PCP = {(P) | P je Postův systém, který má nějaké řešení}
Definice (iniciální Postův korespondenční problém (inPCP))
Iniciál ní Postův korespondenční problém (in PCP) je problém rozhodnout, zda má Postův systém P řešení začínající číslem 1.
in PCP = {(P) | P je Postův systém a má řešení začínající číslem 1}
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
24/26
nerozhodnutelnost PCP
PCP není rozhodnutelný.
Důkaz: Postupně ukážeme ACC <m inPCP <m PCP. inPCP <m PCP:
Zkonstruujeme totálně vyčíslitelnou funkci f tak, že f({P)) = (Př), kde P' má řešení <=^> P má řešení začínající 1.
p={
ba		b		b		bab
b	i	bb	i	abb	i	a
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
25/26
nerozhodnutelnost PCP
ACC <m in PCP:
#q0 > w# > (fw# ... # > ... qacc ■ ■ ■ #
IB107 Vyčíslitelnost a složitost: opakování, Turingovy stroje a redukce, Postův korespondenční problém*
26/26