VŠ z trochu jiného úhlu

[Mirek Prýmek]

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

[Reklama]

[poiu]

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.

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.

Problém je podľa mňa inde, tu nie - ak má TS vykonať nekonečne veľa krokov (zmeniť nekonečne veľa číslic pri sčítaní), tak zaručene pri tomto vstupe nezastaví.

To máte pravdu, to skoro nič nezmení - stále mi tam chýba implikácia vychádzajúca z prvého kroku do ďalšieho kroku.

Co přesně ti tam chybí?

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.

Ale vlastne ani neviem, čo si mám predstaviť pod "x" v predpoklade. Podľa logiky, ak x je voľna, tak by to malo platiť pre všetky x. A ak nepotrebuje konkrétne viac ako "0" políčok pásky, tak nepotrebuje pásku a máme konečný automat, nie?

[Jakub Galgonek]

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

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

[Mirek Prýmek]

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

[Mirek Prýmek]

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

[Reklama]

[Jakub Galgonek]

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

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

[Jakub Galgonek]

Ale jedna bota tam nakonec přecejen je.

[poiu]

Ale jedna bota tam nakonec přecejen je.

Je to tá moja? Ak nie, tak aká a kde som robil ja chybu?

[Mirek Prýmek]

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í

[Mirek Prýmek]

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

[Radek Miček]

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

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

[Mirek Prýmek]

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?

[poiu]

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

Tak tu niekde mám asi chybu ja - ja som uvažoval konečnú pásku ako takú, ktorá sa dá zhora obmedziť nejakou dĺžkou, teda napríklad spomínaných 1024.

[Jakub Galgonek]

Ale jedna bota tam nakonec přecejen je.

Je to tá moja? Ak nie, tak aká a kde som robil ja chybu?

Tak ne, bota tam není. Jen je třeba tu větu dobře číst

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

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

Tak ona je to jen Riceho věta, ke které jsem přihodil pár předpokladů navíc, aby vypadala více k věci

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?

Kdybych uměl porovnat dva konkrétní programy, tak by rekurzivní byla (já pro jistotu předpokládal, že i znám jeden algoritmus z A).

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. Navíc je propastný rozdíl vědět, že algoritmus je realizovatelný na stroji s konečnou pamětí a znát kolik paměti mu stačí.

[Mirek Prýmek]

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]