Petr Hliněný, FI MU Brno 1 FI: IB000: Nekonečno a zastavení 11 Nekonečné množiny a zastavení algoritmu11 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 g(a) - - g(b) - - g(c) - - g(d) - - ... ... ... ... ... 2 Stručný přehled lekce * Nekonečné množiny, jejich kardinalita 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ý, FI MU Brno 2 FI: IB000: Nekonečno a zastavení 11.1 O kardinalitě a nekonečných množinách11.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. 2 Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce.2 V případech nekonečných množin místo "velikosti" mluvíme formálně o jejich kardinalitě. Tyto definice kardinality množin ,,fungují dobře i pro nekonečné množiny. Například a mají stejnou kardinalitu (,,stejně velké ), tzv. spočetně neko- nečné).2 Lze snadno ukázat, že i Éje spočetně nekonečná, tj. existuje bijekce f : É.2 Existují ale i nekonečné množiny, které jsou ,,striktně větší než libovolná spočetná množina (příkladem je ).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ý, FI MU Brno 3 FI: IB000: Nekonečno a zastavení Věta 11.1. Neexistuje žádné surjektivní (ani bijektivní) zobrazení g : .2 Důkaz 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: g(0) = 0. 1 5 4 2 7 5 7 8 3 2 5 . . . g(1) = 0. 2 . . . g(2) = 0. 1 . . . g(3) = 0. 3 . . . g(4) = 0. 9 . . . ... ... ... 2 Nyní sestrojíme číslo (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ě = 0.21211 . . .2 Kde se naše číslo v tabulce nachází? (Nezapomeňme, g byla surjektivní, takže tam musí být!) Kostrukce však ukazuje, že 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.) 2 Petr Hliněný, FI MU Brno 4 FI: IB000: Nekonečno a zastavení V obecnosti lze dokonce analogickým způsobem dokázat následovné. Věta 11.2. Buď M libovolná množina. Pak existuje injektivní zobrazení f : M 2M , ale neexistuje žádné bijektivní zobrazení g : M 2M .2 Důkaz: Dokážeme nejprve existenci f. Stačí ale položit f(x) = {x} pro každé x M. Pak f : M 2M je zjevně injektivní.2 Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bijekce g : M 2M . Uvažme množinu K M definovanou takto: K = {x M | x g(x)}. Jelikož g je bijektivní a K 2M , musí existovat x M takové, že g(x) = K. 2Nyní rozlišíme dvě možnosti: ­ x g(x). Tj. x K. Pak ale x g(x) z definice K, spor. ­ x g(x). To podle definice K znamená, že x K, tj. x g(x), spor. 2 Petr Hliněný, FI MU Brno 5 FI: IB000: Nekonečno a zastavení Dvě navazující poznámky. * 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é), proto nutně existují problémy, které nejsou algoritmicky řešitelné. 2 * Technika použitá v důkazech Vět 11.1 a 11.2 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(a) - - g(b) - - g(c) - - g(d) - - ... ... ... ... ... 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(b) a a g(d). Petr Hliněný, FI MU Brno 6 FI: IB000: Nekonečno a zastavení ,,Naivní množinové paradoxy Příklad 11.3. Uvážíme-li nyní nekonečnou posloupnost množin A1, A2, A3, kde A1 = a Ai+1 = 2Ai pro každé i , je vidět, že všechny množiny jsou nekonečné a každá je ,,striktně větší než libovolná předchozí. 2 Kde však v tomto řazení mohutností bude ,,množina všech množin ? 2 Takto se koncem 19. století objevil první Cantorův paradox nově vznikající teorie množin.2 (Dnešní vysvětlení je jednoduché, prostě ,,množinu všech množin nelze definovat, prostě v matematice neexistuje.) 2 Brzy se však ukázalo, že je ještě mnohem hůř. . . Petr Hliněný, FI MU Brno 7 FI: IB000: Nekonečno a zastavení Russelův paradox Fakt: Není pravda, že každý soubor prvků lze považovat za množinu. * X = {M | M je množina taková, že M M}. 2Platí X X ?2 Ano. Tj. X X. Pak ale X splňuje X X.2 Ne. Pak X splňuje vlastnost X X, tedy X je prvkem X, tj., X X.2 * Obě možné odpovědi vedou ke sporu. X tedy nelze prohlásit za množinu. Vidíte zde 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. 2 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í ? 2 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čí s ,,intuitivně bezpečnými množinami. Petr Hliněný, FI MU Brno 8 FI: IB000: Nekonečno a zastavení 11.2 Algoritmická neřešitelnost problému zastavení11.2 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ť je množina všech těchto symbolů. Množina všech programů je tedy jistě podmnožinou množiny i i, která je spočetně nekonečná. Existuje tedy bijekce f mezi množinou a množinou všech programů. Pro každé i označme symbolem Pi program f(i). Pro každý program P tedy existuje j takové, že P = Pj.2 * Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné mnočiny . Množina všech možných vstupů je tedy spočetně nekonečná a existuje bijekce g mezi množinou a množinou všech vstupů. Pro každé i označme symbolem Vi vstup g(i).2 * Předpokládejme, že existuje program Halt, který pro dané i, j zastaví s výstupem ano/ne podle toho, zda Pi 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ý, FI MU Brno 9 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 ; done2 (Program Diag(k) má na rozdíl od Halt jen jeden vstup k, což bude důležité.) Fungování programu Diag lze znázornit za pomocí následující tabulky: P0 P1 P2 P3 V0 - - V1 - - V2 - - V3 - - ... ... ... ... ... ... 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ý, FI MU Brno 10 FI: IB000: Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j takové, že Diag = Pj. 2 Zastaví Diag pro vstup Vj?2 ­ Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví.2 ­ Ne. Podle kódu Diag pak ale if test neuspěje, a tento program tedy za- staví.2 Předpoklad existence programu Halt tedy vede ke sporu. 2 Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti.2 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é.