VŠ z trochu jiného úhlu

[Mirek Prýmek]

V praxi se nedá dívat na počítač jako na konečný automat. Opravdu model Turingova stroje je mnohem vhodnější.

Smím vědět, čím se TS liší od FSM, kromě toho, že má nekonečnou paměť? Je podle tebe jakýkoli TS s konečně dlouhou páskou převoditelný na FSM nebo ne?

[Reklama]

[mc.]

Smím vědět, čím se TS liší od FSM, kromě toho, že má nekonečnou paměť? Je podle tebe jakýkoli TS s konečně dlouhou páskou převoditelný na FSM nebo ne?

TS s konečně dlouhou páskou? Pokud si rozumíme, pak ano, protože obsah pásky můžu zakódovat do stavů... ale teď mám pocit, že touto otázkou jsme se dostali jinam, než kde jsem byl se svým příspěvkem já...

[Mirek Prýmek]

ale teď mám pocit, že touto otázkou jsme se dostali jinam, než kde jsem byl se svým příspěvkem já...

No podle mě jsi se snažil vyvolat falešný dojem, že otázka složitosti algoritmu je nějak svázaná s TS a proto je TS potřeba, zatímco FSM by nestačil. Což je samozřejmě blbost. Není žádný lineární algoritmus ve složitostně-turingovském smyslu. Protože není žádný složitostně-turingovský smysl. TS se pro zkoumání složitosti používá (jak správně píše JS) jenom proto, aby byly věci jednodušší (nemusely se brát v potaz omezení).

Viz tahle věta: Pokud máte lineární algoritmus, tedy velice efektivní v tom "složitostně-turingovském" smyslu, tak (až na nějaké umělé, obskurní případy) bude efektivní i na běžném hardware.

TS ale není nějak "podobnější HW" než FSM, je to přesně naopak. TS se používá jako zjednodušení, aby nebylo nutný se párat s omezeními.

[mc.]

TS ale není nějak "podobnější HW" než FSM, je to přesně naopak. TS se používá jako zjednodušení, aby nebylo nutný se párat s omezeními.

S tím souhlasím, jako přesnější model HW opravdu je FSM. Což je třeba princip explicitního model checkingu - zkoumat všechny stavy (nebo alespoň všechny zajímavé) systému.

Ale pořád si stojím za tím, že složitost problému na turingově stroji koresponduje s náročností problému v reálu (resp. s analogickým problémem, který je omezený konečností světa), a proto je vhodné používat složitostní analýzu. S tím nesouhlasíš?

[JS]

TS ale není nějak "podobnější HW" než FSM, je to přesně naopak. TS se používá jako zjednodušení, aby nebylo nutný se párat s omezeními.

Jak se to vezme. Pokud nekdo rekne, "hledam algoritmus na porovnani, zda 2 programy delaji totez", nema tim na mysli to, ze hleda ten "naivni" algoritmus, co ceka 2^1G stavu, aby to mohl prohlasit. Hleda neco chytrejsiho. Proto definujeme algoritmus na nekonecne mnozine, a proto je to uzitecne (uz abychom vedeli, kde nehledat).

[Reklama]

[Mirek Prýmek]

Ale pořád si stojím za tím, že složitost problému na turingově stroji koresponduje s náročností problému v reálu (resp. s analogickým problémem, který je omezený konečností světa), a proto je vhodné používat složitostní analýzu. S tím nesouhlasíš?

No já spíš nevím, co to tvrzení má znamenat. Podle mě je nesmyslné, nedává smysl - podobně jako "hranatá koule".

Nic jako "složitost na turingově stroji" prostě není. Je jenom složitost výpočtu - tj. počet kroků, které je potřeba udělat k tomu, abych dostal výsledek. Jestli to budu dělat na stroji s konečnou nebo nekonečnou pamětí (tj. na FSM nebo TS) nemá na složitost žádný vliv.

"Krok výpočtu" je prostě změna stavu něčeho - a jestli to něco je obklobeno nekonečným počtem nějakých jiných něc, je úplně jedno.

[Mirek Prýmek]

Jak se to vezme. Pokud nekdo rekne, "hledam algoritmus na porovnani, zda 2 programy delaji totez", nema tim na mysli to, ze hleda ten "naivni" algoritmus, co ceka 2^1G stavu, aby to mohl prohlasit. Hleda neco chytrejsiho. Proto definujeme algoritmus na nekonecne mnozine, a proto je to uzitecne (uz abychom vedeli, kde nehledat).

Ať je to jak chce, to, že něco jde na TS neznamená, že to jde na fyzickém stroji.

Žádný fyzický stroj nikdy nebude umět rozeznávat jazyk a^(n)b^(n) - protože to holt je FSM

A proto je od céčka k javě blíž než od TS k javě    -- no nic, to už byl jenom takový vtípek, dobrou noc, pánové.

[poiu]

Jmenujte jeden jediný problém z jádra Windows nebo Linuxu, který nejde vyřešit bez znalostí Turingova stroje. To si rád poslechnu.

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.

[Trdlo]

Tato diskuse je jako chlapec snažící se udržet konverzaci s dívkou i za cenu, že bude mluvit bláboly, resp. věci, které nejsou ve shodě s tématem diskuse.

