VŠ z trochu jiného úhlu

[Mirek Prýmek]

Ty snad nectes? Jasne jsem ti rekl, ze to nerika nic o algoritmech, ktere zname (stejne jako veta o nemoznosti trisekce uhlu nerika nic o znamych konstrukcich pravitkem a kruzitkem), ale ze to vypovida o _algoritmizaci_ - snaze prevest realny problem na algoritmus.

No tak OK. Tak se teda aspoň shodneme na tom, že pomocí myšlenkového stroje zvaného TM můžeme jenom zaručeně dokázat, že něco na fyzickém počítači NEJDE? To bysme ale mohli dokázat i pomocí myšlenkového stroje zvaného FSM.

Shodneme se taky na tom, že jediná věc, kterou pomocí myšlenky TM můžeme zjistit, je, že nějaký problém je neřešitelný nezávisle na tom, kolik paměti mám k dispozici? (i když ji mám nekonečně, stejně to nejde řešit) Všechno ostatní je totiž dokazatelné i pomocí myšlenky FSM.

[Reklama]

[Jakub Galgonek]

Ta mluvi o tom, ze neexistuje zadny TS, ktery by mohl analyzovat zastaveni nekonecne mnoziny TS.

To se mi nějak nepozdává, co přesně tím chceš říct?

Na vstupu do toho hypotetickeho TS, ktery resi problem zastaveni, dostanes zase TS nejak zakodovany a jeho vstup. Mnozina vsech TS je nekonecna. Tedy schopnost TS zpracovavat vstup libovolne delky je nutnou podminkou pro algoritmus, ktery resi problem zastaveni. Ale neni to podminka postacujici, protoze evidentne existuji jine algoritmy (jine TS), ktere take zpracovavaji vstupy libovolne delky, a tento fakt nijak nebrani jejich existenci.

No dobře, ale stále je možné udělat TS,  který by mohl analyzovat zastavení nekonečné množiny TS. Pravda, ne množiny všech TS (která je nekonečná), ale nějaká nekonečná množina, pro kterou by to svedl, by se našla.

[Mirek Prýmek]

No dobře, ale stále je možné udělat TS,  který by mohl analyzovat zastavení nekonečné množiny TS. Pravda, ne množiny všech TS (která je nekonečná), ale nějaká nekonečná množina, pro kterou by to svedl, by se našla.

Já nevím, proč pořád řešíte "definiční obor". O ten přece vůbec nejde. Důležité je, že existuje nějaký minimálně jeden konkrétní TS (nazvěme ho "lump"), jehož zastavení neumí žádný TS vyřešit.

Podle mě lump vypadá tak, že pro nějaké jedno konkrétní slovo konkrétní délky pořád zapisuje na nová a nová políčka pásky - proto nedokážeme algoritmicky rozlišit, jestli s tím jednou bude hodlat skončit nebo ne. U LBA (ani u žádného fyzického stroje) se tohle prostě nemůže stát. Proto tvrdím, že problém zastavení TS je čistě teoretický.

[Mirek Prýmek]

Řečeno jinak: "lump" má podle mě "nekonečnou" paměťovou náročnost - i pro slovo délky 1 zapisuje (postupně) na nekonečné množství políček.

[Jakub Galgonek]

No dobře, ale stále je možné udělat TS,  který by mohl analyzovat zastavení nekonečné množiny TS. Pravda, ne množiny všech TS (která je nekonečná), ale nějaká nekonečná množina, pro kterou by to svedl, by se našla.

Já nevím, proč pořád řešíte "definiční obor". O ten přece vůbec nejde.

Řeším jen to, že ta věta, co napsal, prostě neplatí. A řeším to teda asi paralelně k tomu, co tu s ním řešíš ty

[Reklama]

[Mirek Prýmek]

Řeším jen to, že ta věta, co napsal, prostě neplatí. A řeším to teda asi paralelně k tomu, co tu s ním řešíš ty

A tomu, co píšu já, rozumíš? A souhlasíš s tím, je to podle tebe správně, nebo tam mám nějakou chybu?

[Jakub Galgonek]

