' $' & $ %Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": 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 doka- zováním zprá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) - - . .. . .. . .. . .. . .. ' $' & $ %Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": 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 doka- zováním zprá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) - - . .. . .. . .. . .. . .. 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 IB000 "Úv. Inf.": 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. ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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. Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce. ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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. Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce. 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 N a Z mají stejnou kardinalitu (,,stejně velké ), tzv. spočetně neko- nečné). ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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. Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce. 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 N a Z mají stejnou kardinalitu (,,stejně velké ), tzv. spočetně neko- nečné). Lze snadno ukázat, že i Q je spočetně nekonečná, tj. existuje bijekce f : N Q. ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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. Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce. 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 N a Z mají stejnou kardinalitu (,,stejně velké ), tzv. spočetně neko- nečné). Lze snadno ukázat, že i Q je spočetně nekonečná, tj. existuje bijekce f : N Q. Existují ale i nekonečné množiny, které jsou ,,striktně větší než libovolná spočetná množina (příkladem je R). ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": 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. Množiny A a B jsou ,,stejně velké právě když mezi nimi existuje bijekce. 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 N a Z mají stejnou kardinalitu (,,stejně velké ), tzv. spočetně neko- nečné). Lze snadno ukázat, že i Q je spočetně nekonečná, tj. existuje bijekce f : N Q. Existují ale i nekonečné množiny, které jsou ,,striktně větší než libovolná spočetná množina (příkladem je R). 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 IB000 "Úv. Inf.": Nekonečno a zastavení Věta 11.1. Neexistuje žádné surjektivní (ani bijektivní) zobrazení g : N R. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Nekonečno a zastavení Věta 11.1. Neexistuje žádné surjektivní (ani bijektivní) zobrazení g : N R. 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 . . . ... ... ... ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Nekonečno a zastavení Věta 11.1. Neexistuje žádné surjektivní (ani bijektivní) zobrazení g : N R. 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 . . . ... ... ... 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 . . . ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Nekonečno a zastavení Věta 11.1. Neexistuje žádné surjektivní (ani bijektivní) zobrazení g : N R. 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 . . . ... ... ... 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 . . . 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 IB000 "Úv. Inf.": 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 . ' $' & $ %Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": 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 . 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í. ' $' & $ %Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": 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 . 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í. Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bi- jekce 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. ' $' & $ %Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": 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 . 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í. Neexistenci g dokážeme sporem. Předpokládejme tedy naopak, že existuje bi- jekce 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. Nyní 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 IB000 "Úv. Inf.": 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é. ' $' & $ %Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": 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é. ˇ Technika použitá v důkazech Vět 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 IB000 "Úv. Inf.": 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 = N a Ai+1 = 2Ai pro každé i N, je vidět, že všechny množiny jsou nekonečné a každá je ,,striktně větší než libovolná předchozí. ' $' & $ %Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": 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 = N a Ai+1 = 2Ai pro každé i N, 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í mohutností bude ,,množina všech množin ? ' $' & $ %Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": 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 = N a Ai+1 = 2Ai pro každé i N, 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í mohutností bude ,,množina všech množin ? Takto se koncem 19. století objevil první Cantorův paradox nově vznikající teorie množin. ' $' & $ %Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": 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 = N a Ai+1 = 2Ai pro každé i N, 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í mohutností bude ,,množina všech množin ? Takto se koncem 19. století objevil první Cantorův paradox nově vznikající teorie množin. (Dnešní vysvětlení je jednoduché, prostě ,,množinu všech množin nelze defino- vat, prostě v matematice neexistuje.) 2 Brzy se však ukázalo, že je ještě mnohem hůř. . . ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? Ano. Tj. X X. Pak ale X splňuje X X. ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? Ano. Tj. X X. Pak ale X splňuje X X. Ne. Pak X splňuje vlastnost X X, tedy X je prvkem X, tj., X X. ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? Ano. Tj. X X. Pak ale X splňuje X X. Ne. Pak X splňuje vlastnost X X, tedy X je prvkem X, tj., X X. ˇ 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. ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? Ano. Tj. X X. Pak ale X splňuje X X. Ne. Pak X splňuje vlastnost X X, tedy X je prvkem X, tj., X X. ˇ 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. 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í ? ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": 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}. Platí X X ? Ano. Tj. X X. Pak ale X splňuje X X. Ne. Pak X splňuje vlastnost X X, tedy X je prvkem X, tj., X X. ˇ 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. 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 zapa- matujeme 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 IB000 "Úv. Inf.": 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 iN i, která je spočetně nekonečná. Existuje tedy bijekce f mezi množinou N a množinou všech programů. Pro každé i N označme symbolem Pi program f(i). Pro každý program P tedy existuje j N takové, že P = Pj. ' $' & $ %Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": 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 iN i, která je spočetně nekonečná. Existuje tedy bijekce f mezi množinou N a množinou všech programů. Pro každé i N označme symbolem Pi program f(i). Pro každý program P tedy existuje j N takové, že P = Pj. ˇ 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 N a množinou všech vstupů. Pro každé i N označme symbolem Vi vstup g(i). ' $' & $ %Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": 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 iN i, která je spočetně nekonečná. Existuje tedy bijekce f mezi množinou N a množinou všech programů. Pro každé i N označme symbolem Pi program f(i). Pro každý program P tedy existuje j N takové, že P = Pj. ˇ 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 N a množinou všech vstupů. Pro každé i N označme symbolem Vi vstup g(i). ˇ Předpokládejme, že existuje program Halt, který pro dané i, j N 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 za- stavení nemá algoritmické řešení. ' $' & $ %Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": 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 ; done ' $' & $ %Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": 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 ; done (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: P1 P2 P3 P4 V1 - - V2 - - V3 - - V4 - - ... ... ... ... ... ... 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 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? ­ Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? ­ Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. ­ Ne. Podle kódu Diag pak ale if test neuspěje, a tento program tedy zastaví. ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? ­ Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. ­ 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. 2 Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti. ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Nekonečno a zastavení Podle našeho předpokladu (Diag je program a posloupnost Pi zahrnuje všechny programy) existuje j N takové, že Diag = Pj. Zastaví Diag pro vstup Vj? ­ Ano. Podle kódu Diag pak ale tento program vstoupí do nekonečné smyčky, tedy nezastaví. ­ 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. 2 Otázkami algoritmické (ne)řešitelnosti problémů se zabývá teorie vyčíslitelnosti. 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é.