VŠ z trochu jiného úhlu

[Zz]

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

Uživatel po prvním vyhučení dá na zásobník veškerou volnou paměť a když to i pak vyhučí, tak algoritmus hodí ze skály a buď ho zásadně změní nebo zkusí úplně jiný.

Už tě nebudu dál trápit, to mi takhle stačí

[Reklama]

[JS]

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.

Nechapu, jakou ted pouzivas definici algoritmu. Vseobecne se algoritmus definuje jako TS (viz Churchova teze). Muzes ho samozrejme definovat jako KA, ale pak toto tve omezene chapani algoritmu bude jen znamenat, ze vety o TS jsou vety o algoritmech (v tvem smyslu) parametrizovanych prirozenymi cisly.

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

Ale my se bavime o nekonecne velke mnozine KA. Protoze to je to, co nas v praxi zajima. Je to asi podobne, jako kdybys tvrdil, ze nepotrebujes znat rovnici na obsah kruhu, protoze pi stejne nespocitame na "nekonecny" pocet cifer, a v praxi je kazdy kruh jenom polygon. Ale to naprosto miji tu pointu, totiz ze ta rovnice vyjadruje nejaky vztah, ktery uz prakticky smysl ma.

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

Aplikace vet o TS nekonecnou pasku nevyzaduji, podobne, jako vyse, aplikace vzorecku o obsahu kruhu nevyzaduje znat pi na nekonecny pocet mist. Podstatna je ta neomezenost pasky, nikoli nekonecnost.

[JS]

Uživatel po prvním vyhučení dá na zásobník veškerou volnou paměť a když to i pak vyhučí, tak algoritmus hodí ze skály a buď ho zásadně změní nebo zkusí úplně jiný.

Proc ne, stejne jako existuji lide, kteri se pokousi sestrojit perpetuum mobile, prestoze z fyziky vime, ze to nejde.

[Zz]

Proc ne, stejne jako existuji lide

Když jim teoretikové nejsou schopni prakticky naimplementovat Turinga, který by o jejich nápadu řekl jestli to je nebo není nesmysl, tak jim nic jiného nezbývá.

[Mirek Prýmek]

Nechapu, jakou ted pouzivas definici algoritmu. Vseobecne se algoritmus definuje jako TS (viz Churchova teze). Muzes ho samozrejme definovat jako KA, ale pak toto tve omezene chapani algoritmu bude jen znamenat, ze vety o TS jsou vety o algoritmech (v tvem smyslu) parametrizovanych prirozenymi cisly.

No ano. Například můžu říct, že můj stroj je schopný rozeznat jazyk a^{n}b^{n} jenom pro n<k. A to taky odpovídá realitě skutečného počítače. S čím teda vlastně nesouhlasíš?

Ale my se bavime o nekonecne velke mnozine KA.

Bavíme se o tvém tvrzení "Neexistuje reseni [HP pro FSM], ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA." Ptám se, jestli to můžeš dokázat.

Aplikace vet o TS nekonecnou pasku nevyzaduji, podobne, jako vyse, aplikace vzorecku o obsahu kruhu nevyzaduje znat pi na nekonecny pocet mist. Podstatna je ta neomezenost pasky, nikoli nekonecnost.

To snad záleží na tom, jaká aplikace, ne? Např. nemůžu řict, že TS rozeznává jazyk a^{n}b^{n}, takže ho je možné rozeznat i na reálném HW. Nejde.

[Reklama]

[JS]

Bavíme se o tvém tvrzení "Neexistuje reseni [HP pro FSM], ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA." Ptám se, jestli to můžeš dokázat.

Samozrejme, to je prece to, co rika Turingova veta - neexistuje takovy TS, ktery by byl schopen pro nekonecnou mnozinu TS (ktera je ovsem zadana konecne) a zadany vstup urcit, zda se zastavi. Myslim, ze si trochu nerozumime, museli bychom to definovat presneji.

Ale znovu opakuji: TS nevyzaduje nekonecnou pasku; TS je v podstate stavovy automat, a tedy konecna vec. To co vyzaduje nekonecnou pasku je aplikace TS na algoritmy (coz jsou v podstate nekonecne mnoziny konecnych stavovych automatu, jenom nejak parametrizovane, takze jejich popis je konecny, a jak lze ukazat, muzeme je reprezentovat pomoci TS).

To snad záleží na tom, jaká aplikace, ne? Např. nemůžu řict, že TS rozeznává jazyk a^{n}b^{n}, takže ho je možné rozeznat i na reálném HW. Nejde.

