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č. Konkrétně si dokážeme, že nelze algoritmicky rozhodnout, zda se daný algoritmus na svém vstupu zastaví nebo ne.
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.
Petr Hliněný, Fl MU Brno, 2012
1/33
Fl: IB000: Nekonečno a zastaven
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
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, 2012
Fl: IB000: Nekonečno a zastaven
Ukázky kardinalit množin
Uvedená definice kardinality množin „funguje" dobře 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.n
* 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í.
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, 2012
3/33
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.c
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, 2012
4/33
Fl: IB000: Nekonečno a zastaven
Věta. Neexistuje žádné surjektivní zobrazení g : N —> R.
Důkaz (Věty 12.2 sporem): 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:
0(0) = 0.  12 54275 7
g(l) = 0. 41
g{2)= 0. 12
g(3) = 0. 3-1
g(4) = 0. 9-1
3   2 5
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 . ..
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ě, to je spor.
(Až na drobný technický detail s rozvojem ... 9.) □
Petr Hliněný, Fl MU Brno, 2012
5/33
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 a'e ž/ 0 <?(y) z definice K, spor.
- y 0 g(y). To podle definice K znamená, že y G Ä", tj. y G g(y), spor.
Petr Hliněný, Fl MU Brno, 2012
6/33
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).
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, 2012
7/33
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, _/e vidět, že všechny množiny jsou nekonečné a každá je striktně větší než libovolná předchozí, c
Kde však v tomto řazení mohutností bude „množina všech množin"? nNa 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, 2012
8/33
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, 2012
9/33
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, 2012
10/33
Fl: IB000: Nekonečno a zastaven
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, 2012
11/33
Fl: IB000: Nekonečno a zastaven
PO      Pi      P2 P3
V0 Ví
v2 v3
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, 2012
12/33
Fl: IB000: Nekonečno a zastaven