TIN064 Úvod

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Skutečný úvod k těmto wiki-skriptům je zde, tato stránka by měla sloužit spíš jako takový náhled do problematiky, návod před studiem,... ale nevěděl jsem, jak to nazvat líp.

Některé pojmy, o kterých se píše na této stránce (zvlášť ke konci), budou podrobně (exaktně) vysvětleny v následujících kapitolách. Myslím si ale, že je užitečné mít už předem aspoň nějakou mlhavou představu, ono to pak snadněji do sebe zapadá. Představu o tom, k čemu ta vyčíslitelnost vlastně je, si můžete udělat (samozřejmě krom pravidelného navštěvování přednášek) z Johančiny pohádky první.

Některá fakta mohou připadat některým vyučujícím (nejen vyčíslitelnosti) natolik zřejmá, že je raději ani nezmiňují, a když, tak jen jako poznámku na okraj. Člověk by na ně při učení nakonec taky přišel, ale přesto snad neuškodí, když některá zmíním předem.

Čísla, funkce, programy

$ 0 \in \mathbb{N} $. Číslo = přirozené číslo

Ve vyčíslitelnosti (stejně jako v teorii množin a pár dalších vědách) se jako přirozená čísla označuje množina $ \mathbb{N}=\{0,1,2,...\} $. Je to jednodušší, než vždy psát $ \mathbb{N} \cup \{0\} $. S jinými čísly (celá, reálná, komplexní,...) se ve vyčíslitelnosti nepracuje (pokud ano, tak se zakódují do přirozeného čísla), takže dál v tomto textu se pojmem číslo rozumí vždy přirozené číslo (včetně nuly).

Co to je funkce ve vyčíslitelnosti?

Funkcí se myslí vždy tzv. aritmetická funkce, která k-tici čísel přiřazuje jedno číslo, tedy $ f: \mathbb{N}^k \to \mathbb{N} $. Tato funkce navíc nemusí být totální (česky úplná), tedy může být parciální (česky částečná), což znamená, že nemusí být "všude definovaná". V matematice se zápisem $ f: A \to B $ obvykle myslí, že definiční obor $ f $ je $ A $ (zapisujeme $ dom(f)=A $). Ve vyčíslitelnosti, ale platí $ dom(f) \subseteq A $. Ještě jinými slovy: pro některé k-tice nemusí být hodnota $ f $ definována a tyto k-tice pak nepatří do definičního oboru $ f $.

Funkce lze chápat jako programy a naopak

Funkci $ f: \mathbb{N}^k \to \mathbb{N} $ si můžeme představit jako program, který na vstupu dostane $ k $ čísel a vrátí jedno číslo. Tedy schematicky: 

program_pro_f(x1,...,xk){
  ...
  return(y);
}

Každý konečný matematický objekt (např. celé číslo, slovo nad nějakou abecedou, dvojice čísel,...) lze zakódovat jako jedno (přirozené) číslo (konkrétní metody kódování budou popsány dále). Vezmeme-li si tedy program (který nemá žádné side-efekty, jako že by něco tiskl atd., a jeho návratová hodnota závisí jen na vstupních parametrech), tak ho můžeme chápat jako funkci $ \mathbb{N}^k \to \mathbb{N} $.

Nulární funkce

U programů je celkem běžné, že nemusí mít vstup. U funkcí by tomu odpovídaly nulární funkce, které se občas zavádějí (např. v algebře), aby se nemuselo zvlášť ošetřovat konstanty. Mohli bychom si je zavést i ve vyčíslitelnosti, ale mám pocit, že se to na přednášce tak nedělá, protože se bez nich obejdeme. Nic nám totiž nebrání v tom, abychom si vyrobili funkci, která svůj parametr vůbec nepoužije (funkce je konstantní).

Co znamená, že program či funkce konverguje či diverguje?

Jistě znáte nějaký program, který se pro nějaký vstup zacyklí a nikdy se nezastaví (if (x == 42) while (true) do {}). Pokud se program zacyklí pro všechny vstupy, říkáme, že je to prázdný program, kterému odpovídá prázdná funkce, což jest funkce $ f $ taková, že $ dom(f)=\emptyset $. Aby to znělo učeněji, tak místo program se zacyklí (resp. funkce není definována) říkáme program diverguje (resp. funkce diverguje) a píšeme $ f(x_1,...,x_n)\uparrow $. Obdobně místo program se zastaví (po konečném počtu kroků) (resp. funkce je definována) říkáme, že program konverguje (resp. funkce konverguje) a píšeme $ f(x_1,...,x_n)\downarrow $. Například pro funkci $ f $ jedné proměnné tedy máme $ dom(f)=\{x|f(x)\downarrow\} $.

Co znamená $ \downarrow= $?

