VŠ z trochu jiného úhlu

[Mirek Prýmek]

Pokud ty to myslíš tak, že tvrzení o jednom konkrétním TM je vlastně jakoby tvrzením o jednom konkrétním FSM krát všechny možné délky vstupů (tedy "dohromady nekonečný vstup"), tak to podle mě není pravda.

[Reklama]

[Mirek Prýmek]

Vlastně je to pravda Takže takhle jsi to myslel?

[mc.]

Prýmku, problém, který jsem se ti snažil vysvětlit já, spočívá v tom, že ano máš pravdu, že HP je pro FSM rozhodnutelný (ehm, když si ho nějak upravíme, protože formálně FSM čte s každým výpočetním krokem jeden symbol, ale na formalismy se nedívejme). Bohužel s tím, že budeš muset prozkoumat všechny stavy, které FSM má. A to je v reálném HW nemožné, jelikož různých konfigurací pár megabajtů paměti je víc, než atomů ve vesmíru.

Obecněji se dá říct, že sice máš pravdu v tom, že na FSM jakoby odpadá neřešitelnost problémů tak, jak to známe z TS, bohužel ale za to platíš tím, že tvůj algoritmus někde v nějaké formě musí projít všechny stavy systému - a to je prakticky neřešitelné.

Neřešitelnost na TS ~ průzkum všech stavů na FSM ~ praktická neřešitelnost.
Řešitelnost na TS ~ chytrý algoritmus bez průzkumu všech stavů FSM ~ (často) praktická řešitelnost.

[Jakub Galgonek]

Vlastně je to pravda Takže takhle jsi to myslel?

No, TS s pevnou délkou vstupu je sice ekvivalentní nějakému FSM, ovšem pozor, obecně nejsi schopen takový FSM sestrojit.

[Mirek Prýmek]

Obecněji se dá říct, že sice máš pravdu v tom, že na FSM jakoby odpadá neřešitelnost problémů tak, jak to známe z TS, bohužel ale za to platíš tím, že tvůj algoritmus někde v nějaké formě musí projít všechny stavy systému - a to je prakticky neřešitelné.

Mně na tom vadí tahle věc:

Mám průměrného absolventa, který tou teorií prošel. Dám mu nějaký konkrétní algoritmus a otázky:
1. zastaví se ten algoritmus na stroji s X bitů paměti při vstupu aaabba?
2. zastaví se ten algoritmus na všech vstupech o délce max. N?
3. zastaví se ten algoritmus na všech vstupech?

Vsadím boty na to, že průměrný absolvent řekne, že to přece nebude řešit, protože HP je neřešitelný. A to je přece blbost. Prostě reálně ten problém řešitelný je a průměrného absolventa ta teorie spíš zmate, protože se mluví obecně o TM a ne o reálné mašině s limitovanou pamětí. Navíc reálné algoritmy pracují s odděleným kódem a daty, což tu analýzu zase výrazně zjednodušuje.

Prostě to, že průměrný absolvent si zapamatuje maximálně obecná tvrzení o TM, ho podle mě spíš zmate, než že by mu to nějak pomohlo.

[Reklama]

[mc.]

Mně na tom vadí tahle věc:

Mám průměrného absolventa, který tou teorií prošel. Dám mu nějaký konkrétní algoritmus a otázky:
1. zastaví se ten algoritmus na stroji s X bitů paměti při vstupu aaabba?
2. zastaví se ten algoritmus na všech vstupech o délce max. N?
3. zastaví se ten algoritmus na všech vstupech?

Ačkoli s tím moc nesouhlasím (alespoň ne pro FI), asi nemá cenu dělat nějaké průzkumy absolventů, abychom si ověřili, kolik jich odpoví správně :-)

Mimochodem, vzpomínám si ale na testovou otázku z předmětu Formální jazyky a automaty, která testovala podobný princip. Něco ve smyslu:

Je rozhodnutelný následující problém? Pro vstup TS M+slovo w rozhodnout, zda-li TS M při výpočtu nad slovem w použije (popíše) vice jak 100 políček pásky.

[Zz]

Je rozhodnutelný následující problém? Pro vstup TS M+slovo w rozhodnout, zda-li TS M při výpočtu nad slovem w použije (popíše) vice jak 100 políček pásky.

A to se dělá jak ? Není mi známo že by teorie o TS umožňovala determinovat počet popsaných políček, ale třeba tomu jenom nerozumím. Není to doufám tak, že si student otrocky provádí algoritmus na papíře a pak spočítá políčka ?

[mc.]

A to se dělá jak ? Není mi známo že by teorie o TS umožňovala determinovat počet popsaných políček, ale třeba tomu jenom nerozumím. Není to doufám tak, že si student otrocky provádí algoritmus na papíře a pak spočítá políčka ?

Nepochopil jsi zadání, otázka je, jestli je nějaký problém rozhodnutelný (algoritmicky řešitelný).

(Studentovi tedy stačí napsat/zaškrtnout "Ano")

[Mirek Prýmek]

Nepochopil jsi zadání, otázka je, jestli je nějaký problém rozhodnutelný (algoritmicky řešitelný).

No jo, to je sice bezva, ale je to vlastně jenom test toho, jestli se student tou teoretickou látkou nechal zmást nebo ne - protože pro konečné stroje jsou všechny problémy algoritmicky rozhodnutelné. Nebo je něco nerozhodnutelného?

[JS]

Vlastně je to pravda Takže takhle jsi to myslel?

Ano. To je to co od zacatku rikam, ze ta Turingova veta je tvrzenim o nekonecne mnozine konecnych veci, nikoli tvrzenim o nekonecne veci. A proto ma prakticke aplikace, protoze ona nekonecna mnozina dobre aproximuje to, co v praxi delame.

[JS]

No jo, to je sice bezva, ale je to vlastně jenom test toho, jestli se student tou teoretickou látkou nechal zmást nebo ne - protože pro konečné stroje jsou všechny problémy algoritmicky rozhodnutelné. Nebo je něco nerozhodnutelného?

Zalezi, co povazujes za "problem na konecnem stroji". Pokud je treba velikost tech stroju (a tedy i pocet stavu) omezena, pak to samozrejme vse algoritmicky rozhodnutelne je. Tam pak nastavaji jine problemy, treba typu P=NP, coz je prave urcity analog nerozhodnutelnosti.

[poiu]

(...)
Vsadím boty na to, že průměrný absolvent řekne, že to přece nebude řešit, protože HP je neřešitelný.

Tak toho môžeš rovno vyhodiť - rovnako ako každého, kto sa pokúša použiť ľubovolnú na škole naučenú vetu bez (nejakého) overenia predpokladov.

Tam by som pochyboval aj o tom, že takýto absolvent vôbec spravil tú vysokú školu regulérne - každý normálny skúšajúci vyhodí študenta, keď sa študent pokúsi spraviť niečo také. Že by to niekto na škole nerobil a potom začal, o tom pochybujem. A keď za to bol aspoň raz vyhodený, tak si to mal zase zapamätať.

[Jakub Galgonek]

Prostě to, že průměrný absolvent si zapamatuje maximálně obecná tvrzení o TM, ho podle mě spíš zmate, než že by mu to nějak pomohlo.

A proto se na některých VŠ prý učí například to, že každá funkce má derivaci

[xxx]

Vás to opravdu ještě baví?

[poiu]

A proto se na některých VŠ prý učí například to, že každá funkce má derivaci

To je podľa mňa nezmysel (protipríklad napadne aj lepšieho škôlkára). Aj tak by som rád vedel, ako sa niečo netriviálne dokazuje pre všetky funkcie bez ďalších predpokladov. Ale vlastne - poznáte niekto nejaké netriviálne tvrdenie o všetkých funkciách?