VŠ z trochu jiného úhlu

[Zz]

Je napríklad problém, u ktorého vieme, že nejde riešiť a nemusíme sa o to snažiť. A to vďaka Turingovým strojom.
Napríklad nejde riešiť napríklad automatické odstrelenie zacykleného programu. Ideálne by bolo, keby sa program po takomto odstrelení znovu načítal do posledného stavu, ktorý predchádzal zacykleniu a program pritom "mal aj inú možnosť ako sa zacykliť" - teda by umožnil pokračovať v práci bez straty neuložených dát.

Psal jsem tady 3x, že v praxi se HP neřeší, tak počtvrté: V praxi se problém HP neřeší, nemáme nekonečnou pásku.

Automatické odstřelení zacykleného programu má dneska vyřešen každý mikrokontrolér za 1 USD a to watchdogem, na to Turinga netřeba. Dokonce máš po resetu od watchdogu zachován obsah RAM, takže se můžeš podívat co se stalo, přijdeš jenom o obsah registrů.
Na vyšší úrovni to takhle lze hravě emulovat, zabití procesu po timeoutu je triviální, vyčtení dat před zabitím je jenom mírný kus práce.

[Reklama]

[Jakub Galgonek]

Psal jsem tady 3x, že v praxi se HP neřeší, tak počtvrté: V praxi se problém HP neřeší, nemáme nekonečnou pásku.

Automatické odstřelení zacykleného programu má dneska vyřešen každý mikrokontrolér za 1 USD a to watchdogem, na to Turinga netřeba.

On HP je trošku něco jiného, než tu píšeš ...

[Zz]

On HP je trošku něco jiného, než tu píšeš ...

To se může stát, Turing mě moc nebere, proto jsem si chtěl nechat od zkušenějších vysvětlit co bez Turinga naimplementovat nejde, ale zatím kde nic tu nic

[Mirek Prýmek]

On HP je trošku něco jiného, než tu píšeš ...

Musíš ale uznat, že Zz má pravdu minimálně v tom, že v praxi HP prostě není potřeba řešit. A pokud by ho nakrásně někdo z nějakých exotických důvodů řešit chtěl, tak pro konkrétní fyzický stroj řešitelný (alespoň teoreticky) je, protože konkrétní fyzický stroj je vždycky FSM - a spadla klec...

[Jakub Galgonek]

To se může stát, Turing mě moc nebere, proto jsem si chtěl nechat od zkušenějších vysvětlit co bez Turinga naimplementovat nejde, ale zatím kde nic tu nic

To slovo problem bych překládal spíše jako úloha. Je to úloha při pohledu na program zjistit, zda se nad daným vstupem zastaví. A lze velmi snadno ukázat, že je algoritmicky nerozhodnutelná. Proto se také všude učí

To, že mám problém, že jsem naprogramoval něco, co mi ne a ne doběhnout je trošku něco jiného :-)

[Reklama]

[Mirek Prýmek]

To slovo problem bych překládal spíše jako úloha. Je to úloha při pohledu na program zjistit, zda se nad daným vstupem zastaví. A lze velmi snadno ukázat, že je algoritmicky nerozhodnutelná. Proto se také všude učí

Ale je to naprosto teoretická úvaha. [vtip]Trochu na způsob "je rozhodnutelné, co se s člověkem stane, když se píchne o roh jednorožce?".[/vtip]

[Jakub Galgonek]

A pokud by ho nakrásně někdo z nějakých exotických důvodů řešit chtěl, tak pro konkrétní fyzický stroj řešitelný (alespoň teoreticky) je

Je řešitelný, jen ne na tom fyzickém stroji

Musíš ale uznat, že Zz má pravdu minimálně v tom, že v praxi HP prostě není potřeba řešit.

V praxi potřebuju dokázat, že to, co jsem napsal, se zastaví. Pokud to dokázat nemohu, tak tomu, co jsem napsal, prostě nerozumím. Takže jasně, tam HP (obecně) fakt neřeším. Problém jsem spíše viděl v tom, že Zz má o těch pojmech jen mlhavou/mylnou představu.

[Zz]

To slovo problem bych překládal spíše jako úloha. Je to úloha při pohledu na program zjistit, zda se nad daným vstupem zastaví. A lze velmi snadno ukázat, že je algoritmicky nerozhodnutelná. Proto se také všude učí

