MSZ diagonalizace Zdravím, mohl by mi někdo kdo chápe podstatu diagonalizace zkusit lidsky vysvětlit jak můžu s jistotou říct, že ten jazyk L s prvky aij bude VŽDY rozdílný od toho co jsme definovali v matici, minimálně právě na té diagonále?
Pro ten důkaz stačí když vymyslíš slespoň jeden jazyk co se liší. Takže vymyslíš jazyk L, který se liší od každého jazyka právě tím řetězcem co je na diagonále.
Zobrazit všechny odpovědi (5)
Vladislav Závada to je právě to na co se ptám, jak můžu s jistotou říct že se liší...to jako vím že v tom původním jazyku tam ty řetězce na diagonále vždy patří?
oni tam nemusí patřit, když v tabulce ten řetězec k jazyku patří tak v L patřit nebude, a když v tabulce řetězec do jazyka nepatří tak v L patřit bude
Tobě nejde o to, že bys měl vědět, že v tom původním jazyku tam vždy patří. Jde ti o to, že pokud tam patří, tak ty následně řekneš, že nepatří a následně naopak. Tím najdeš věc, která se bude vždy pro každý řetězec lišit ve výsledku právě na diagonále a tím dokážeš, že jsi nemohl předtím vypsat veškeré stroje (či tk nějak)
Díky, je mi to trochu jasnější ale pořád mi to přijde jako dost zvláštní důkaz :D
Tak to jsme dva :D
Dostanes spocetnou mnozinu jazyku a mas za ukol vymyslet novy jazyk, ktery je jiny nez kterykoliv z mnoziny. Protoze kazdy jazyk muze/nemusi obsahovat libovolny retezec ze sigma*, kazdy takovy retezec vyuzijes na to, aby se tvuj novy jazyk lisil, tj. i-ty retezec pouzijes na to aby se tvuj jazyk lisil od i-teho jazyka (i-ty retezec bude patrit --prave-- do jednoho z novy jazyk / i-ty jazyk), a protoze retezcu mas stejny pocet (spocetne nekonecno) jako jazyku, dokazes se novym jazykem odlisit od kazdeho z danych jazyku.
Doporučuji kouknout na Cantorův důkaz – princip důkazu je z toho vidět opravdu dobře https://en.wikipedia.org/wiki/Cantor's_diagonal_argument
Zobrazit všechny odpovědi (1)
Heuréka, z tohodle odkazu jsem to konečně pochopil :D
TIN diagonalizace Diagonalizace po stopadesáté... Srry, za otravování s detailama, ale mám tady příklad, co dělal Dr. Češka na STI a tak nějak pořád nechápu ten moment, kdy se slavnostně prohlásí "C s pruhem nikdy nemůže být hodnotou f(j), protože se i od toho f(j) musí lišit..." nebo něco v tom slovasmyslu... Přijde mi to celkem logické, ale ve smyslu, jak to chápu, se nemůžu zbavit pocitu, že něco podobného vymyslíte vždycky. Třeba vemte bijekci N -> N, (jasně spočetná) kde si na horizontální ose představíte místo číslic desetinných číslice celých čísel... I potom přece najdete nějaké číslo, které se bude lišit od všech na diagonále, ne? A to je divný, ne? Beztak mi něco uniká, budu vděčnej za každej nápad nebo blbuvzdorný vysvětlení. Přikládám ten příklad z STIčka pro ilustraci a rovnou se omlouvám za prasopis...
Nejde tam nahodou o to ze nevis co dat na pozici Xji? Protoze kdyz tam das 1 tak by tam podle Ci mela byt 2 a kdyz tam das 2 tak by tam podle Ci mela byt 1....
Úplně ve zkratce: Přirozená čísla mají dle definice konečnou reprezentaci a jsou definována jako všichni následníci jedničky (n+1, nebo ta naše boží primitivní funkce sigma). Reálná čísla definičně mají nekonečnou reprezentaci. Hlouběji (ale zpochybnitelně, čti nejsem si tím jistý): A právě proto, že diagonalizace nad N vytvoří něco s konečnou reprezentací, Ti to nepřinese nové číslo, co by už nebylo v matici (protože je to logicky následník jiného čísla). Edit: Použití slova "logicky" není úplně na místě, protože nemůžu říct, že by to na mě logicky působilo, lol. Edit 2: (A budu rád, když mě někdo doupřesníte)
Nakonec to je ještě jednodušší. Nemůžu tohle udělat pro N, protože N se vůči sobě vzájemně liší počtem cifer a zapisovat nižší čísla tím, že jim budou předcházet 0 není přípustné (což je imho taky víceméně důsledek toho, že N mají konečnou reprezentaci). Klíčové zde je to, že při práci s reálnými čísly můžu zapsat to číslo 1 ve tvaru 1,000000000000000000000000 ... až do nekonečna počet des. míst Při pokusu s přirozenými čísly se mi tohle nepodaří a není cesta okolo. Bylo by kupříkladu nasnad reverznout zápis čísel tak, že nuly nebudou předcházet ale budou následovat, tzn 21 zapsat jako 1200000... do nekonečna (ale tenhle nekonečný zápis nemohu s přirozenými čísly použít, PROTOŽE NEMAJÍ NEKONEČNÝ ZÁPIS).
EDIT: Pochopeno blbě, otázku radši nečíst... hmmm... Takže jestli to dobře chápu, pes je zakopanej právě v tom vícenásobným počtu reprezentací jednoho čísla... i když se snažím nějak haluz-inteligentně "seřadit" tu posloupnost reálných čísel, řekněme f(1)=0,0001 f(2)=0,0002 f(3)=0,0003... vždycky ke každýmu najdu ještě nějakou reprezentaci (třeba 0,00010), která tam tak nějak není... a toho využívám u C s pruhem... Kdežto u přiroz. čísel prostě řadím 1, 2, 3, ..., 10000, ... a ať se snažím sebevíc, nenajdu žádný C s pruhem, který by se lišilo od všech, protože takové vzniklé číslo už tam je. Jenom nápad, jak je na tom sqrt(2) - má i číslo s nekonečným počtem desetinných míst víc reprezentací?
Zobrazit všechny odpovědi (8)
No, právě, že ne tak docela. Jde o to, že ty přirozený čísla v první řadě už vůbec neseřadíš tak, jak je při diagonalizaci potřeba a proto to nejde.
no podle mě: u přirozených když vezmu nějaký usek, tak ho dokážu spočítat, takže když udělám tu tabulku tak bude prostě malá a nenajdu číslo takové abych to mohl měnit na diagonále, protože se tam nevejde. Ovšem u reálných když vezmu nějaký usek, tak nevím kolik jich tam je ať vezmu libovolně velký usek, takže tam můžu prcnout i to moje nějaké číslo které se bude lišit na diagonále, protože tam je ten nekonečný rozvoj a já pak můžu tvrdit že pro každé číslo mě existuje protičíslo
Pro úplné zamotání hlavy: Princip diagonalizace by fungoval, kdyby bylo možné zapsat všechny N pomocí nekonečného rozvoje. Ale protože to nejde, tak nejde diagonalizovat => lepší nad tím příliš nepřemýšlet a vzít to jako fakt.
no víceméně to je to co jsem napsal ne?:D
ááá, Takže vůbec nemá smysl dělat diagonalizaci u něčeho, co nemá nekonečný počet reprezentací... třeba u přiroz. čísel. Prostě mi měly mi upadnout ruce v okamžiku, kdy jsem napsal do tabulky něco, co nejde roztáhnout do nekonečné délky (kde nejde vyplnit hodnota pro každý z nekonečného počtu sloupců)... Naopak u reálných čísel je to v pohodě - každé číslo můžu roztáhnout do nekonečného zápisu... a třeba u přiloženého příkladu ze slidů máme sloupce označené nekonečným počtem řetězců ze Sigma* a jsem zase schopný vyplnit každou buňku, jestli daný řetězec náleží do jazyka nebo ne... už se začínám chytat? :D
...to, že nemůžu zapsat 21 jako 0021 nebo 000021 atd., protože "přirozená čísla NEMAJÍ NEKONEČNÝ ZÁPIS" asi budu brát prostě jako fakt, o kterým se nediskutuje...
A neni to tak, ze kdyz zapises 0021 je to stejny jako 0000021 a to je 21 a takove cislo uz tam mas? vpodstate nevymyslis nic noveho
Vondra Vomlela Nezapíšeš. Protože budeš-li chtít zapsat 0021 budeš muset začínat na 0001, protože každé další číslo je následník toho prvního. Budeš-li takhle chtít napsat 0000021, pak budeš muset začínat na 0000001 (logicky bys tedy musel začít na přesném počtu N, což jaksi nejde, že jo.