{{TIN064 Skripta}}
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 <math>\mathbb{N}</math>.
* Není těžké dokázat, že množina <math>\mathbb{N} \cup \{a\}</math> (přirozená čísla a ještě jeden nový prvek k tomu) je spočetná. Bijekcí na <math>\mathbb{N}</math> je zobrazení <math>f(a)=0\,</math> a <math>f(x)=x+1 \mbox{ pro }x \in \mathbb{N}</math>.
* Obdobně snadné je najít bijekci mezi <math>\mathbb{Z}</math> a <math>\mathbb{N}</math>.
* O něco těžší je dokázat, že i množina <math>\mathbb{N} \times \mathbb{N}</math> je spočetná. Jde tedy o to, umět zakódovat dvojici čísel jako jedno číslo, tedy najít funkci <math>f(a,b)=\langle a,b \rangle</math>, kde <math>\langle a,b \rangle</math> značí kód dvojice čísel.
Kdyby stačilo jen najít prosté zobrazení do <math>\mathbb{N}</math>, tak můžeme použít <math>f(a,b)=2^a 3^b\!</math> (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í ==
<math>f(a,b) = \langle a,b \rangle =\frac{(a+b)(a+b+1)}{2} + a</math>
{| class="wikitable" border="1" cellspacing="0"
! a\b !! width="20" | 0 !! width="20" | 1 !! width="20" | 2 !! width="20" | 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 <math>\mathit{l}\!</math> (jako ''left''), resp. <math>\mathit{r}\!</math> (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:
<math>\langle x_1,...,x_{n+1}\rangle_{n+1} = \langle x_1, \langle x_2,...,x_{n+1}\rangle_n \rangle</math>
(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:
<math>\mathit{l}(\langle 42,3\rangle) = \mathit{l}(1038) = (\langle 42,3\rangle)_{2,1} = (1038)_{2,1} = 42</math>
<math>z:=\langle 1,2,3,4,5\rangle_{5}</math>
<math>(z)_{5,4}= 4\!</math>
== 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 [[wcs:Cantorova diagonální metoda|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ů.
=== <math>\mathcal{P}(\mathbb{N})</math> je nespočetná. ===
Důkaz sporem: Předpokládejme, že <math>\{A_n\}_{n \in \mathbb{N}}</math> je posloupnost '''všech''' podmnožin <math>\mathbb{N}</math>. Zkonstruujme množinu <math>B=\{n|n \notin A_n\}</math>. Platí, že <math>B \subseteq \mathbb{N}</math>, ale zároveň vidíme, že pro <math>\forall n \in \mathbb{N}: A_n \ne B</math>, a tedy <math>\{A_n\}_{n \in \mathbb{N}}</math> nebyla posloupnost všech podmnožin <math>\mathbb{N}</math>, což je spor.
== Varianty TS ==
Z [[Automaty a gramatiky|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
* ...
{{TODO| 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: <math>U(k\acute{o}d(T), V) \simeq T(V)</math>. (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 (<math>\lambda</math> 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 <math>Q_0,Q_1,...,Q_n</math> stroje T, přičemž <math>Q_0</math> je onen koncový stav. Přechodovou funkci f stroje T pak můžeme zakódovat jako posloupnost: <math>f(Q_1,\lambda),f(Q_1,1), ..., f(Q_n,\lambda),f(Q_n,1)</math> (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 (<math>\lambda</math> 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í: <math>Q_j</math> se zapíše jako j+1 čárek (to +1 je tam proto, aby i kód stavu <math>Q_0</math> měl aspoň jednu čárku, ale to je detail).
=== Jak funguje simulace T ===
{{TODO|}}
== Halting problem ==
