VŠ z trochu jiného úhlu

[j]

V čem přesně má být ten rozpor?

I v praxi je třeba řešit terminaci pro všechny vstupy, tudíž i v praxi se vyskytuje obecný HP.

V praxi jsou vstupy velmi omezene, kuprikladu neznam ucetni program, ktery by zvladal na vstupu cisla vetsi nez 10^99 ... protoze je to v praxi naprosta kravina. Realne zvlada vstupy cisel daleko mensich. Takze resit (teoreticky) co se stane kdyz ... je naprosta <>ina, protoze takova situace nikdy nenastane. Ony se v praxi dokonce neresi ani vstupy, ktere realne nastat muzou, pokud je pravdepodobnost takoveho vstupu dostatecne nizka.

...

Opet resis kokotiny, v praxi je pro me omezujici predevsim mnoztvi $$$ na mem konte, takze at uz budu resit jakykoli problem, musim ho vyresit za $$$ kteryma disponuju => reseni rozhodne nemusi byt dokonaly a schopny se vyporadat s koncem vesmiru, me staci reseni ktery dostatecne splni moje touhy.

Proto v praxi vazne nepotrebuju dokazovat, ze neco dobehne, protoze od toho neceho ocekavam nejaky vystup a nastavim podminku dle ocekavani. Stejne tak ocekavam ze to pobezi nejak dlouho a spotrebuje nejaky mnoztvi pameti, a problem budu resit az mi pamet dojde. Trebas prikoupim, trebas dojdu k tomu, ze je chyba v programu, trebas dojdu k tomu, ze program je az prilis dokonaly, ale porad nepotrebuju nic dokazovat.

BTW: Elektrinu vetsina lidi pouziva, sifrovani muze (a funguje) i bez prvocisel.

[Reklama]

[Rax]

Ak ide len o aplikaciu postupov, tak na to sprav program - mozes ho predavat ako programatora na mojej urovni, ktory nebude robit chyby

To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.

[Mirek Prýmek]

To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.

Spis bych rekl, ze zatim je dostatek lidi, kteri jsou schopni to udelat levneji

[Radek Miček]

realne nikdy nemuze existovat jakykoli stroj/mechanismus/robot/cokoli... co by mohlo nabyvat stale nove a nove stavy. A jelikoz pocet stavu je nejak shora omezeny, tak proste k tehle TEORETICKE neresitelnosti nikdy nedojde.

Ale o to vůbec nejde. Důležité je, že logický systém je bezesporný. Funkce, jenž není totální zavádí do logického systému spor. Všimněte si, že vůbec nezáleží na tom, pro jak velký vstup je funkce nedefinovaná. A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

[Mirek Prýmek]

Ale o to vůbec nejde. Důležité je, že logický systém je bezesporný.

Cili veta "je uplne jedno, o co se jedna, dulezite je ze..." nebyla pochopena.

Lamu hul.

Pokud jste ty a d.k. chteli dokazat, ze je kazdy informatik potrebuje znat Turinga, tak podle me jste dokazali jenom to, ze se Turing na nasich skolach uci tim zpusobem, ze z toho maji studenti jenom zamotanou hlavu a neumeji to aplikovat.

Kazdy at si o tom mysli, co chce.

Howgh.

[Reklama]

[student]

Zaprve to neni pravda. Moznosti kazdeho stroje jsou celkem jasne omezene. Stavovy prostor kazdeho stroje je a vzdy bude omezeny.

Stavovy priestor je v kazdom okamihu niecim obmedzeny, ale priebezne sa moze zvacsovat, kde je prave ten mnou opisany problem.

Cim je (celkovo) obmedzeny stavovy priestor serveru, ktory ked mi napise "no space left on device", tak mu tam za behu pridam dalsi disk alebo vymenim stary maly za novy velky? A ked mi zacne dochadzat miesto aj tak, tak zacnem pouzivat vzdialene ulozisko?

Zadruhe to je hloupy predpoklad, protoze pokud se bavime o skutecne realnych problemech ve skutecne realnych podminkach, tak vzdy mame ramcovou predstavu o narocnosti algoritmu. Spravne to rika Rax: pokud soucet dvou 32bitovych cisel bude trvat deset let, tak nas proste uz vysledek nezajima.

To som uz opisoval ako "bezne programy".

Ak ide len o aplikaciu postupov, tak na to sprav program - mozes ho predavat ako programatora na mojej urovni, ktory nebude robit chyby

To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.

A na co je tam treba vykonny HW? Mozno tam niekde bude odpoved na to, co uz nepovazujem za mechanicke aplikovanie postupov a je na to (aspon momentalne) treba clovek, ktory nad tym musi rozmyslat a moze navrhnut aj lepsie riesenie.

...

