Příspěvky

7711

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 23:01:29 »

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.

7712

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 22:42:23 »

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?

7713

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 21:45:13 »

Ale neviem, ako si presne predstaviť všetky algoritmy, ktorým stačí obmedzená pamäť - či je to 1 obmedzenie pamäti pre všetky algoritmy alebo zvlášt konečné obmedzenie pre každý.

Představovat si můžeme oboje. Ale jenom to první má reálně smysl uvažovat (pokud se bavíme o fyzickém světě

7714

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 21:36:32 »

Když má pracovní páska T.S. délku N pro všechny vstupy, tak je to konečný automat.

No dyť jsem to říkal: přijde mi, že to docela koresponduje s intuitivní představou: mám-li konečné množství stavů, potom musí být nutně možnost porovnání výpočtu hrubou silou.

7715

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 21:23:21 »

On je rozdíl uvažovat stroje s omezenou pamětí a algoritmy, kterým stačí omezená paměť. Pokud uvažuju stroje s omezenou pamětí, tak tam si ty programy opravdu srovnám. Ale zase máte problém, že ty programy si sice srovnáte na turingově stroji, ale ten váš stroj s omezenou pamětí je srovnat nedokáže. A jste tam, kde jste byli

No stejně by to dopadalo tak, že dva stroje délky x a y umím srovnat jenom strojem minimální délky nějaké f(x,y), jak jinak by to mohlo dopadnout?

7716

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 21:04:06 »

On je vtip v tom, že já jsem sice kladl předpoklady na algoritmus a, ale vůbec jsem si neomezil výpočetní model.

Ono by to nešlo imho právě ani pro množinu A všech konečných strojů, to jsou pořád slabá omezení.

[sarkasmus]
Tak ok, tak jsme zjistili, že jsme nic nezjistili, protože teorie, kterou známe, se detailně zabývá něčím, co stejně v praxi neexistuje [/sarkasmus]

7717

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 20:49:29 »

Ano, to plyne např. Riceovy věty.

No a plyne z toho nějak, že nemůžeme zjistit ekvivalenci dvou automatů s konečnou páskou?

7718

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 20:37:17 »

Kurnik a zase jsem to napsal blbě. Já už dneska fakt raději půjdu spát...

Konkrétně ten problém vidím v tomhle: Uvažujme množinu A všech algoritmů, které vyčíslují f. Pak já tvrdím, že A není rekurzivní.

Asi teda není. Ale plyne z toho nějak, že neumím porovnat dva konrétní konečné algoritmy?

Myslím, že ne, ale už to raději nechám na vás, dneska mi to fakt nějak nejde   (což mimochodem jenom dokazuje, co jsem říkal: nikdy jsem to nepoužil a skoro všechno zapomněl

7719

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 20:30:15 »

No a? Však já ji na ten algortimus nepoužívám.

Máš pravdu. Ono to asi fakt bude korektní

On asi bude problém vůbec v tom pojmu "konečná páska", protože chceš cosi tvrdit o množině všech strojů s konečnou páskou - tj. o všech strojích s libovolně dlouhou páskou, čili v podstatě o stroji s nekonečnou páskou Minimálně o nekonečné množině různých strojů. A i intuitivně je jasný, že těžko můžu garantovat, že v konečném čase projdu nekonečnou množinu...

Kdybysme řekli, jestli jde porovnat ekvivalence programů o maximální délce 1024, tak to by asi bylo jiný kafe.

Takže abysme se vrátili na začátek, v praxi potřebujeme řešit tu druhou úlohu, ne tu první

7720

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 20:04:57 »

Proč by ne, nechť algoritmus a je realizovatelný na stroji s konečnou pamětí, pak ... zbytek důkazu je stejný.

Jenže o takových algoritmech věta o rekurzi nemluví.

7721

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 20:04:14 »

Ako si prišiel k implikácii "nepotřebuje víc jak x políček pásky" => "Vždy zastaví" alebo aspoň kde mám chybu v mojom TS, ktorý donekonečna chodí LR a nepotrebuje viac ako 2 políčka pásky.

Podle mě to bylo myšleno opačně: "žádný algoritmus, který zaručeně zastaví, nepotřebuje nutně nekonečnou pásku".

No a to právě není pravda, pokud mluvíme obecně o algoritmu realizujícím nějakou funkci s neomezenou délkou vstupu (ani identitu).

7722

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 19:59:25 »

V tom pro tebe oplatí první varianta důkazu.

Nechápu. Podle mě prostě negarantuješ, že skutečně mluvíš o funkci realizovatelné strojem s konečnou pamětí.

7723

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 19:53:07 »

Když si vezmu třeba hloupé sčítání s neomezenou přesností - neexistuje žádné x takové, aby mi páska délky x stačila. Mám algoritmus, který se zaručeně zastaví, a přitom potřebuju (potenciálně) nekonečnou pásku.

- přijde mi, že to docela koresponduje s intuitivní představou: mám-li konečné množství stavů, potom musí být nutně možnost porovnání výpočtu hrubou silou. Ten problém, co tam zdánlivě nastává, je v tom, že při té tvé úvaze nemám konečné množství stavů, protože vstupů je nekonečně a nemám nijak garantováno, že dva různé vstupy způsobí stejný stav.

(asi to píšu kostrbatě, ale snad je jasný, co mám tak asi namysli)

7724

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 19:50:25 »

Pokud si to změníte na "nepotřebuje více jak x políček pásky", tak by to snad nemělo nic změnit.

Nejsem si jistej, jestli je ten důkaz korektní.

Když si vezmu třeba hloupé sčítání s neomezenou přesností - neexistuje žádné x takové, aby mi páska délky x stačila. Mám algoritmus, který se zaručeně zastaví, a přitom potřebuju (potenciálně) nekonečnou pásku.

7725

Studium a uplatnění / Re:VŠ z trochu jiného úhlu

« kdy: 21. 10. 2012, 18:59:37 »

Jenže tohle obecně nefunguje, když neznáte velikost té pásky (co když uživatel přidá paměť?).

Stejně tohle nemá vůbec smysl řešit, takové věci se prostě v praxi obvykle nedějí.

Obvyklý program když běží dlouho, tak nejspíš provádí nějaké iterace s cílem něčeho dosáhnout. Nějproblematičtější jsou možná stochastické algoritmy typu neuronek. Ale tam se to afaik opět řeší úplně stupidně "inženýrsky" - sleduje se, jestli dochází ke konvergenci a když ne, tak se prostě předpokládá, že lepší už to nebude. A spadla klec!