Je tady již přes 1000 příspevků a nikdo se ještě nedobral k výsledku, z čehož předpokládám, že autor diskuse jen stále přilévá benzín do ohně. Myslel jsem si, že tady bude konstruktivní diskuse o vysokém školství, jenže tomu tak není. Někteří z vás, ač akademici, se jen dohadujete o (ač zajímavých) partiích informatiky, ale nevšímáte si toho, že původní téma diskuse už vůbec neplníte. Jste tady jako kohouti v aréně bojující o to, čí turingův stroj bude mít delší/kratší/menší/větší parametr xyz. Běžte za svými ženami, udělejte jim radost, vypněte své počítače a jděte spát.

[mc.]

Nic jako "složitost na turingově stroji" prostě není. Je jenom složitost výpočtu - tj. počet kroků, které je potřeba udělat k tomu, abych dostal výsledek. Jestli to budu dělat na stroji s konečnou nebo nekonečnou pamětí (tj. na FSM nebo TS) nemá na složitost žádný vliv.

"Krok výpočtu" je prostě změna stavu něčeho - a jestli to něco je obklobeno nekonečným počtem nějakých jiných něc, je úplně jedno.

Složitostí myslím počet kroků výpočtu, to je jasné.

Já pořádně nechápu, co se mi teď snažíš vyvrátit. Nesouhlasíš s tím, že TS je vhodný model pro zkoumání vlastnostní algoritmů? FSM je snad lepší? Není. Na FSM nemůžeš nijak zkoumat vztahy mezi velikostí zpracovávaných dat (tj. velikostí vstupu) a délkou výpočtu, protože každý (det.) FSM počítá stejně dlouho...

Ty dáváš příklad a^nb^n jako argument, že máme TS zahodit a koukat na počítače skrz FSM? To už je moc abstraktní, prakticky přece a^nb^n počítač umí rozpoznávat :-)

[Mirek Prýmek]

Já pořádně nechápu, co se mi teď snažíš vyvrátit. Nesouhlasíš s tím, že TS je vhodný model pro zkoumání vlastnostní algoritmů? FSM je snad lepší? Není.

Není. Složitost vůbec nemá nic poslečného s FSM nebo TS, to se snažím říct.

Na FSM nemůžeš nijak zkoumat vztahy mezi velikostí zpracovávaných dat (tj. velikostí vstupu) a délkou výpočtu, protože každý (det.) FSM počítá stejně dlouho...

Samozřejmě že můžu - prostě si ho nadefinuju stejně jako TS, akorát mu dám konečnou pásku Nebo použiju klasický FSM s epsilon stavy a budu počítat změny stavů.

To už je moc abstraktní, prakticky přece a^nb^n počítač umí rozpoznávat :-)

Opět přesně naopak - prakticky ho rozpoznávat neumí, protože nemá nekonečnou paměť, která je k tomu nutně potřeba

[Mirek Prýmek]

ale nevšímáte si toho, že původní téma diskuse už vůbec neplníte.

Všechno beztak zaznělo v prvních stech příspěvcích, tak proč nepřijmout jako fakt, že se z tématu stalo jenom takové nesourodé plácání o všem možném? Je to aspoň lepší než po sté odpovídat na ten samý dotaz

[poiu]

ale nevšímáte si toho, že původní téma diskuse už vůbec neplníte.

Ja si myslím, že aj áno - rozpráva sa o niečom stále. Akurát by to možno ešte chcelo, aby niekto spravil forum.root.cz irssi plugin a odpovede chodili priamo tam na štýl IRC.

[JS]

Všechno beztak zaznělo v prvních stech příspěvcích, tak proč nepřijmout jako fakt, že se z tématu stalo jenom takové nesourodé plácání o všem možném?

Nejspis proto, ze chces zrusit vyuku neceho, jehoz smyslu sam nerozumis. Snaha nahradit analyzu TS analyzou KA je jako snazit se vynechat realna cisla, a delat analyzu jen na tech racionalnich, protoze v praxi stejne realna cisla neumime popsat. Je to uplne stejna blbost.

A nez mi zacnes vykladat, jak jsem arogantni, mel by sis uvedomit, ze ti to tu rika vic inteligentnich lidi. A ze se mozna mylis ty.

[Mirek Prýmek]

Nejspis proto, ze chces zrusit vyuku neceho, jehoz smyslu sam nerozumis. Snaha nahradit analyzu TS analyzou KA je jako snazit se vynechat realna cisla, a delat analyzu jen na tech racionalnich, protoze v praxi stejne realna cisla neumime popsat. Je to uplne stejna blbost.

A nez mi zacnes vykladat, jak jsem arogantni, mel by sis uvedomit, ze ti to tu rika vic inteligentnich lidi. A ze se mozna mylis ty.

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. Nikdy nesestrojí dokonce ani stroj, který by skutečně uměl rozpoznávat jazyk a^{n}b^{n}. Protože to prostě fyzicky nejde. Vždycky a navěky budeme mít k dispozici jenom stroje výpočetní síly FSM.

A především je imho úplně mylná představa, že počítání složitosti je možné jenom pro TS. To samozřejmě není. Složitost v tomhle abstraktním smyslu není nijak vázaná na žádný stroj konkrétní výpočetní síly.