A tomu, co píšu já, rozumíš? A souhlasíš s tím, je to podle tebe správně, nebo tam mám nějakou chybu?

Já už to jen tak prolítávám. Každopádně mi přijde, že se tu nějak mlží pojmy. TS je z matematického hlediska konečná věc - je to šestice také konečných množin. Představujeme si jej ale jako stroj s nekonečnou páskou. TS má konečný pořet stavů, ale množina jeho možných konfigurací je nekonečná. A teď se tu jen práská konečná, nekonečná, konečná

[Mirek Prýmek]

Já už to jen tak prolítávám. Každopádně mi přijde, že se tu nějak mlží pojmy. TS je z matematického hlediska konečná věc - je to šestice také konečných množin. Představujeme si jej ale jako stroj s nekonečnou páskou. TS má konečný pořet stavů, ale množina jeho možných konfigurací je nekonečná. A teď se tu jen práská konečná, nekonečná, konečná

Základní otázka je, proč je HP pro LBA řešitelný a pro TM ne.

Ten pojem "stav" jsem trochu zamlžil, to je pravda. To je u automatů terminus technicus, měl jsem použít "konfigurace".

Takže přesněji: Umíme říct, že nikdy neskončí výpočet (konkrétního, zadaného) TM, který se vrátí do nějaké konfigurace, ve které už byl. Neumíme říct, jestli skončí výpočet (konkrétního, zadaného) TM, který pro (konkrétní, zadané) slovo vytváří pořád nové a nové konfigurace - je možné, že někdy skončí, je možné, že nikdy neskončí - a neumíme to algoritmicky rozhodnout. To je rozdíl oproti LBA, který nic takového dělat nemůže, protože množství konfigurací je u něj omezené délkou slova. Čili po určitém konečném čase (konkrétní, zadaný) LBA buď skončí, nebo se vrátí do nějaké konfigurace, ve které už byl a tímpádem neskončí nikdy. Proto je HP pro LBA řešitelný a pro TM neřešitelný. A proto je neřešitelnost HP pro TM čistě teoretická věc, se kterou se v praxi nikdy nepotkáme, protože žádný reálný stroj nemůže při výpočtu vytvářet pořád nové a nové konfigurace.

[JS]

No dobře, ale stále je možné udělat TS,  který by mohl analyzovat zastavení nekonečné množiny TS. Pravda, ne množiny všech TS (která je nekonečná), ale nějaká nekonečná množina, pro kterou by to svedl, by se našla.

To je pravda. Ale ja tam to "nekonecno" napsal proto, abych zduraznil, ze ta mnozina je nekonecna; nechtel jsem tim rict, ze to plati pro libovolnou nekonecnou podmnozinu.

[JS]

LBA má počet stavů omezený. TM má neomezený počet stavů.

Ano, ale to je neco jineho. Predtim jsi tvrdil, ze problem je v nekonecnem mnozstvi potencialnich stavu, nikoli neomezenosti. Kazdopadne, zase ta neresitelnost z te neomezenosti stavu neplyne; to je opacna implikace nez resitelnost problemu zastaveni pro LBA.

Pokud ten důvod je podle tebe jiný, proč teda nenapíšeš, jaký?

Ten duvod je platnost Turingovy vety, a nema cenu to tu opakovat (krome toho, sam si to jiz presne nepamatuji). Ta veta byla dokazana a presne rika, proc to tak je. Ale ten dukaz neprobiha ve smyslu "TS ma neomezene mnoho stavu, a proto to nejde". Je trochu slozitejsi.

[JS]

Já nevím, proč pořád řešíte "definiční obor". O ten přece vůbec nejde. Důležité je, že existuje nějaký minimálně jeden konkrétní TS (nazvěme ho "lump"), jehož zastavení neumí žádný TS vyřešit.

Ne. Pro kazdy vstupni TS muzes dost mozna najit TS, ktery resi jeho zastaveni (z Turingovy vety neplyne ani pozitivni, ani negativni odpoved na tuto otazku). Co nenajdes je obecny TS, ktery to dela pro vsechny TS. Takze tu neresitelnost nezpusobuje zadny konkretni TS, ale jejich mnozina jako celek.

