VŠ z trochu jiného úhlu

[Mirek Prýmek]

tak pro něj prostě závěry získané pro TS neplatí a nikdy platit nebudou.

Tohle jsem napsal blbě - samozřejmě když máme důkaz, že něco nejde ani na TS, tak to určitě nepůjde ani na FSM. Ale je otázka, jakou reálnou cenu takový závěr má

[Reklama]

[Jakub Galgonek]

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...

Tak pozor, já schválně o spouštění toho programu nic nemluvil!

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.

Jenže ty utíkáš od jednoho nekonečna k jinému. HP pro FSM jde teoreticky taky řešit na FSM, pokud FSM nemá omezený počet stavů.

[Mirek Prýmek]

Tak pozor, já schválně o spouštění toho programu nic nemluvil!

Když řekneš "[Neumím zjistit, jestli] výpočet skončí v reálném čase", tak přesně říkáš co?

Podle mě říkáš tohle: "Neumím zjistit, jestli se program, spuštěný na idealizovaném nezkostruovatelném počítači zastaví" - a já říkám, že vlastnosti běhu programu na takovém typu počítače nás zas až tak moc netrápí - jediné, co nám to může dát, je poznatek, že když to pro jednorožce neplatí, tak to neplatí ani pro hřebík.

V praxi jsou ale daleko potřebnější úvahy nad tím, jestli je něco spočítatelné skutečně, reálně, v nějakém rozumném časovém horizontu - vždyť celá asymetrická kryptografie je založená na tom, že něco sice teoreticky jde, ale prakticky ne...

Jenže ty utíkáš od jednoho nekonečna k jinému. HP pro FSM jde teoreticky taky řešit na FSM, pokud FSM nemá omezený počet stavů.

Ne. (znovu: pokud se nepletu, kdyžtak se rád nechám opravit) Pro program délky N potřebuju "ověřovací mašinu" s pamětí f(N). Je to ale pořád stroj teoreticky skutečně sestrojitelný, ne zcela imaginární jako TS.

[Jakub Galgonek]

Podle mě říkáš tohle: "Neumím zjistit, jestli se program, spuštěný na idealizovaném nezkostruovatelném počítači zastaví"

Jasně, ale nemůžeš mi tam přihodit požadavky a říct, že nemám pravdu . Ta poznámka se týkala jen toho, že TS a jejich programy není jediná abstrakce, ke které se denně modlíme, a není tedy až tak moc smysluplné se ptát, co by bez nich nešlo.

Jenže ty utíkáš od jednoho nekonečna k jinému. HP pro FSM jde teoreticky taky řešit na FSM, pokud FSM nemá omezený počet stavů.

Ne. (znovu: pokud se nepletu, kdyžtak se rád nechám opravit) Pro program délky N potřebuju "ověřovací mašinu" s pamětí f(N). Je to ale pořád stroj teoreticky skutečně sestrojitelný, ne zcela imaginární jako TS.

A až dojdeš na fyzické limity, tak to zase budeš mít pouze teoreticky

[Mirek Prýmek]

Jasně, ale nemůžeš mi tam přihodit požadavky a říct, že nemám pravdu . Ta poznámka se týkala jen toho, že TS a jejich programy není jediná abstrakce, ke které se denně modlíme, a není tedy až tak moc smysluplné se ptát, co by bez nich nešlo.

tak to asi nechápu, protože nevím, jaké požadavky jsem tam přihodil.

Ale to je jedno, u6 toho nechme a pojďme dělat něco rozumnějšího, než dumat nad jednorožci, ne?

A až dojdeš na fyzické limity, tak to zase budeš mít pouze teoreticky

tak na tom se shodneme - jediné, co ve finále rozhoduje, je, jak se to chová prakticky, nezávisle na tom, jestli to jde teoreticky

[Reklama]

[Jakub Galgonek]

tak to asi nechápu, protože nevím, jaké požadavky jsem tam přihodil.

Začal jsi mluvit o reálné sestrojitelnosti HW

Ale to je jedno, u6 toho nechme a pojďme dělat něco rozumnějšího, než dumat nad jednorožci, ne?

Asi spíše půjdu hledat zlaté kapradí ...

[Mirek Prýmek]

Asi spíše půjdu hledat zlaté kapradí ...

Tak aspoň řeš jeho folding, ať moc nevypadneš z oboru

[Zz]

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.

Že to potřebuješ chápu, jenže mě zajímá implementace
Někdo tady měl spoustu krásných teoretických nápadů ohledně Haskelu a pak se zjistilo, že v praxi je tam obyčejný stack overflow.

[JS]