Opet resis kokotiny, v praxi je pro me omezujici predevsim mnoztvi $$$ na mem konte, takze at uz budu resit jakykoli problem, musim ho vyresit za $$$ kteryma disponuju => reseni rozhodne nemusi byt dokonaly a schopny se vyporadat s koncem vesmiru, me staci reseni ktery dostatecne splni moje touhy.

Proto v praxi vazne nepotrebuju dokazovat, ze neco dobehne, protoze od toho neceho ocekavam nejaky vystup a nastavim podminku dle ocekavani. Stejne tak ocekavam ze to pobezi nejak dlouho a spotrebuje nejaky mnoztvi pameti, a problem budu resit az mi pamet dojde. Trebas prikoupim, trebas dojdu k tomu, ze je chyba v programu, trebas dojdu k tomu, ze program je az prilis dokonaly, ale porad nepotrebuju nic dokazovat.

Jasne, nastavis podmienku napr. 5GB na kompilaciu Linux kernelu (lebo to by malo stacit) a ono to nezbehne. Nepotrebujes nic dokazovat, ale niekedy "by bolo dobre" vediet, ci sa oplati kupovat novy disk / rychlejsi CPU a to este pred jeho kupou a niekolkymi hodinami kompilacie (ci nie je bug v gcc/inde).

BTW: Elektrinu vetsina lidi pouziva, sifrovani muze (a funguje) i bez prvocisel.

Vsak aj TV sa da pozerat aj pri svieckach ;-).

[Rax]

A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

Nepotřebuji znát chování funkce pro všechny vstupy, protože mám HDD 1 TB tak mi to bohatě stačí pro nějakých 2^2^43 vstupních kombinací. Je zásadní rozdíl mezi "2^2^43" a "všechny".

[Mirek Prýmek]

Stavovy priestor je v kazdom okamihu niecim obmedzeny, ale priebezne sa moze zvacsovat, kde je prave ten mnou opisany problem.

Ale to neni podstata problemu. Podstata problemu je v tom, ze napr. nikdy nebudes potrebovat resit vypocet, ktery ma tolik stavu, kolik je atomu ve vesmiru. Proste nebudes. A jestlize nejaka takova hranice existuje (libovolne jak velka, ale nejaka), tak je HP teoreticky resitelny.

Jako nezlob se na me, ale jestli tohle nechapes, a zaroven argumentujes tim, jak je teoreticka informatika a matematika strasne dulezita, tak si o tom chte nechte musim myslet svoje...

[Rax]

A na co je tam treba vykonny HW? Mozno tam niekde bude odpoved na to, co uz nepovazujem za mechanicke aplikovanie postupov a je na to (aspon momentalne) treba clovek, ktory nad tym musi rozmyslat a moze navrhnut aj lepsie riesenie.

I mechanická aplikace postupů vyžaduje výkonný HW, například řízení automobilu. Při řízení nic nevymýšlíš, stejně tak nic nevymýšlíš při kódování www stránek pro LAMP.

[student]

Ale to neni podstata problemu. Podstata problemu je v tom, ze napr. nikdy nebudes potrebovat resit vypocet, ktery ma tolik stavu, kolik je atomu ve vesmiru. Proste nebudes. A jestlize nejaka takova hranice existuje (libovolne jak velka, ale nejaka), tak je HP teoreticky resitelny.

Skor ... tak je HP teoreticky resitelny pro pocet stavu mensi jak pocet atomu ve vesmiru.

Ale to je podla mna nezmysel - atomov vo vesmire je nieco ako 10^80 ~= 2^265.75. A nejaky vypocet, ktory moze pouzivat 266 bitov (tj. moze mat az 2^266 stavov) zase nie je az taka vzacnost. Niektore jeho vetvy jednoducho nezastavia a nezriedka by sa oplatilo vediet, ci su aj take.

Jako nezlob se na me, ale jestli tohle nechapes, a zaroven argumentujes tim, jak je teoreticka informatika a matematika strasne dulezita, tak si o tom chte nechte musim myslet svoje...

Tak nieco o "strasnej dolezitosti" som AFAIK nikde nepisal. Akurat som sa staval proti tomu, ze je z principu zbytocna a nikdy ju nebude na nic treba (prip. ze ju bude menej treba ako pravo atd - ale tam bola explicitne spomenuta len moja skusenost a skusenosti inych sa mozu lisit).

[Radek Miček]

A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

Nepotřebuji znát chování funkce pro všechny vstupy, protože mám HDD 1 TB tak mi to bohatě stačí pro nějakých 2^2^43 vstupních kombinací. Je zásadní rozdíl mezi "2^2^43" a "všechny".

Když dovolím divergenci, tak mohu dokázat cokoliv (verifikace ztrácí smysl).

[Mirek Prýmek]