Zápis $ f(x)\downarrow=y $ je zkratkou za $ f(x)\!\downarrow \; \And \; f(x)=y $, tedy $ f(x) $ konverguje a rovná se $ y $. Exaktně vzato by stačilo psát $ f(x)=y $, protože z toho už vyplývá, že funkce konverguje. Zápis $ f(x)\downarrow=y $ se ale používá v situacích, kdy nás chce jeho autor upozornit, že to není tak samozřejmé, že $ f(x) $ konverguje. Případně to může znamenat, že se v důkazu nejprve musí dokázat ta konvergence a až poté výsledná hodnota.

Funkce, predikát, množina, relace, problém

Je dobré si uvědomit, že tyto pojmy jsou na sebe jednoduše převeditelné, jde jen o úhel pohledu. V důkazech se obvykle tyto převody ani nezmiňují.

Predikát jako funkce

Predikát k proměnných $ P(x_1,...,x_k) $ je nějaké tvrzení o těchto proměnných, které může být pravdivé či nepravdivé. Např. $ P(x_1,x_2) $="($ x_1 $ je prvočíslo) a ($ x_2 > x_1) $". Ve vyčíslitelnosti budou proměnnými vždy čísla a pravdu reprezentujeme jako 1, nepravdu jako 0. Predikáty lze tedy chápat jako funkce, jejichž obor hodnot je {0,1} (zapisujeme $ rng(f)=\{0,1\} $).

Množina jako predikát

Množinu lze chápat jako soubor prvků, které mají nějakou vlastnost P, tedy množina $ M = \{x | P(x) \mbox{ platí}\} $. Pokud nebude uvedeno jinak, bude v následujícím textu pojem množina znamenat vždy množina (nějakých) přirozených čísel. Každý predikát jedné proměnné odpovídá nějaké množině a naopak. Jelikož už víme, že predikáty odpovídají funkcím, tak nás nepřekvapí, že množiny odpovídají funkcím jedné proměnné s oborem hodnot {0,1}. Takovouto funkci nazýváme charakteristická funkce množiny a pro množinu M píšeme $ C_M: \mathbb{N} \to \{0,1\} $ a $ C_M(x) = \begin{cases} 1 & \mbox{pro }x \in M \\ 0 & \mbox{pro }x \notin M \end{cases} $.

Všimněme si, že charakteristická funkce je z definice totální.

Relace jako predikát

Relace na množinách $ A_1,..., A_n $ je podmnožina jejich kartézského součinu. Ve vyčíslitelnosti jako množiny $ A_i $ bereme (kupodivu opět:-)) podmnožiny $ \mathbb{N} $. Relace na n množinách je v důsledku totéž co predikát n proměnných. Nenechte se tedy zmást, že se občas místo predikátu používá relace. (Zajímavé, že zatímco v teorii množin se odvozuje funkce z relace, zde bereme funkci jako základní pojem a relace převádíme na funkce.)

Problém jako množina

V teorii složitosti se instance problému definuje jako slovo nad abecedou {0,1} (tedy pro nás číslo) a problém Q je pak definován jako úloha rozhodnout, zda daná instance problému patří do jazyka $ L(Q)_Y $, tedy do množiny kladných instancí. Zjednodušeně řečeno: problémy jsou zase jen množiny.

  • Problém je rozhodnutelný (též se říká vyčíslitelný či rekurzivní), jestliže existuje TS, který se zastaví na libovolném vstupu a skončí v přijímacím stavu právě pro ty vstupy, které jsou řešením daného problému. O množině kladných instancí pak říkáme, že je to rekurzivní množina, případně že je efektivně rozhodnutelná (o každém prvku můžeme efektivně zjistit, zda do ní patří, nebo nepatří).
  • Problém je částečně rozhodnutelný (též se říká vyčíslitelně spočetný či rekurzivně spočetný), jestliže existuje TS, který se zastaví (v přijímacím stavu) na vstupech, pro které je odpověď ANO (na vstupech, pro které je odpověď NE, se zastavit nemusí). O množině kladných instancí pak říkáme, že je to rekurzivně spočetná množina - existuje pro ni program, který se na vstupu x zastaví, pokud prvek x patří do té množiny. Dokud se nezastaví, nevíme nic. Příklad ze života: když se hraje hokej, prodloužení, je to nerozhodně, vy to nesledujete a jen slyšíte případný řev zvenku, tak pokud se tento řev ozve, víte, že jsme vyhráli, ale pokud je ticho, nevíte nic. Takže hokejový řev je rekurzivně spočetný.
  • Problém je nerozhodnutelný, jestliže není rozhodnutelný. Existují nerozhodnutelné problémy, které jsou částečně rozhodnutelné (Halting problem), ale existují také problémy, které nejsou ani částečně rozhodnutelné.

ČRF a další trojpísmenné zkratky

Jak jsem již předeslal, exaktní definice ČRF, ORF a spol. se nacházejí v následujících kapitolách, ale přijde mi šikovné, když si člověk napřed udělá nějaký rámcový přehled, případně si nové termíny propojí se znalostmi, které už má z jiných přednášek (hlavně Automaty a gramatiky).