Já spíš vidím problém v tom, že ty prostě neposloucháš, co říkám. "Nahradit analýzu TS analýzou KA" jsem nikdy vůbec neřekl. Jenom jsem mc. upozornil, že TS je jenom čistě teoretický koncept, který nikdy nebude reálně existovat - člověk nikdy nesestrojí jakýkoli stroj výpočetní síly TS.

To neni tak docela pravda. Ty se na to divas spatne. TS neni nerealny. Vety o TS jsou tvrzenim o mnozinach algoritmu (dalo by se rict o mnozinach KA) ktere jsou nejak parametrizovatelne prirozenymi cisly. V tomto smyslu jsou uzitecne, protoze to byvaji ty nejjednodussi algoritmy.

Mozna bychom mohli resit HP pro KA (lepe nez hrubou silou). Ale pak bychom museli pro kazdou velikost KA pridat neco noveho. Neexistuje reseni, ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA.

Mimochodem, jak KA tak TS muzeme brat jako stavove automaty na nekonecne pasce, ale s tim rozdilem, ze KA muze posouvat pasku jen jednim smerem, kdezto TS obema smery. Takze to neni tak, ze nikdo nemuze sestrojit TS.

[JS]

Že to potřebuješ chápu, jenže mě zajímá implementace
Někdo tady měl spoustu krásných teoretických nápadů ohledně Haskelu a pak se zjistilo, že v praxi je tam obyčejný stack overflow.

Problem je, ze to preteceni zasobniku nemusi nastat, aby se to nezastavilo (v rozumne dobe, treba do miliardy let, do ktere bude znicena slunecni soustava). Stejne tak muze nastat, protoze dana uloha vyzaduje zasobnik vetsi. Pritom nedokazeme obecne rict, ktera z tech dvou variant nastala.

[Zz]

Problem je, ze to preteceni zasobniku nemusi nastat, aby se to nezastavilo (v rozumne dobe, treba do miliardy let, do ktere bude znicena slunecni soustava). Stejne tak muze nastat, protoze dana uloha vyzaduje zasobnik vetsi. Pritom nedokazeme obecne rict, ktera z tech dvou variant nastala.

Mám tomu rozumět tak, že nevíš jak je implementován kompilátor tvého oblíbeného jazyka ? Zda tam je nabušená turingova mašina, nebo záležitosti z pekelné praxe jako stack overflow nebo timeout exceed ?

[Mirek Prýmek]

To neni tak docela pravda. Ty se na to divas spatne. TS neni nerealny. Vety o TS jsou tvrzenim o mnozinach algoritmu (dalo by se rict o mnozinach KA) ktere jsou nejak parametrizovatelne prirozenymi cisly.

To je to samé, co jsem psal Kubovi - není to přece tvrzení o algoritmech jako takových, ale o algoritmech spuštěných na TS.

To bych taky mohl říct, že mám imaginární Prýmkův stroj, který je definovaný tím, že instrukce spouští ne popořadě, ale podle Božského pravidla - a pak bych nějak třídil algoritmy podle toho, jaké vlastnosti jejich běh na PS bude mít. Takový stroj prostě nikdy nebudeme mít, takže musíme taky přemýšlet pořádně nad tím, k čemu jsou nám dobré závěry, které platí pro něj.

Neexistuje reseni, ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA.

Dá se to dokázat? Přijde mi to totiž trochu divné, vzhledem k tomu, že KA má jasně daný počet stavů a tímpádem i maximální počet možných přechodů...

Takze to neni tak, ze nikdo nemuze sestrojit TS.

Vyžaduje TS nekonečnou pásku nebo ne? Je možné nekonečnou pásku sestrojit?

[Mirek Prýmek]

Mám tomu rozumět tak, že nevíš jak je implementován kompilátor tvého oblíbeného jazyka ? Zda tam je nabušená turingova mašina, nebo záležitosti z pekelné praxe jako stack overflow nebo timeout exceed ?

JS má pravdu - pokud mám obecný algoritmus a zhavaruje mi při stacku délky 1MB, tak mám dvě možnosti:
1. když přidám další x MB stacku, tak už to nezhavaruje
2. ať bych přidal jakékoli množství, tak to stejně zhavaruje

Tyhle dvě možnosti odlišit je dost problém.

[Zz]

Tyhle dvě možnosti odlišit je dost problém.

Nic takového nerozporuji.
Já jen chci vědět konkrétní příklad, kde se Turing využije v praxi. Kompilátor Haskelu mě neuspokojil.

[JS]

Mám tomu rozumět tak, že nevíš jak je implementován kompilátor tvého oblíbeného jazyka ? Zda tam je nabušená turingova mašina, nebo záležitosti z pekelné praxe jako stack overflow nebo timeout exceed ?

Kompilator meho oblibeneho jazyka ten problem, jak zvolit velikost zasobniku, prehazuje na uzivatele (ktery to samozrejme taky dobre vedet nemuze).