To, že mám problém, že jsem naprogramoval něco, co mi ne a ne doběhnout je trošku něco jiného :-)

Já se nepřu že teorii nerozumím dokonale. Já chci vidět praktický algoritmus nebo program, který naimplementován byl v dnešních počítačích a bez Turinga by to naimplementovat nešlo Pokud ho nemáš, tak tě dále nebudu zdržovat
Filozofické meditace nad nekonečnou páskou jsou mi s prominutím volné.

[Jakub Galgonek]

To slovo problem bych překládal spíše jako úloha. Je to úloha při pohledu na program zjistit, zda se nad daným vstupem zastaví. A lze velmi snadno ukázat, že je algoritmicky nerozhodnutelná. Proto se také všude učí

Ale je to naprosto teoretická úvaha.

Jasně že je, ale je třeba ji nezaměňovat s problémem, že se mi zacyklil program

[Mirek Prýmek]

Je řešitelný, jen ne na tom fyzickém stroji

Není řešitelný na tom stejném stroji, ale je řešitelný na stroji s (řádově) větší pamětí.

Koneckonců, krátce a výstižně je to shrnuto na Wiki citací Minského:

Minsky warns us, however, that machines such as computers with e.g. a million small parts, each with two states, will have at least 21,000,000 possible states:
This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle (Minsky 1967 p. 25):

http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls
- a v tom je právě ta komičnost: vyřešit HP pro reálný počítač je obtížné až nemožné z toho důvodu, že je to příliš složité. Nikoli z toho důvodu, že je dokázáno, že to nejde pro TS.

Čili:
 * teoreticky jsme dokázali, že otázka píchnutí se o jednorožce je nerozhodnutelná
 * prakticky nás ale zajímá píchnutí se o hřebík
 * teoreticky víme, že píchnutí se o hřebík je řešitelné
 * prakticky (víceméně pozorováním) víme, že je to stejně neřešitelné - proměnných je příliš moc

V praxi potřebuju dokázat, že to, co jsem napsal, se zastaví. Pokud to dokázat nemohu, tak tomu, co jsem napsal, prostě nerozumím. Takže jasně, tam HP (obecně) fakt neřeším. Problém jsem spíše viděl v tom, že Zz má o těch pojmech jen mlhavou/mylnou představu.

Ono je daleko tristnější, že mlhavou představu (v jistém smyslu) o tom mají i ti, kdo tvrdí, že znalost TS je potřeba - tady zejména mc, ale trochu možná i JS, protože zjevně nepochopil, co jsem říkal.

[Jakub Galgonek]

Já se nepřu že teorii nerozumím dokonale. Já chci vidět praktický algoritmus nebo program, který naimplementován byl v dnešních počítačích a bez Turinga by to naimplementovat nešlo Pokud ho nemáš, tak tě dále nebudu zdržovat
Filozofické meditace nad nekonečnou páskou jsou mi s prominutím volné.

Nedobře se na to díváš Veverko. Turingův stroj, částečně rekurzivní funkce, random-access machine (RAM) a podobně jsou jen abstrakce. Tyto abstrakce ti umožní relativně snadno vyvozovat nějaké závěry o algoritmech. Klidně by sis HP mohl přeformulovat: Není možné v C++ napsat program, který by pro daná C++ program (a daný vstup) zjistil zda výpočet skončí v reálném čase. No jo, ale kdo by to dokazoval

[Jakub Galgonek]

Je řešitelný, jen ne na tom fyzickém stroji

Není řešitelný na tom stejném stroji, ale je řešitelný na stroji s (řádově) větší pamětí.

To už je skoro jako tvrdit, že HP řešit na TS umíme, stačí si jen pořídit vhodné orákulum. Prostě si jen také odskočíme k lepšímu stroji .

PS: Raději pro ostatní připomenu, že Turingovy stroje s orákulem opravdu existují. Tedy existují jak jen matematická abstrakce může existovat .

[Zz]

Není možné v C++ napsat program, který by pro daná C++ program (a daný vstup) zjistil zda výpočet skončí v reálném čase. No jo, ale kdo by to dokazoval

