TIN064 Prerekvizity

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

V této části si probereme věci, které asi většinou už znáte, ale je dobré si je připomenout, než se začne s vlastní vyčíslitelností. (Některé následující věci se probírají na přednášce.)

Pro připomenutí

Neformálně:

• Množiny jsou stejně velké (mají stejnou kardinalitu), pokud mezi nimi existuje bijekce.
• Množina je spočetná, má-li stejnou kardinalitu jako $ \mathbb{N} $.
• Není těžké dokázat, že množina $ \mathbb{N} \cup \{a\} $ (přirozená čísla a ještě jeden nový prvek k tomu) je spočetná. Bijekcí na $ \mathbb{N} $ je zobrazení $ f(a)=0\, $ a $ f(x)=x+1 \mbox{ pro }x \in \mathbb{N} $.
• Obdobně snadné je najít bijekci mezi $ \mathbb{Z} $ a $ \mathbb{N} $.
• O něco těžší je dokázat, že i množina $ \mathbb{N} \times \mathbb{N} $ je spočetná. Jde tedy o to, umět zakódovat dvojici čísel jako jedno číslo, tedy najít funkci $ f(a,b)=\langle a,b \rangle $, kde $ \langle a,b \rangle $ značí kód dvojice čísel.

Kdyby stačilo jen najít prosté zobrazení do $ \mathbb{N} $, tak můžeme použít $ f(a,b)=2^a 3^b\! $ (místo 2 a 3 mohou být i jiná prvočísla). Pokud požadujeme zobrazení bijektivní, můžeme použít například Cantorovo diagonální uspořádání.

Cantorovo diagonální uspořádání

$ f(a,b) = \langle a,b \rangle =\frac{(a+b)(a+b+1)}{2} + a $

a\b	0	1	2	3
0	0	1	3	6
1	2	4	7
2	5	8

atd.

Kódování n-tic

Právě jsme si ukázali, že pomocí Cantorova diagonálního uspořádání můžeme zakódovat dvojici čísel do jednoho čísla. Můžeme sestrojit i funkci $ \mathit{l}\! $ (jako left), resp. $ \mathit{r}\! $ (jako right), která dostane kód dvojice a vrátí její levý (resp. pravý) člen. To lze udělat různě chytře (rychle), ale vyčíslitelníkům stačí, že to jde: např. vyzkoušet všechny dvojice čísel menších než zadaný kód – to jsou dva for-cykly plus krát výpočet kódu (k čemuž opět stačí jen for-cykly). Netřeba se namáhat s něčím sofistikovanějším, rychlejším – ve vyčíslitelnosti to vyjde nastejno.

Když už umíme kódovat dvojice, není těžké vymyslet způsob, jak kódovat n-tice:

$ \langle x_1,...,x_{n+1}\rangle_{n+1} = \langle x_1, \langle x_2,...,x_{n+1}\rangle_n \rangle $

(Index n u právé závorky značí kód n-tice. Závorky bez indexu značí kód dvojice, jak jsme si ho zavedli.)

Můžeme si též zavést funkci pro výběr j-tého z n prvků zakódovaných do jednoho čísla. Na příkladech:

$ \mathit{l}(\langle 42,3\rangle) = \mathit{l}(1038) = (\langle 42,3\rangle)_{2,1} = (1038)_{2,1} = 42 $

$ z:=\langle 1,2,3,4,5\rangle_{5} $

$ (z)_{5,4}= 4\! $

Cantorova diagonální metoda

Jestli se vám začíná zdát, že Cantor a diagonála mají něco společného, tak jste na dobré stopě :-). Diagonální metoda je obecný dokazovací postup, který poprvé využil Georg Cantor k důkazu nespočetnosti množiny reálných čísel. My ji zde použijeme k důkazu nespočetnosti potenční množiny přirozených čísel. V různých obměnách se ovšem bude používat celý semestr pro mnoho dalších důkazů.

$ \mathcal{P}(\mathbb{N}) $ je nespočetná.

Důkaz sporem: Předpokládejme, že $ \{A_n\}_{n \in \mathbb{N}} $ je posloupnost všech podmnožin $ \mathbb{N} $. Zkonstruujme množinu $ B=\{n | n \in \mathbb{N} \And n \notin A_n\} $. Platí, že $ B \subseteq \mathbb{N} $ (triv.), ale zároveň vidíme, že pro $ \forall n \in \mathbb{N}: A_n \ne B $ (index $ n $ je totiž obsažen v právě jedné z množin $ B $ a $ A_n $), a tedy $ \{A_n\}_{n \in \mathbb{N}} $ nebyla posloupnost všech podmnožin $ \mathbb{N} $, což je spor s predpokladem, že byla.

Ak by to potreboval niekto vidiet podrobnejsie, tu: [1]

Varianty TS

Z Automatů a gramatik znáte tzv. kanonický Turingův stroj a nejspíš jste se už setkali z různými modifikacemi TS, o kterých lze dokázat, že mají stejnou sílu jako kanonický TS.