[JS]

Ne. Pro kazdy vstupni TS muzes dost mozna najit TS, ktery resi jeho zastaveni (z Turingovy vety neplyne ani pozitivni, ani negativni odpoved na tuto otazku). Co nenajdes je obecny TS, ktery to dela pro vsechny TS. Takze tu neresitelnost nezpusobuje zadny konkretni TS, ale jejich mnozina jako celek.

Dokonce ani fakt, ze ta mnozina TS je nekonecna nemusi zpusobovat tu neresitelnost. Mohou existovat nekonecne mnoziny TS takove, pro ktere umime resit problem zastaveni. Proto ta neomezenost neni postacujici podminkou pro platnost Turingovy vety.

[JS]

A proto je neřešitelnost HP pro TM čistě teoretická věc, se kterou se v praxi nikdy nepotkáme, protože žádný reálný stroj nemůže při výpočtu vytvářet pořád nové a nové konfigurace.

A jsme zase u te stejne hlouposti, kterou tvrdis. Je to asi jako rict: "Jelikoz perpetuum mobile nelze postavit, pak je fakt, ze ho nelze postavit, ciste teoreticka vec, a v praxi se s pokusy postavit perpetuum mobile nesetkame." No ano! Samozrejme, prave protoze vime, ze to nejde, ani se o to nikdo (rozumny) nepokousi. To ale neznamena, ze nema smysl se ucit, ze to nejde.

[Zz]

"Jelikoz perpetuum mobile nelze postavit, pak je fakt, ze ho nelze postavit, ciste teoreticka vec, a v praxi se s pokusy postavit perpetuum mobile nesetkame." No ano! Samozrejme, prave protoze vime, ze to nejde, ani se o to nikdo (rozumny) nepokousi. To ale neznamena, ze nema smysl se ucit, ze to nejde.

A skutečně víme alespoň o jednom troubovi, který ignoroval studium Turinga a díky tomu se marně pokoušel v praxi ohledně počítačů řešit neřešitelný problém ? To není nic proti nikomu, jenom mě to tak zajímá.
Troubů ohledně perpetua mobile znám dost.

[Mirek Prýmek]

Ano, ale to je neco jineho. Predtim jsi tvrdil, ze problem je v nekonecnem mnozstvi potencialnich stavu, nikoli neomezenosti.

Neomezené množství konfigurací = potenciálně nekonečné množství konfigurací.

Kazdopadne, zase ta neresitelnost z te neomezenosti stavu neplyne; to je opacna implikace nez resitelnost problemu zastaveni pro LBA.

LBA je úplně stejný jako TM s tím rozdílem, že má množství konfigurací omezené délkou vstupního slova. Pro LBA je HP řešitelný, pro TM není řešitelný. Každý ať posoudí sám, jestli neřešitelnost plyne nebo neplyne z neomezenosti, já už se opakovat nebudu.

Ale ten dukaz neprobiha ve smyslu "TS ma neomezene mnoho stavu, a proto to nejde". Je trochu slozitejsi.

To, že se ten důkaz dělá jinak, nic nedokazuje. Může být x důkazů vedených úplně jiným způsobem.

A jsme zase u te stejne hlouposti, kterou tvrdis. Je to asi jako rict: "Jelikoz perpetuum mobile nelze postavit, pak je fakt, ze ho nelze postavit, ciste teoreticka vec, a v praxi se s pokusy postavit perpetuum mobile nesetkame." No ano! Samozrejme, prave protoze vime, ze to nejde, ani se o to nikdo (rozumny) nepokousi. To ale neznamena, ze nema smysl se ucit, ze to nejde.

Ale vždyť jsem explicitně psal pravý opak: abstrakce zvaná TM se HODÍ na to, dokázat, že na normálním počítači něco nejde. Hodí se na to, když chci dokázat, že něco nevyřeším ani s nekonečnou (neomezenou) pamětí, čili s omezenou pamětí to nevyřeším zcela jistě taky.