11   Nekonečné množiny a zastavení algoritmu
Bystrého čtenáře může snadno napadnout myšlenka, proc se vlastně zabýváme dokazováním správnosti algoritmů a programů, když by to přece (snad?) mohl za nas delat automaticky počítač samotny.
Bohužel to vsak nejde a je hlavním cílem teto lekce ukazat důvody proč. Konkretne si dokažeme, ze nelze algoritmicky rozhodnout, zda se dany algoritmus na svem vstupu zastaví nebo ne.
	a	b      c      d     • • •
	V	- - v •••
		-  -  v •••
g{c)	-	v -  v •••
9(d)		-  v v •••
Stručný přehled lekčé
* Nekonečné množiny, jejich kardinalita a Cantorova diagonála.
* „Naivní" množinové paradoxy: Cantorův a Russelův.
* Důkaž algoritmicke neřešitelnosti problemu zastavení programu.
Petr Hliněný,  FI MU Brne_IB000: Nekonečno a zastavení
_
11.1   O kardinalitě a nekonečných množinách
Definice: Množina A je „nejvýše tak velká" jako množina B, právě když existuje injektivní funkce f : A — B. c
Množiny A a B jsou „stejne velke" práve když meži nimi existuje bijekce.c
V případech nekoneCných množin místo "velikosti" mluvíme formálne o jejich kardinalitě.
Tyto definice kardinality množin „fungují" dobře i pro nekonecne množiny.
* Napríklad N a 7L mají stejnou kardinalitu („stejne velké"), tžv. spočetně nekonečné).c
* Lže snadno ukažat, že i Q je spocetne nekonečna, tj. existuje bijekce f : N — Q .c
* Existují ale i nekonecne množiny, kterejsou „striktne vetsí" než libovolna spocetna množina (příkladem je r).c
* Poždeji dokažeme, že existuje nekonecní posloupnost nekonecnych množin, ž nichž každí je striktne vetsí než vsechny predchoží.
Petr Hliněný,  FI MU Brno
FI: IB000: Nekonečno a zastavení
Věta 11.1. Neexistuje žádné surjektivní(ani bijektivní) zobrazení g :N — r .c
Důkaz sporem. Necht takové g existuje a pro zjednodušení se omezme jen na funkční hodnoty v intervalu (0,1). Podle hodnot zobrazeni g si takto mUZeme „uspořádat" dekadicke zapisy vsech reainych čísel v intervalu (0,1) po řadcích do tabulky:
7
=   0. 1
g(0)
g(1) = 0.
g(2)= o.
g(3)= 0.
g(4)= 0.
5   7  8   3   2 5
Nyní sestrojíme císlo a € (0,1) následovne; jeho í-tí oslice za desetinnou cárkou bude 1, pokud v í-tem rídku tabulky na diagoníle není 1, jinak to bude 2. V nasem príklade a = 0.21211.. .c
Kde se nase císlo a v tabulce nachází? (Nezapomenme, g byla surjektivní, takze tam a musí byt!) Kostrukce vsak ukazuje, ze a se od kazdeho císla v tabulce lisí na aspon jednom desetinnem míste, to je spor.
(Az na drobný technický detail s rozvojem ... 9.) □
Petr Hlinený,  FI MU Brno _Nekonečno a zastavení
V obecnosti lze dokonce analogickým způsobem dokázat následovné.
Věta 11.2. Bud M libovolná množma. Pak existuje injektivní zobrazení f : M — 2M, ale neexistuje žádné bijektivní zobrazení g : M — 2M .□
Důkaz: DokáZeme nejprve existenci f. StaCí ale poloZit f (x) = {x} pro kaZde x € M. Pak f : M — 2M je zjevne injektivní.n
Neexistenci g dokáZeme sporem. Předpokládejme tedý naopak, Ze existuje bi-jekce g : M — 2M. UvaZme mnoZinů K C M definovanou takto:
JelikoZ g je bijektivní a K € 2M, můsí existovat x € M takove, Ze g(x) = K. □ Nýní roZlisíme dve moZnosti:
- x € g(x). Tj. x € K. Pak ale x € g(x) z definice K, spor.
- x € g(x). To podle definice K znamena, Ze x € K, tj. x € g(x), spor.
K = {x € M | x € g(x)}.
□
Petr Hliněný,  FI MU Brno
FI: IB000: Nekonečno a zastavení
Dvě navazující poznámky.
• Technika pouZitá v dUkazěch Vět 11.1 a 11.2 sě nazývá Cantorova diagonální metoda, něbo takě zkráceně diagonalizace. Konstrukci mnoziny K lzě znázornit pomocí následující tabulky:
	a    b    c d
9ÍP)	v - - v ■■■
9(b)	v - - v •••
9Í.c)	- v - v •••
9{d)	- - v v •••
Symbol y resp. — říká, že prvek uvedený v záhlaví sloupce patří resp. nepatří do množiny uvedene v záhlaví řádku. Tedy napr. d € g(b) a a ^ c
Z toho, že nekoneCna mohou bít „rUzne velkí", lze lehce odvodit řadu dalSích faktu. V jistem smyslu je např. množina vSech „problemm" vetSí než množina vsech algoritmu (obe množiny jsou nekoneCne), proto nutne existují problemy, ktere nejsou algoritmicky resitelne.
etr Hliněný.  FI MU Brno
FI: IB000: Nekonečno a zastavení
„Naivní" množinové paradoxy
Příklad 11.3. Uvážíme-li nyní nekonečnou posloupnost množin
Ai,Ä2,A3, •••
kde Äi = N a Äi+1 = 2Ai pro každé i € N, je vidět, že všechny množiny jsou nekonečne a každá je „striktně větší" než libovolná pžedčhoží c
Kde vsak v tomto řazení mohutností bude „množina vsech množín"? c
Takto se koncem 19. století objevil první CantorUv paradox nove vznikající teorie množin.c
(Dnesní vysvetlení je jednoduche, proste „množinu vsech množin" nelze definovat, proste v matematice neexistuje.) □
Bržy se vsak ukažalo, že je jeste mnohem huř. ..
Petr Hliněný.  FI MU Brno
FI: IB000: Nekonečno a zastavení
Russelův paradox
Fakt: Není pravda, ze každý soubor prvků lze povazovat za množinu.
• X = {M | M je mnozina takova, ze M £ M}.   Platí X e X ?c
* Ano. Tj. X e X. Pak ale X splňuje X £ X.c
* Ne. Pak X splňuje vlastnost X £ X, tedý X je prvkem X, tj., X e X .c
• Obe mozne odpovedi vedou ke sporu. X tedý nelze prohlasit za mnozinu.
Vidíte zde podobnost pňístupu s Cantorovou diagonalizací? Russeluv paradox se objevil zacatkem 20. století a jeho „jednoduchost" zasahující uplne zakladý matematiky (teorie mnozin) si vynutila hledaní seriozního roznesení a rozvoj formalní matematicke logiký.
Pro ilustraci tohoto paradoxu, slýseli jste uz, ze „v malem mestecku zije holic, který holí prave tý muze mestečka, kterí se sami neholí"? c
Zmínene paradoxý naivní teorie mnozin zatím v tomto kurzu nerozresíme, ale zapamatujeme si, ze vetsina matematických a informatických disciplín výstacís „intuitivně bezpecnými" mnozinami.
Petr Hliněný,  FI MU Brn.__IB000: Nekonečno a zastavení
11.2   Algoritmická neřešitelnost problému zastavení
Fakt: Uvedomme si (velmi neformálne) nekolik základních myslenek.
• Program v kazdem programovacím jazyce je koneční posloupnost slození z konecne mnoha symbolu (písmena, císlice, mezery, speciílníznaky, apod.) Necht S je mnozina vsech techto symbolu. Mnozina vsech programu je tedy jistě podmnozinou mnoziny [jíeN £\ kterí je spocetne nekonecní. Existuje tedy bijekce f mezi mnozinou N a mnozinou vsech programu. Pro kazde i € N oznacme symbolem Pí program f (i). Pro kazdy program P tedy existuje j € N takove, ze P = Pj .c
• Kazdy mozný vstup kazdeho mozneho programu lze zapsat jako konecnou posloupnost symbolu z konecne mnociny r. Mnozina vsech mozních vstupu je tedy spocetne nekonecní a existuje bijekce g mezi mnozinou N a mnozinou vsech vstupu. Pro kazde i € N oznacme symbolem Ví vstup g(i c
• Předpoklýdejme, ze existuje program Halt, kterí pro dane i, j € N zastaví s vystupem ano/ne podle toho, zda Pí pro vstup Vj zastaví, nebo ne.
• Tento předpoklad díle dovedeme ke sporu dokazujícímu, ze problem zastavení nemí algoritmicke resení.
Petr Hliněný,  FI MU Brne__FI: IB000: Nekonečno a zastavení
Tvrzení 11.4. Předpoklad existence programu Halt vede ke sporu. Důkaz: Uvažme program Diag s následujícím kódem: input k;
if   Halt (k,k) = ano   then   while true do ; donee
(Program Diag (k) ma na roždíl od Halt jen jeden vstup k, což bude dUležite.) Fungovaní programu Diag lže žnažornit ža pomocí nasledující tabulky:
	Po	Pi	P2	p3 ...
Vq	V	-	-	v ■■■
ví	V	—	-	V •••
v2	-		—	V •••
v3				v •••
Symbol yj resp. — ríka, že program uvedeny v žahlaví sloupce žastaví resp. nežastaví pro vstup uvedeny v žáhlavířádku. Program Diag „žneguje" diagonálu tíeto tabulky.
Petr Hlinený,  FI MU Brno _Nekonečno a zastavení
r.
Podle našeho předpokladu {Diag je program a posloupnost Pí zahrnuje všechny
programy) existuje j € N takove, Ze Diag = Pj. c
Zastaví Diag pro vstup Vj?c
- Ano. Podle kodu Diag pak ale tento program vstoupí do nekoneCne smyCky, tedy nezastaví. c
- Ne. Podle kodu Diag pak ale if test neuspeje, a tento program tedy zas-
Otazkami algoritmické (ne)řesitelnosti problému se zabyva teorie vyčíslitelnosti.c
Metoda diagonalizace se take často vyuzíva v teorii slozitosti k dukazu toho, ze dane dve slozitostní třídy jsou mzne.
taví. c
Přredpoklad existence programu Halt tedy vede ke sporu.
n
Petr Hliněný,  FI MU Brno
FI: IBGGG: Nekonečno a zastavení