Modifikace buďto mohou být omezující (jakoby se "ubírá síla"):

• "neposedný TS": hlava smí jen doleva či doprava, nesmí zůstat na místě
• v každém taktu lze provést jen dvě činnosti
• abeceda se zredukuje na dva symboly (lambda a nelambda) (zvýší se počet stavů)
• ...

Nebo mohou modifikace jakoby "přidávat sílu":

• více pásek, více hlav
• nedeterministický TS (na rozdíl od zásobníkových automatů se nedeterministický TS dá simulovat pomocí deterministického)
• ...

Tato část je neúplná a potřebuje rozšířit. Ještě takové ty kaňky a důkazy... Ale na přednášce se to taky moc nedělalo.

Univerzální TS

Pro připomenutí (namísto definice): Univerzální Turingův stroj U umí simulovat libovolný jiný TS T nad libovolným vstupem V. U dostane na vstupu kód stroje T a vstup V a vrátí stejný výsledek, jako by vrátil T na vsupu V. To můžeme zapsat takto: $ U(k\acute{o}d(T), V) \simeq T(V) $. (Pokud se T na vstupu V zacyklí, musí se zacyklit i U(kód(T),V).)

Kódování

Pokud uvažujeme kanonický TS s jedinou páskou a chceme mu předat na vstup dva parametry, můžeme je oddělit na pásce nějakým speciálním symbolem. (Na přednášce se k tomuto účelu používá hvězdička, tedy U(kód(T),V) je totéž co U(kód(T) * V).)

Druhý technický detail, který musíme vyřešit, je: jak zakódovat stroj T jako slovo nad nějakou abecedou. Abychom si zjednodušili práci, předpokládáme, že stroj T pracuje nad abecedou s pouze dvěma symboly ($ \lambda $ a 1), a jako správní matematici uchylujeme se k tomuto předpokladu BÚNO (viz předchozí část o variantách TS). Podobně předpokládáme, že koncový stav je jen jeden a přechodová funkce je (až na ten jeden koncový stav) úplná.

Mějme stavy $ Q_0,Q_1,...,Q_n $ stroje T, přičemž $ Q_0 $ je onen koncový stav. Přechodovou funkci f stroje T pak můžeme zakódovat jako posloupnost: $ f(Q_1,\lambda),f(Q_1,1), ..., f(Q_n,\lambda),f(Q_n,1) $ (jednotlivé členy této posloupnosti samozřejmě oddělujeme vhodnými symboly). Každý člen posloupnosti je trojice: kód symbolu, který se má zapsat na pásku ($ \lambda $ nebo 1), kód pohybu (doleva, doprava, stát) a kód nového stavu. Kódy stavů můžeme kódovat různě, ale pro popis univerzálního TS je nejjednodušší použít unární kódování: $ Q_j $ se zapíše jako j+1 čárek (to +1 je tam proto, aby i kód stavu $ Q_0 $ měl aspoň jednu čárku, ale to je detail).

Páska univerzálního stroje

Páska UTS pak vypadá následovně (může obsahovat i jiné symboly, než vstupní $ \lambda $ a 1 ze simulovaného stroje, takže má navíc $ Y,\Delta, M,\times $ a možná další):

$ Y[blok1]Y[blok2]\Delta[blok3] \times O_1 \times O_2\times O_3\dots O_m \times $

Kde:

• "blok1" je obsah pásky původního stroje, jen obsah právě čteného pole (nad nímž má simulovaný stroj hlavu) je nahrazen pomocným symbolem M
• "blok2" kóduje aktuální číslo stavu stroje (takže to je příslušný počet čárek)
• "blok3" je jen jedna buňka, v níž je uložen obsah právě čteného pole ($ \lambda $ nebo 1)
• $ O_i $ jsou kódy přechodových funkcí z jednotlivých stavů (pro oba dva znaky na vstupu), tj. $ O_i \equiv f(Q_i,\lambda) f(Q_i,1) $

Jak funguje simulace T

Práce UTS pak sestává z:

1. odsimulování jednoho kroku práce původního stroje
2. test na to, zda blok2 obsahuje koncový stav
3. procedura vyčištění pásky a vydání výsledku

Takže se vždycky odkrokuje jeden stav původního TS a otestuje se, zda se v blok2 neobjevil koncový stav, a pokud ano, spustí se čištění a konec, jinak se pokračuje simulací dalšího kroku.

Krok původního TS se simuluje následovně:

1. najde se relevantní blok $ O_i $ -- stav $ i $ si nelze pamatovat přímo, proto musím z blok2 postupně umazávat čárky a posouvat nějaký speciální symbol "zarážku" doprava
2. zarážka se posune na konkrétní instrukci podle blok3 (čteného znaku)
3. provede se instrukce (po kouskách se nový stav přenese do blok2, mám 6 možností zápisu písmene a pohybu hlavy; při mazání a pohybu se musí dávat pozor na okraje pásky původního stroje -- pokud někde něco chybí či přebývá, celá páska původního stroje se po pásce UTS musí posouvat).

