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. Petr Hliněný, Fl MU Brno, 2024 1/17 Fl: IB000: Nekonečno a zastaven 1~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 oc? - Ponejvíce závažný fakt, že není „nekonečno" jako „nekonečno" (Věta 12.2)!c Definice: Množina A je „nejvýše tak velká11 jako množina B, právě když existuje injektivní funkce f : A B. Množiny A a B jsou „stejně velké11 právě když mezi nimi existuje bijekce. Í7) <7\ vy V případech nekonečných množin pak mluvíme formálně o jejich kardinalitě. Petr Hliněný, Fl MU Brno, 2024 2/17 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 Z mají stejnou kardinalitu (jsou „stejně velké", tzv. spočetně nekonečné).n * Lze snadno ukázat, že i (Q je spočetně nekonečná, tj. existuje bijekce / : N Q, stejně jako bijekce h : N N2. 4/4 5/4 6/4 5 j 3/5 4/5 5/5 6/5 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).c * 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, 2024 3/17 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, 2024 4/17 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, 2024 5/17 Fl: IB000: Nekonečno a zastaven ■r 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: Nyní sestrojíme číslo a £ [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, že 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.) □ 5(0 5(1 5(2 5(3 5(4 0. 42 5427578325 0. 41 0. 42 0. 31 0. dl □ □ Petr Hliněný, Fl MU Brno, 2024 6/17 Fl: IB000: Nekonečno a zastaven ■r 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í f : 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 f : M —> 2M je zjevně injektivní.c Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bije kce g : M —> 2M. Uvažme množinu K C M definovanou takto: K = {x G M | x 0 g (x)}. Jelikož g je bijektivní a K G 2M, musí existovat y G M takové, že g (y) = K.c Nyní rozlišíme dvě možnosti: ~ V £ 5 (ž/)- TJ- V ^ K- Pak ale y 0 g (y) z definice K, což je spor. ~ y 0 5(ž/)- To podle definice if znamená, že y G Ír, tj. y G ^(y), spor. Petr Hliněný, Fl MU Brno, 2024 7/17 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. □ Konstrukci množiny K lze znázornit pomocí následující tabulky: b c d g (o) i sr - V ••• 9(P) Ar V — g(d) ■ ■ ■ II ■ ■ Symbol y/ 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, 2024 8/17 Fl: IB000: Nekonečno a zastaven Cantorův paradox Příklad 12.5. Uvážíme-li nyní nekonečnou posloupnost množin AuA2,A3,A4r-- kde A\ — N a Ai+i = 2Ai pro každé ígN, 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.□ Brzy se však ukázalo, že je ještě mnohem hůř... Petr Hliněný, Fl MU Brno, 2024 9/17 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}. nPlatí X G X ?□ * 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. □ * 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í"? * 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, 2024 10/17 Fl: IB000: Nekonečno a zastaven 12.3 Formální popis a „správnost" algoritmu Před samotným závěrem kurzu si položme otázku, co je vlastně algoritmus? Poznámka: Za definici algoritmu je obecně přijímána tzv. Ch u rch-Tu ringová teze tvrdící, že všechny algoritmy lze „simulovat" na Turingově stroji. Jedná se sice o přesnou, ale značně nepraktickou definici. Mimo Tu ringová stroje existují i jiné matematické modely výpočtů, jako třeba stroj RAM, který je abstrakcí skutečného strojového kódu, nebo neprocedurální modely. Konvence 12.6. Zjednodušeně zde algoritmem rozumíme konečnou posloupnost elementárních výpočetních kroků, ve které každý další krok vhodně využívá (neboli závisí na) vstupní údaje či hodnoty vypočtené v předchozích krocích. Tuto závislost přitom pojímáme zcela obecně nejen na operandy, ale i na vykonávané instrukce v krocích. Pro zápis algoritmu a jeho zpřehlednění a zkrácení využíváme řídící konstrukce - podmíněná větvení a cykly. Vidíte, jak blízké si jsou konstruktivní matematické důkazy a algoritmy v našem pojetí? Jedná se nakonec o jeden ze záměrů našeho přístupu... Petr Hliněný, Fl MU Brno, 2024 11/17 Fl: IB000: Nekonečno a zastaven Ukázka algoritmického zápisu Příklad 12.7. Zápis algoritmu pro výpočet průměru daného pole a[] s n prvky. • Inicializujeme sum ^— 0 ; • postupně pro i: = 0,l,2,... ,n-l provedeme * sum ^—sum+a[i] ; • vypíšeme podíl (sum/n) . □ Ve „vyšší úrovni" formálnosti se totéž dá zapsat jako: Algoritmus 12.8. Průměr z daného pole a[] s n prvky. input pole a [] délky n > 1; sum ^— 0; foreach i 0,1,2,...,n-l do sum ^— sum+a[i] ; done res ^— sum/n; output res. Petr Hliněný, Fl MU Brno, 2024 12/17 Fl: IB000: Nekonečno a zastaven Hluběji o „správnosti" a dokazování programů Jak se máme přesvědčit, že daný algoritmus / program počítá „správně"? • Co třeba ladění programů? Jelikož počet možných vstupních hodnot je (v principu) neohraničený, nelze otestovat všechna možná vstupní data.c • Situace je zvláště komplikovaná v případě paralelních, randomizovaných, interaktivních a nekončících programů (operační systémy, systémy řízení provozu apod.). Takové systémy mají nedeterministické chování a opakované experimenty vedou k různým výsledkům. Nelze je tudíž ani rozumně ladit... t • V některých případech je však třeba mít naprostou jistotu, že program funguje tak jak má, případně že splňuje základní bezpečnostní požadavky. * Pro „malé" algoritmy je možné podat přesný matematický důkazn. * Narůstající složitosti programových systémů si pak vynucují vývoj jiných „spolehlivých" formálních verifikačních metod. Mimochodem, co to vlastně znamená „počítat správně"? Petr Hliněný, Fl MU Brno, 2024 13/17 Fl: IB000: Nekonečno a zastaven Ukázka formálního důkazu algoritmu Příklad 12.9. Je dán následující symbolicky zapsaný algoritmus. Dokažte, že jeho výsledkem je „ výměna " vstupních hodnot a,b. Algoritmus 12.10. input a, b; a i- a+b; b i- a-b; a ^— a-b; output a, b . Pro správný formální důkaz si musíme nejprve uvědomit, zeje třeba symbolicky odlišit od sebe proměnné a,b od jejich daných vstupních hodnot, třeba ha,hb. Nyní v krocích algoritmu počítáme hodnoty proměnných: * a = ha, b = hb, * a ^— a + b = ha + h0, b = h0, * a = ha + hb, b <- a - b = ha + hb - hb = ha, □ * a^a-b = ha + hb- ha = h, b = ha, Tímto jsme s důkazem hotovi. Petr Hliněný, FI MU Brno, 2024 14/17 Fl: □ B000: Nekonečno a zastaven 12.4 Algoritmická neřešitelnost problému zastavení Fakt: Uvědomme si znovu (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ť S je množina všech těchto symbolů. Množina všech programuje tedy jistě podmnožinou množiny Uígn ^'» 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 i G N takové, že P = Pi x • Každý možný vstup každého možného programu lze zapsat jako konečnou posloupnost symbolů z konečné množiny I\ 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é j G N označme symbolem Vj vstup g(j^p • 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, 2024 15/17 Fl: IB000: Nekonečno a zastaven Věta 12.11. 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 Halt(k,k) = ano then while true do ; donee Fungování programu Diag lze znázornit za pomocí následující tabulky: p2 p3 ... - v ■■■ \/^\ — v2 v3 ■ ■ ^ Symbol y/ 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, 2024 16/17 Fl: IB000: Nekonečno a zastaven if Halt (k, k) = ano then while true do ; done fi Po Pi P2 p3 ... Vo — — v ■■■ Vi V V — V ■■■ v2 — V V ■■■ Vs V *J ... Podle našeho předpokladu (Diag je program a posloupnost Pí zahrnuje všechny programy) existuje j G N takové, že Diag = Pj. 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 zastaví. □ Předpoklad existence programu Halt tedy vede ke sporu. □ Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti x 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é. Petr Hliněný, Fl MU Brno, 2024 17/17 Fl: IB000: Nekonečno a zastaven