Na realnem hardware je mozne rozeznat a^nb^n pro libovolne zadane n. V tom je cely ten vtip - my muzeme zkonstruovat konecny popis, ktery tohle dela; bez ohledu na to, zda ten realny HW lze postavit. U HP takovy konecny popis nevyrobis.

[ded kenedy]

Když začneme na špatné škole učit hodně teorie, stane s z ní Caltech? Je teorie opravdu tím, co dělá Caltech Caltechem?

A znovu: kolik, jaké a jak se vlastně té teorie třeba na tom Caltechu učí? To by bylo potřeba nějak doložit. Zatím jsme se koukli na Princeton a tam jsou (pokud jsem správně pochopil studijní požadavky) povinné 4 matematické předměty na 4 roky studia. A k tomu OSM předmětů, které bysme nejspíš zařadili do ranku "soft" nebo přinejmenším humanities ( http://www.princeton.edu/ua/sections/11/ )

Sice se tema posunulo trochu jinam, ale neodpustim si poznamku k tomu mnozstvi matiky, co se uci jinde...

Semestr na americky skolach ma vetsinou 4 mesice, uci se od zacatku zari a konci se az skoro pred vanocema a predmety jsou vetsinou 2x tydne, takze prumerny predmet ma za semestr kolem 30 vyucovacich hodin! V cesku to je obvykle 12-13 vyucovacich hodin na semestr. Takze kdyz se to prevede, tak to odpovida minimalne 8 ceskym predmetum, coz uz moc nevybocuje z toho, co se uci u nas.

[Mirek Prýmek]

Tak teď nevím. Buďto jsem blázen, nbo mi asi něco nedochází...

Bavíme se o tvém tvrzení "Neexistuje reseni [HP pro FSM], ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA." Ptám se, jestli to můžeš dokázat.

Samozrejme, to je prece to, co rika Turingova veta - neexistuje takovy TS, ktery by byl schopen pro nekonecnou mnozinu TS (ktera je ovsem zadana konecne) a zadany vstup urcit, zda se zastavi. Myslim, ze si trochu nerozumime, museli bychom to definovat presneji.

1. proč si tam přidáváš tu "nekonečnou množinu TS"?
Viz wiki: In computability theory, the halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever."  [...]  A key part of the proof was a mathematical definition of a computer and program, what became known as a Turing machine;" [http://en.wikipedia.org/wiki/Halting_problem]
- já jsem to doteď chápal tak, že nemůžu mít jeden TS, kterému bych předal definici libovolného TS a on by mi řekl "zastaví se" nebo "nezastaví se". Nikde nevidím žádnou "nekonečnou množinu TS", nad žádnou nekonečnou množinou neoperuju, předám mu prostě jeden libovolný TS.

To je jako bys řekl, že operace "přičti 1" operuje nad nekonečnou množinou, protože jí můžu předat libovolné číslo z nekonečné množiny čísel.

...anebo mi teda asi něco nedochází, prosil bych to vysvětlit nějak líp, nejraději úplně formálně.

2. Problém zastavení KA je přece něco jiného než problém zastavení TS.
Opět znovu citace Wiki (kterou už jsem uváděl, opět jsi neslyšel?): The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory.
- jak to jde dohromady s tvou větou "Neexistuje reseni [HP pro FSM], ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA." ? Je špatně Wiki, nebo tvoje věta, nebo ty věty nejsou v rozporu (potom prosím taky vysvětlit nějak blbuvzdorněji)

Ale znovu opakuji: TS nevyzaduje nekonecnou pasku; TS je v podstate stavovy automat, a tedy konecna vec. To co vyzaduje nekonecnou pasku je aplikace TS na algoritmy (coz jsou v podstate nekonecne mnoziny konecnych stavovych automatu, jenom nejak parametrizovane, takze jejich popis je konecny, a jak lze ukazat, muzeme je reprezentovat pomoci TS).

Tak tohle je buď hraní se slovy, nebo jsem taky úplně mimo. Mějme automat, který rozeznává jazyk a^{n}b^{n} - potřebuje podle tebe nekonečnou paměť nebo ne?

Na realnem hardware je mozne rozeznat a^nb^n pro libovolne zadane n. V tom je cely ten vtip - my muzeme zkonstruovat konecny popis, ktery tohle dela; bez ohledu na to, zda ten realny HW lze postavit.

O tom jsem ale nemluvil. Nemluvím o tom, jestli může existovat ALGORITMUS, který to dělá, ale o tom, že nemůže existovat FYZICKÝ STROJ, kterému bych mohl předhodit libovolně dlouhý řetězec a on by mi řekl "je" nebo "není". Každý fyzický stroj, který kdy člověk vyrobí, bude mít prostě nějaký limit k takový, že slovo a^{k+1}b^{k+1} nebude schopen rozpoznat.

Proto nikdy nebudeme mít fyzický stroj, který by skutečně reálně počítal to, co myšlenkový stroj zvaný TS umí počítat.

[Mirek Prýmek]

Sice se tema posunulo trochu jinam, ale neodpustim si poznamku k tomu mnozstvi matiky, co se uci jinde...

Semestr na americky skolach ma vetsinou 4 mesice, uci se od zacatku zari a konci se az skoro pred vanocema a predmety jsou vetsinou 2x tydne, takze prumerny predmet ma za semestr kolem 30 vyucovacich hodin! V cesku to je obvykle 12-13 vyucovacich hodin na semestr. Takze kdyz se to prevede, tak to odpovida minimalne 8 ceskym predmetum, coz uz moc nevybocuje z toho, co se uci u nas.

A ta poznámka nějak vysvětluje, proč mají na Princetonu na CS víc než dvakrát víc povinných humanities než matiky?

[Mirek Prýmek]

Ajo, já už ti asi rozumím - ty jsi jednoduše chtěl říct, že "zastaví se" je vlastností algoritmu, ne celého systému algoritmus+stroj_na_kterem_to_bezi.

No tak to jo. Ale to není nic jiného, než že implicitně předpokládáš definici "algoritmus je nějaká konkrétní konfigurace Turingova Stroje" - a to jsme pořád tam, kde jsme byli: žádný takový program ve skutečnosti neexistuje.  Skutečné programy "běží" na FSM - jsou to konfigurace FSM, ne TS. Proto taky HP pro skutečné programy je (teoreticky) rozhodnutelný.

[Mirek Prýmek]

Á, tak už rozumím teda konečně i té zašmodrchané větě "Neexistuje reseni [HP pro FSM], ktere by bylo konecne a stacilo ho jen parametrizovat velikosti toho KA."

- tím jsi tedy myslel "řešení jiné než hrubou silou". Ok, no tak to stačilo říct...

No tak to nevím, jestli existuje nebo neexistuje* - ale každopádně pro původní téma je to naprosto nepodstatné, protože důležitý závěr je, že pro všechny nyní existující a i budoucí skutečné fyzické počítače je a vždy bude HP teoreticky řešitelný - navzdory tomu, že pro TS není řešitelný ani teoreticky.

No tak pokud celým smyslem debaty bylo ukázat Zz-ovi, k čemu je potřeba znát TS a důkazy s ním spojené, tak to jsme se teda pochlapili

Jinak co se týče té konečnosti pásky, dá se to říct i naprosto "inženýrsky" - algoritmus běžící na FSM má předem naalokovanou paměť, zatímco algoritmus pro TM má instrukci "naalokuj další paměť". Jelikož tuhle instrukci může používat donekonečna a tím donekonečna natahovat svůj stavový prostor, nemůžeme nikdy říct, jestli se výpočet zastaví. U FSM to říct můžeme, protože množství stavů je omezené a tímpádem po N krocích zaručeně výpočet buď skončí, nebo se vrátí do nějakého předchozího stavu. Pro TM žádné takové N neexistuje, takže nám může stroj pořád unikat do nových a nových stavů a nikdy se nevrátit do stavu, ve kterém už byl, a přesto neskončit. Proto to nemůže být rozhodnutelné ani hrubou silou, natož nějak jinak.

A pak že TM nepotřebuje nekonečnou paměť a nekonečná paměť nesouvisí s HP

* a stejně by mě moc zajímalo, jak by se to dokazovalo

[ded kenedy]

A ta poznámka nějak vysvětluje, proč mají na Princetonu na CS víc než dvakrát víc povinných humanities než matiky?

Bavime se tu snad o mnozstvi matiky, ne?

Jinak tech dvakrat vic predmetu souvisi vicemene s tim, jak je nastaveny system, kde se studium deli na hlavni a vedlejsi zamereni. Univerzity to maji casto nastavene tak, ze pokud je hlavni zamereni na tvrde vedy, mel by mit student vedlejsi zamereni z mekkych ved, ktere odpovida osobnim zajmum konkretniho cloveka.  Takze casto to je, ze clovek dela obor, ktery ho bude zivit (napr. CS, ekonomika, ...) a pak si k tomu vybere oblast, ktera ho zajima (hudba, vytvarne umeni, ...) nebo kterou jde snadno prolezt. Typickym prikladem budiz treba znamy Bender Bending Rodríguez, ktery vystudoval Bending State University a jako hlavni zamereni mel ,,Ohybani'' a jako vedlejsi ,,Robo-americka studia''.

[Mirek Prýmek]

Bavime se tu snad o mnozstvi matiky, ne?

Bavíme se o množství matiky v poměru k jiným předmětům.

[JS]

Tak tohle je buď hraní se slovy, nebo jsem taky úplně mimo. Mějme automat, který rozeznává jazyk a^{n}b^{n} - potřebuje podle tebe nekonečnou paměť nebo ne?

Ty porad nechapes to zakladni, ze to nekonecno tam (v tech vetach) neni o tom, zda to muzeme postavit, ale o tom, abychom mohli neco prohlasit o libovolne velke konecne mnozine veci. Kdyz budu u tveho prikladu, pak podle tebe, konecny automat, ktery rozeznava jazyk a^n pro vsechna n take nelze prakticky postavit, protoze na to rozeznani spotrebuje nekonecne casu. Ale to neni pravda, protoze je rozdil mezi "spotrebuje nekonecne casu" a "spotrebuje libovolne velke mnozstvi casu". Automat na rozeznani a^n potrebuje to druhe. Stejne tak, TS nespotrebovava nekonecne mnozstvi pasky, ale jen libovolne velke mnozstvi. Proto ma prakticke aplikace.

[Mirek Prýmek]

Kdyz budu u tveho prikladu, pak podle tebe, konecny automat, ktery rozeznava jazyk a^n pro vsechna n take nelze prakticky postavit, protoze na to rozeznani spotrebuje nekonecne casu. Ale to neni pravda, protoze je rozdil mezi "spotrebuje nekonecne casu" a "spotrebuje libovolne velke mnozstvi casu".

No to samozřejmě NENÍ pravda - a je to úplně jiný případ:

Jazyk a^n je regulární a na jeho rozpoznání mi stačí FSM se dvěma stavy: první stav se jmenuje "doposud byly na vstupu jenom áčka" a druhý se jmenuje "už jsem dostal i něco jiného" - ten první je akceptující a přes áčko se jde zpátky do něj, přes cokoli jiného do druhého stavu. Potřebuju teda jenom jeden bit paměti, nic víc.

Pochopitelně je nesmysl "potřebuji nekonečný čas". Že automat rozeznává jazyk a^{n} znamená, že mu můžu předhodit libovolně dlouhý (konečný) řetězec "aaaa..." a on mi správně odpoví - opakuji: libovolně dlouhý.

Automat akceptující jazyk a^{n}b^{n} je úplně jiný případ - k tomu, aby uměl správně akceptovat libovolně dlouhé slovo, musí mít automat k dispozici buď nekonečnou paměť, nebo musí mít instrukci "alokuj další pamět", kterou může použít kolikrát chce a ta instrukce nikdy neselže - protože automat prostě musí někam ukládat, kolik áček zatím dostal - a ta hodnota je neomezené přirozené číslo, tudíž potřebuji mít k dispozici neomezené množství paměti. To pochopitelně neznamená, že musím mít k dispozici "aktuálně nekonečnou" paměť, ale musí být alespoň "potenciálně nekonečná", protože dopředu nikdy nevím, kolik jí skutečně budu potřebovat.

Takový jazyk není regulární a pro jeho rozpoznání potřebuju minimálně PDA, které má ex definitio k dispozici neomezené množství paměti.

Takový stroj ale nemáme a nikdy mít nebudeme. Vždycky budeme mít jenom OMEZENÉ množství paměti, což znamená, že každý fyzický stroj, který máme a kdy budeme mít, bude schopen rozeznat jazyk a^{n}b^{n} jenom pro n menší než nějaké k, což je množství dostupné paměti. Slovo a^{k}b^{k} už stroj nebude schopný rozpoznat, protože tak velké k už se mu prostě nevejde do paměti. Proto neexistuje a nikdy nebude existovat fyzický stroj, který by uměl rozeznávat celý jazyk a^{n}b^{n} - tj. a^{n}b^{n} pro libovolné přirozené n.