Fajn, tohle fakt neumím, to přiznávám.
Ovšem už dříve jsem psal, že tento problém se v praxi neřeší, jestliže výpočet neskončí do příštího pondělí, tak letí ze skály.
Tedy v praxi nemám problém zda skončí v reálném čase, ale zda skončí v čase 100 hodin a to si myslím že bych svedl.

[Radek Miček]

To slovo problem bych překládal spíše jako úloha. Je to úloha při pohledu na program zjistit, zda se nad daným vstupem zastaví. A lze velmi snadno ukázat, že je algoritmicky nerozhodnutelná. Proto se také všude učí

To, že mám problém, že jsem naprogramoval něco, co mi ne a ne doběhnout je trošku něco jiného :-)

Já se nepřu že teorii nerozumím dokonale. Já chci vidět praktický algoritmus nebo program, který naimplementován byl v dnešních počítačích a bez Turinga by to naimplementovat nešlo Pokud ho nemáš, tak tě dále nebudu zdržovat
Filozofické meditace nad nekonečnou páskou jsou mi s prominutím volné.

Zkusím jiný příklad. Některé programovací jazyky potřebují, aby všechny funkce byly totální (tj. aby výpočet vždy skončil) - v opačném případě by byl jejich typový systém sporný (tj. k ničemu). Konkrétně např. funkce definovaná f(n) = f(n)+1 je neterminující a odečtením f(n) od obou stran rovnice dostaneme 0 = 1, což je spor s axiomem aritmetiky.

[Mirek Prýmek]

Tyto abstrakce ti umožní relativně snadno vyvozovat nějaké závěry o algoritmech. Klidně by sis HP mohl přeformulovat: Není možné v C++ napsat program, který by pro daná C++ program (a daný vstup) zjistil zda výpočet skončí v reálném čase. No jo, ale kdo by to dokazoval

No ale pozor! Tohle prostě není pravda. Díky TS víme, jaké jsou vlastnosti algoritmu na idealizovaném, neexistujícím a nikdy nezkonstruovatelném HW. Pokud se jedná o vlastnosti algoritmu, napsaném v C++ a spuštěném na libovolném HW, který teď existuje, nebo kdykoli v budoucnu existovat bude, tak pro něj prostě závěry získané pro TS neplatí a nikdy platit nebudou.

Možná by bylo na místě být trochu opatrnější s tím tvrzením o mlhavých představách, každý máme své limity v něčem jiném...

To už je skoro jako tvrdit, že HP řešit na TS umíme, stačí si jen pořídit vhodné orákulum. Prostě si jen také odskočíme k lepšímu stroji .

To taky imho není pravda. Protože (pokud se nepletu), tak HP pro FSM jde teoreticky taky řešit na FSM. Čili na stroji stejné síly a tudíž i na stroji alespoň teoreticky zkonstruovatelném. Zatímco orákulum (obecně) výpočetní sílu TS zvyšuje, čímž z jednorožce dělá jednorožce navíc neviditelného

---------
Pokud bych měl vymyslet nějaké docela praktické opodstatnění TS (kromě toho, že se s tím hezky počítá a nemusíme se zabývat nějakými limity), hledal bych ho u Goedela a argumentoval bych asi tímhle směrem:

Někoho by mohlo napadnout realizovat Hilbertův program tak, že uděláme nekonečně škálovatelný stroj, zadáme do něj základní axiomy a pak ho necháme produkovat platné věty. Budeme kontrolovat, jestli náhodou necyklí (např. negeneruje triviální rozšíření typu "něco na N") - tj. budeme mít zajištěno, že nám dává pořád nová a nová platná fakta. Samozřejmě budou fakta čím dál složitější, takže vždycky jednou za čas mu dojde paměť - v tom případě ji "hot-swap" přidáme. Budeme doufat, že jednou stroj vyprodukuje všechno, co by se nám někdy mohlo hodit.

No a pomocí Goedela/TS se poměrně jednoduše ukáže, že takhle to fungovat nemůže, protože jakmile budeme chtít produkovat na základě čehokoli, co obsahuje alespoň Peanovu aritmetiku, není to otázka velikosti paměti, protože by to nešlo ani s nekonečnou pamětí. Takže Hilbertův program zahodíme a budeme vymýšlet nějaký jiný ptákoviny

(pokud jsem v tomhle udělal nějakou chybu, tak se omlouvám, chtěl jsem spíš naťuknout směr...)