11   Nekonečné množiny a 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.
	a	b      c d
	V	- - v ■■■
g(b)		-          -          y/ ■■■
g(c)	-	v - v ■■■
g(d)		- v v •••
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, 2011
1/12
Fl: IB000: Nekonečno a zastaven
11.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 11.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, 2011
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.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ě 11.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 11.1. Pro libovolné dvě množiny A, B (i nekonečné) 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, 2011
3/12
Fl: IB000: Nekonečno a zastaven
Cantorova diagonála, aneb kolik je reálných čísel
Věta 11.2. Neexistuje žádné surjektivní zobrazení g : N —> R.c
Důsledek 11.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, 2011
4/12
Fl: IB000: Nekonečno a zastaven
Věta. Neexistuje žádné surjektivní zobrazení g : N —> R.
Důkaz (Věty 11.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:
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.. x
Kde se naše číslo a v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže tam a musí být!) Kostrukce 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.) □
9(0) 9(1)
í?(3) 9(4)
0. 0. 0. 0. 0.
1
5427578325 4
1
3
9
c
Petr Hliněný, Fl MU Brno, 2011
5/12
Fl: IB000: Nekonečno a zastaven
11.2   „Naivní" množinové paradoxy
Analogickým způsobem k Větě 11.2 lze dokázat následovné zobecnění.
Věta 11.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, 2011
6/12
Fl: IB000: Nekonečno a zastaven
Dvě navazující poznámky.
• Technika použitá v důkazech Vět 11.2 a 11.4 se nazývá Cantorova diagonální metoda, nebo také zkráceně diagonalizace. Konstrukci množiny K lze znázornit pomocí následující tabulky:
	a	b	c d
g(o)	v	-	- v ■■■
9(b)		—	- v •••
9{c)	-		- v •••
g(d)			v v •••
Symbol ^ resp. — říká, že prvek uvedený v záhlavísloupce patří resp. nepatří 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, 2011
7/12
Fl: IB000: Nekonečno a zastaven
Cantorův paradox
Příklad 11.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"? 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, 2011
8/12
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, 2011
9/12
Fl: IB000: Nekonečno a zastaven
11.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é i G N označme symbolem Pí program f (i). Pro každý program P tedy existuje jeN 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é i G N označme symbolem V vstup g{i)z
• Předpokládejme, že existuje program Halt, 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, 2011
10/12
Fl: IB000: Nekonečno a zastaven
Věta 11.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 ; done Fungování programu Diag lze znázornit za pomocí následující tabulky:
	Po	Pi	P2	p3 ...
Vo	v	-	-	v ■■■
Vi		—	-	v •••
v2	-		—	v •••
				v •••
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.
Petr Hliněný,  Fl MU Brno, 2011
11/12
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, 2011
12/12
Fl: IB000: Nekonečno a zastaven