Halting problem

"Lze algoritmicky rozhodnout, zda se Turingův stroj T na vstupu V zastaví, nebo zacyklí?"

Toto je asi nejznámější příklad nerozhodnutelného problému (čímž naznačuji, že odpověď na otázku výše je ne). O mnoha důkazech v teorii vyčíslitelnosti uslyšíte "To je vlastně stejný princip jako halting problem."

Halting problem (HP) lze formulovat různě, například i pro libovolný prog. jazyk (kód(T) pak může být např. zdroják v Pascalu). My se ale budeme držet našich oblíbených TS. Jistě vás už nepřekvapí, že algoritmickou rozhodnutelností budeme rozumět to, zda existuje nějaký TS, který by daný problém řešil (přesněji řečeno rozhodoval, tedy zastavil se po konečném počtu kroků a odpověděl ANO, nebo NE).

V důkazu nerozhodnutelnosti HP se obvykle využívá univerzální Turingův stroj (UTS). Osobně si myslím, že je to spíš matoucí, protože důkaz funguje i bez UTS. Jediné co z UTS využijeme, je fakt, že každý TS (přesněji jeho přechodová funkce) lze zakódovat jako slovo nad nějakou abecedou. To je ale celkem zřejmé: jak jinak bychom asi dostali na vstup stroj T?

Důkaz

Pro spor předpokládejme, že existuje TS HALT takový, že HALT(kód(T),V)=ANO právě tehdy, když se T(V) zastaví, a HALT(kód(T),V)=NE právě tehdy, když se T(V) nezastaví.

Pozn. pro matematické šťouraly: Pokud vynecháme z předpokladů existenci univerzálního TS, je potřeba říct, co je to ta funkce kód. (pokud předpokládáme UTS je fce kód součástí jeho definice) Pro důkaz sporu stačí předpokládat, že existuje TS HALT a k němu (libovolná) funkce kód z množiny všech TS do abecedy užívané TS HALT, taková, že .... a dál již všude stejně

To, že nějaký TS stroj odpoví ANO, můžeme chápat buď tak, že skončí v koncovém stavu $ Q_{ANO} $, nebo že zapíše na pásku slovo ANO (nebo pro jednoduchost jen znak 1 jakožto kód kladné odpovědi) a zastaví se. Tyto varianty jsou na sebe snadno převeditelné, my budeme zde používat tu první.

V právě uvedeném popisu stroje HALT jaksi implicitně předpokládáme, že první parametr bude kódem nějakého stroje T. Možná přemýšlíte nad tím, co má stroj HALT udělat, když jako první parametr dostane něco, co nelze interpretovat jako TS. Něco udělat samozřejmě musí, ale pro náš důkaz je to celkem nezajímavé, protože to nebudeme nikde potřebovat. (Klidně můžeme předpokládat, že odpoví NE.)

Protože jsme jako správní vyčíslitelníci zlomyslní, vyrobíme TS PODRAZ tak, aby $ PODRAZ(V)\downarrow \iff HALT(V,V)=NE $. Co to znamená? Pokud HALT(V,V)=NE, tak se PODRAZ(V) zastaví. Pokud HALT(V,V)=ANO, tak PODRAZ(V) se (uměle) zacyklí. Stroj PODRAZ tedy vyrobíme jen malou úpravou stroje HALT: stav $ Q_{ANO} $ odebereme z koncových stavů a přidáme instrukci, která bude v tomto stavu do nekonečna cyklit.

Pointa důkazu je v tom, rozmyslet si, co by měl udělat HALT(kód(PODRAZ), kód(PODRAZ)). Platí totiž:

$ HALT(k\acute{o}d(PODRAZ), k\acute{o}d(PODRAZ))=ANO \iff $
$ \iff PODRAZ(k\acute{o}d(PODRAZ))\downarrow \iff $
$ \iff HALT(k\acute{o}d(PODRAZ),k\acute{o}d(PODRAZ))=NE $.

A kýžený spor je na světě.$ \Box $

Další nerozhodnutelné problémy (pro ty, kterým se Halting problém nelíbí)

Pokud se vám Halting problém z nějakého důvodu nezamlouvá, nabízí se další, stravitelnější (v obecnosti) nerozhodnutelné problémy.

• Máme slovo a gramatiku. Rozhodnout, zda daná gramatika mohla vygenerovat dané slovo.
• Rozhodnout, zda 2 programy počítají totéž. (Později ukáže Riceova věta)
• Zda je možné danou pevnou sadou dlaždic vydláždit rovinu (neomezený prostor, nikoli konkrétní "koupelnu" s okraji, jako u NP-úplného KACHL problému). Pevná sada dlaždic, od každé libovolně kusů (každou aspoň 1x). (Tiling the plane/Wang's tiling problem)