ČRF = částečně rekurzivní funkce

Lze dokázat (viz dále), že ke každému programu (v libovolném prog. jazyce, či abstraktním modelu jakým je např. Turingův stroj – dále jen TS) jde zkonstruovat ekvivalentní ČRF. Slovem ekvivalentní se zde myslí to, že program i funkce dojdou pro libovolný vstup ke stejnému výsledku, délka výpočtu (počet kroků, ať už to znamená cokoli) ovšem může být řádově delší. To je ale ve vyčíslitelnosti běžné: zajímá nás jen co (ne)jde spočítat a jakými prostředky, nikoli, jak dlouho to bude trvat, od toho tu je teorie složitosti. Obecný program se může pro nějaký vstup i zacyklit, tudíž i ČRF nemusí být totální.

Téměř jako synonymum k "částečně rekurzivní"=ČR se používá "rekurzivně spočetné"=RS, každý z těchto dvou přívlastků se ovšem pro zmatení nepřítele (jak jinak než z řad studentstva) tradičně spojuje s jinými podstatnými jmény. O funkci se říká že je to ČRF, kdežto o predikátu, že je to RSP (rekurzivně spočetný predikát), a o množině, že je to RSM (rekurzivně spočetná množina).

Možná už znáte z Automatů a gramatik rekurzivně spočetné jazyky definované jako třídu jazyků přijímaných nějakým TS. Tedy jazyk L je RS, existuje-li TS, jenž se zastaví v koncovém přijímacím stavu právě na všech slovech daného jazyka. Pokud nějaké slovo v daném jazyce není, tak se buď TS zastaví v nekoncovém stavu nebo se zacyklí (tj. nikdy se nezastaví). Chceme-li zjistit, zda nějaké slovo patří do L, pak pustíme TS a čekáme, ale dokud se stroj nezastaví, tak nic nevíme.

TS přijímající L lze jednoduše upravit tak, aby se zastavil právě na slovech z L: pokud by se mohl zastavit v nepřijímacím stavu, tak přidáme instrukce, které výpočet zacyklí. Máme-li ČRF $ f $, která je ekvivalentní s takto upraveným TS, tak platí, že $ L = dom(f) $. Vysvětlení: každému slovu lze přiřadit jeho kód, tedy číslo; $ f $ bude funkce jedné proměnné; $ dom(f) $ je množina kódů slov jazyka L. Množina $ dom(f) $ je RSM.

Z částečně rekurzivních funkcí lze odvodit rekurzivně spočetné množiny a rekurzivně spočetné predikáty.

ORF = obecně rekurzivní funkce

ORF jsou ty ČRF, které jsou totální. Z ORF lze odvodit ORP=Obecně rekurzivní predikáty a (obecně) rekurzivní množiny – u množin se slovo obecně vynechává.

PRF = primitivně rekurzivní funkce

Jak si později ukážeme, PRFce jsou vlastní podmnožinou ORFcí. Jsou to takové hezké funkce, které vždy konvergují. Lze pomocí nich vyjádřit většina známých operací jako např.: sčítání, násobení, negace, mocnění, test na prvočíselnost… Naopak se těžko hledá úkol, který by nezvládly (tím je např. Ackermannova funkce). Zatím naprosto neformálně můžeme říct, že PRF odpovídají programům, které mohou používat jen for-cykly (to jest for i := 1 to x do..., nikoli takové ty céčkovské, co simulují while-cyklus), ale nikoli while-cykly. Programy odpovídající ČRF mohou navíc používat právě onen while-cyklus (který ale může běžet do nekonečna a tak vznikne divergence).

Přehled zkratek a terminologie

funkce predikát množina problém
částečně rekurzivní /
rekurzivně spočetný 		ČRF RSP RSM částečně rozhodnutelný
obecně rekurzivní ORF ORP rekurzivní množina rozhodnutelný
primitivně rekurzivní PRF PRP nezavádí se nezavádí se

Efektivní vyčíslitelnost

Efektivní vyčíslitelnost se definuje jako to, co je vyčíslitelné (řešitelné) pomocí ČRF. Vzhledem k již zmíněné ekvivalenci TS a ČRF (kterou ale dokážeme až později), jsou následující výrazy synonyma:

efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné atd.

Když jsem poprvé slyšel o efektivní vyčíslitelnosti, tak jsem si vzpomněl na různé efektivní algoritmy s $ n\,\log n $ složitostí a podobně. Ne, ne, to je něco kapku jiného. Ve vyčíslitelnosti slovem efektivní myslíme, že to vůbec jde. (Jestli někomu přijde efektivní způsob, kterým pracuje univerzální TS, když pobíhá po pásce sem tam a přenáší čárky... no, já nevím.) Zdrojem tohoto nedorozumění je překlad dvou různých anglických přídavných jmen, efficient a effective, pomocí jednoho českého efektivní.

Citováno z „http://wiki.matfyz.cz/index.php?title=TIN064_Úvod&oldid=21244“