Ale to je podla mna nezmysel - atomov vo vesmire je nieco ako 10^80 ~= 2^265.75. A nejaky vypocet, ktory moze pouzivat 266 bitov (tj. moze mat az 2^266 stavov) zase nie je az taka vzacnost. Niektore jeho vetvy jednoducho nezastavia a nezriedka by sa oplatilo vediet, ci su aj take.

Promin, ale ty jsi opravdu tak natvrdlej, nebo si ze me delas srandu? To se jako budeme ted bavit o tom, kolik je atomu ve vesmiru? Promatkuprirodu, jiste ze jsem myslel tolik BITU, kolik je tech atomu. Ale to je jedno, na tom totiz vubec nezalezi...

Prosimte, kdyz te ta teoreticka informatika tak bavi a je tak strasne dulezita, dobre si promysli, proc je HP resitelny pro linear bounded automata. Cim to je? Co je tak zasadne odlisuje od TM?
A proc vlastne problemy zacinaji u counter automata?
A pak si poloz zapeklitou otazku: umi pocitac, ze ktereho prave pises na root, skutecne rozeznavat jazyk na a^{n}b^{n}? Proc? Pokud ne, jak bys ho musel rozsirit, aby to umel?

Samozrejme pokud nechces, tak se nad tim nezamyslej, ale mel bys to udelat, protoze chapat tyhle veci je straaaasne dulezite pro kazdeho ajtaka, aaaaaaano?

Ja si s dovolenim na nejaky cas dam od tohodle tematu pauzu, jinak me fakt jebne.

[student]

Promin, ale ty jsi opravdu tak natvrdlej, nebo si ze me delas srandu? To se jako budeme ted bavit o tom, kolik je atomu ve vesmiru?

Tak v praxi sa castejsie hovori o konkretnych cislach ako o "nejakom pocte" X atomov a podobne. Chcel som sa tomu pripodobnit uz tu ;-).

Promatkuprirodu, jiste ze jsem myslel tolik BITU, kolik je tech atomu. Ale to je jedno, na tom totiz vubec nezalezi...

Nemam kristalovu gulu, aby som mohol tusit, co si myslel. Ak ma nejaku funkcnu nejaky zaryty odporca matematiky, tak nech mi ju prosim poskytne a budeme moct viest aj takuto debatu.

Prosimte, kdyz te ta teoreticka informatika tak bavi a je tak strasne dulezita,

Samozrejme pokud nechces, tak se nad tim nezamyslej, ale mel bys to udelat, protoze chapat tyhle veci je straaaasne dulezite pro kazdeho ajtaka, aaaaaaano?

Odkazujes na nieco, co som nepisal a upozornil som na to aj v prispevku, na ktory reagujes. Tak sa citujem:

Tak nieco o "strasnej dolezitosti" som AFAIK nikde nepisal. Akurat som sa staval proti tomu, ze je z principu zbytocna a nikdy ju nebude na nic treba (prip. ze ju bude menej treba ako pravo atd - ale tam bola explicitne spomenuta len moja skusenost a skusenosti inych sa mozu lisit).

dobre si promysli, proc je HP resitelny pro linear bounded automata. Cim to je? Co je tak zasadne odlisuje od TM?

Pre danu dlzku vstupu mame u LBA len obmedzeny pocet konfiguracii. A kedze mame v HP zadany aj vstup, tak jeho dlzku mozeme pouzit a obmedzit nou pocet stavov.

A pak si poloz zapeklitou otazku: umi pocitac, ze ktereho prave pises na root, skutecne rozeznavat jazyk na a^{n}b^{n}? Proc?

V ziadnom momente nie (v lubovolnom okamihu ma obmedzeny pocet stavov, viz moj prispevok skor - to ma vlastne ale aj Turingov stroj - v lubovolnom momente pouziva len konecne velku cast pasky). Ak mi ale das vstup a pockas si na vystup, tak som schopny* ho rozhodnut - pockam si az dokedy nejaky HW bude schopny udrzat cisla do n (nech je to polovica dlzky vstupu) a potom si ten HW pripojim napr. cez siet a necham ho to spocitat z mojho PC.

* to ma samozrejme nejake predpoklady - vykon a ulozna kapacita HW bude stale rast, co vyzera byt pravda podla Moorovho zakona, ale ktovie, ako to bude za 10, 100 alebo 1000 rokov.

[Mirek Prýmek]

Bezva. Tak to já umím podobně řešit zcela libovolný problém - prostě si počkám, až bude k dispozici patřičném orakulum. A dokud nebude, budu prostě čekat. Výhodou je, že tímto způsobem umím řešit i problémy, které jsou prokazatelně neřešitelné ani teoreticky.

No, tak to bysme měli dneska za F, tak se na to ještě koukněte pane kolego a zkusíme to někdy příště.

[Mirek Prýmek]

P.S. doporučuji úvahu zaměřit směrem k pojmu "stavový prostor". To totiž není to samé jako popsaná část pásky.