r
12   Nekonečné množiny, Zastavení algoritmu
Bystrého čtenáře může snadno napadnout myšlenka, proč se vlastně zabýváme dokazováním správnosti algoritmů a programů, když by to přece (snad?) mohl za nás dělat automaticky počítač samotný.
Bohužel to však nejde a je hlavním cílem této lekce ukázat důvody proč.
Stručný přehled lekce
* Nekonečné množiny, jejich „velikost" a Cantorova diagonála.
* „Naivní" množinové paradoxy: Cantorův a Russelův.
* Důkaz algoritmické neřešitelnosti problému zastavení programu.
c
Petr Hliněný, Fl MU Brno, 2015
1/13
Fl: IB000: Nekonečno a zastaven
r
12.1   O nekonečných množinách a kardinalitě
Uvažme problém stanovit, kolik má nekonečná množina prvků. Co nám třeba brání zavést pro velikost nekonečné množiny symbol oo? c
- Ponejvíce závažný fakt, že není „nekonečno" jako „nekonečno" (Věta 12.2)!c
Definice: Množina A]e „nejvýše tak velká" jako množina B, právě když existuje injektivní funkce / : A —> B. c
(O
Množiny A a B jsou „stejně velké" právě když mezi nimi existuje bijekce. c
V případech nekonečných množin pak mluvíme formálně o jejich kardinalitě.
Petr Hliněný, Fl MU Brno, 2015
2/13
Fl: IB000: Nekonečno a zastaven
Ukázky kardinalit množin
Uvedená definice kardinality množin funguje korektně i pro nekonečné množiny:
* Například N a 7L mají stejnou kardinalitu (jsou „stejně velké", tzv. spočetně nekonečné).c
* Lze snadno ukázat, že i Q je spočetně nekonečná, tj. existuje bijekce / : N ->• Q, stejně jako bijekce h : N ->• N2.
'í/2) 6/2 t/3   5/3 6/3 2/4 (3/4) 4/4  5/4 6/4 3/5   4/5   5/5 6/5 t/6) 2/6   3/6  4/6   5/6 6/6
* Existují ale i nekonečné množiny, které jsou „striktně větší" než libovolná spočetná množina (příkladem je R ve Větě 12.2).
* Později dokážeme, že existuje nekonečná posloupnost nekonečných množin, z nichž každá je striktně větší než všechny předchozí.
Petr Hliněný, Fl MU Brno, 2015
Fl: IB000: Nekonečno a zastaven
Zjednodušeně místo bijekce
Pro porovnávání velikostí množin někdy s výhodou využijeme následující přirozené, ale nelehké tvrzení (bez důkazu):
Věta 12.1. Pro libovolné dvě množiny A, B platí, že pokud existuje injekce A —» B a zároveň i injekce B —» A, pak existuje bijekce mezi A a B.
Petr Hliněný, Fl MU Brno, 2015
4/13
Fl: IB000: Nekonečno a zastaven
Cantorova diagonála, aneb kolik je reálných čísel
Věta 12.2. Neexistuje žádné surjektivní zobrazení g : N —> R.
Důsledek 12.3. Neexistuje žádné injektivní(ani bijektivní) zobraz, h : R —> N. Neformálně řečeno, reálných čísel je striktně více než všech přirozených.
Petr Hliněný, Fl MU Brno, 2015
5/13
Fl: IB000: Nekonečno a zastaven
r
Věta. Neexistuje žádné surjektivní zobrazení g : N —> R.
Důkaz (Věty 12.2 sporení): Nechť takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu [0,1). Podle hodnot zobrazení g si takto můžeme „uspořádat" dekadické zápisy všech reálných čísel v intervalu [0,1) po řádcích do tabulky:
Nyní sestrojíme číslo a G [0,1) následovně; jeho i-tá číslice za desetinnou čárkou bude 1, pokud v i-tém řádku tabulky na diagonále není 1, jinak to bude 2. V našem příkladě a = 0.21211 ... c
Kde se naše číslo a v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže a někde musí být.) Konstrukce však ukazuje, že a se od každého čísla v tabulce liší na aspoň jednom desetinném místě, a to je spor.
(Až na drobný technický detail s rozvojem ... 9.) □
9(0) 9(1)
í?(3) 9(4)
0.  42 54275 78325 0. 41 0. 42 0. 3-1 0. 9-1
c
Petr Hliněný, Fl MU Brno, 2015
6/13
Fl: IB000: Nekonečno a zastaven
12.2   „Naivní" množinové paradoxy
Analogickým způsobem k Větě 12.2 lze dokázat následovné zobecnění.
Věta 12.4. Necht M je libovolná množina. Pak existuje injektivní zobrazení / : M —> 2M, ale neexistuje žádné bijektivní zobrazení g : M —> 2M.c
Důkaz: Dokážeme nejprve existenci /. Stačí ale položit f (x) = {x} pro každé x G M. Pak / : M ->• 2M je zjevně injektivní.n
Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bi-jekce g : M —» 2M. Uvažme množinu K C M definovanou takto:
K = {x e M \ x g. g (x)}.
Jelikož g je bijektivní a K G 2M, musí existovat y G M takové, že g (y) = K.n Nyní rozlišíme dvě možnosti:
~~ V £ 9(y)- TJ. y ^ K. Pak ale y 0 g(y) z definice K, což je spor.
~~ V 0 0(2/)■ To podle definice K znamená, že y G Ä", tj. y G g(y), spor.
Petr Hliněný, Fl MU Brno, 2015
7/13
Fl: IB000: Nekonečno a zastaven
Dvě navazující poznámky.
Technika použitá v důkazech Vět 12.2 a 12.4 se nazývá Cantorova diagonální metoda, nebo také zkráceně diagonalizace, c Konstrukci množiny K lze znázornit pomocí následující tabulky:
	b     c d
g(o) <	
9(b)	
9{c)	- v^^^^y ■ ■ ■
g(d)	
Symbol y/ resp. -
do množiny uvedené v záhlaví řádku. Tedy např. d G g{b) a a 0 g{d). i
Z toho, že nekonečna mohou být „různě velká", lze lehce odvodit řadu dalších faktů. V jistém smyslu je např. množina všech problémů větší než množina všech algoritmů (obě množiny jsou nekonečné), a proto nutně existují problémy, které nejsou algoritmicky řešitelné.
Petr Hliněný, Fl MU Brno, 2015
8/13
Fl: IB000: Nekonečno a zastaven
Cantorův paradox
Příklad 12.5. Uvážíme-li nyní nekonečnou posloupnost množin
Au A2, A3, A*, ■ ■ ■
kde A\ = N a Ai+\ = 2Ai pro každé i G N, je vidět, že všechny množiny jsou nekonečné a každá je striktně větší než libovolná předchozí.
Kde však v tomto řazení kardinalit bude „množina všech množin"? Na tuto otázku, jak sami asi cítíte, nelze podat odpověď. Co to však znamená? □
* Takto se koncem 19. století objevil první Cantorův paradox teorie množin.c
* Dnešní moderní vysvětlení paradoxu je jednoduché, prostě „množinu všech množin" nelze definovat, taková v matematice neexistuje.c
Brzy se však ukázalo, že je ještě mnohem hůř. ..
Petr Hliněný, Fl MU Brno, 2015
9/13
Fl: IB000: Nekonečno a zastaven
Russelův paradox
Fakt: Není pravda, že každý soubor prvků lze považovat za množinu.
• Nechť X = {M | M je množina taková, že M 0 M}.   Platí X G X ?c
* Ano. Tj. X G X. Pak ale X splňuje X 0 X.n
* Ne. Pak X splňuje vlastnost X 0 X, tedy X je prvkem X, tj., X G X.c
• Obě možné odpovědi vedou ke sporu. X tedy nelze prohlásit za množinu. Jak je ale něco takového vůbec možné?
Vidíte u Russelova paradoxu podobnost přístupu s Cantorovou diagonalizací? Russelův paradox se objevil začátkem 20. století a jeho „jednoduchost" zasahující úplné základy matematiky (teorie množin) si vynutila hledání seriózního rozřešení a rozvoj formální matematické logiky, c
* Pro ilustraci tohoto paradoxu, slyšeli jste už, že „v malém městečku žije holič, který holí právě ty muže městečka, kteří se sami neholí"? c
* Zmíněné paradoxy naivní teorie množin zatím v tomto kurzu nerozřešíme, ale zapamatujeme si, že většina matematických a informatických disciplín vystačíš „intuitivně bezpečnými" množinami.
Petr Hliněný,  Fl MU Brno, 2015
10/13
Fl: IB000: Nekonečno a zastaven
12.3   Algoritmická neřešitelnost problému zastavení
Fakt: Uvědomme si (velmi neformálně) několik základních myšlenek.
• Program v každém programovacím jazyce je konečná posloupnost složená z konečně mnoha symbolů (písmena, číslice, mezery, speciální znaky, apod.) Nechť E je množina všech těchto symbolů. Množina všech programů je tedy jistě podmnožinou množiny Uíe]N £\ která je spočetně nekonečná. Existuje tedy bijekce / mezi množinou N a množinou všech programů. Pro každé j g N označme symbolem Pj program f(j). Pro každý program P tedy existuje íěN takové, že P = Pj.c
• Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné mnočiny T. Množina všech možných vstupů je tedy spočetně nekonečná a existuje bijekce g mezi množinou N a množinou všech vstupů. Pro každé jeN označme symbolem Vj vstup g(j}z
• Předpokládejme, že existuje program H alt, který pro dané i, j g N zastaví s výstupem ano/ne podle toho, zda Pí pro vstup Vj zastaví, nebo ne.
• Tento předpoklad dále dovedeme ke sporu dokazujícímu, že problém zastavení nemá algoritmické řešení.
Petr Hliněný,  Fl MU Brno, 2015
11/13
Fl: IB000: Nekonečno a zastaven
r
Věta 12.6. Neexistuje program Halt, který by pro vstup (Pí,Vj) správně rozhodl, zda se program Pí zastaví na vstupu Vj.
Důkaz: Sporem uvažme program Diag s následujícím kódem:
input k;
if   iía/t(k,k) = ano   then   while true do ; donee Fungování programu Diag lze znázornit za pomocí následující tabulky:
Symbol ^ resp. — říká, že program uvedený v záhlaví sloupce zastaví resp. nezastaví pro vstup uvedený v záhlavířádku. Program Diag „zneguje" diagonálu této tabulky.
Vq Vi
v2 v3
Petr Hliněný,  Fl MU Brno, 2015
12/13
Fl: IB000: Nekonečno a zastaven
r
PO      Pi      p2 P3
if   ŕ/ažt(k,k) = ano then while true do ; done
fi
Vo Vi
v2 v3
V - - v
v V - v
- v V v
- - v V
Podle našeho předpokladu (Diag je program a posloupnost Pí zahrnuje všechny programy) existuje jeN takové, že Diag = Pj. c
Zastaví Diag pro vstup Vjlc
- Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví.c
- Ne. Podle kódu Diag pak ale if test neuspěje, a tento program tedy zas-
Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti.c
Metoda diagonalizace se také často využívá v teorii složitosti k důkazu toho, že dané dvě složitostní třídy jsou různé.
taví. c
Předpoklad existence programu Halt tedy vede ke sporu, c
□
Petr Hliněný,  Fl MU Brno, 2015
13/13
Fl: IB000: Nekonečno a zastaven