Algoritmicky nerozhodnutelné problémy

[Samufaj]

Zdravím,
 tak vzhledem k tomu že tady jsou lidí co dokážou něco vysvětlit rcyhleji než já to vydoluju, tak tady další věc co nechápu:

Název: Eq-CFG (Ekvivalence bezkontextových gramatik)
Vstup: Dvě bezkontextové gramatiky G1,G2.
Otázka: Platí L(G1) = L(G2)? Generují obě gramatiky stejný jazyk?

---------
Ok chápu, že budu-li tuto úlohu řešit tak, že budu porovnávat generované slova z dvou gramatik, nikdy se výpočet nezastaví. Jenže, když vstup jsou dvě bezkontextové gramatiky, tak přece existuej algoritmus takový, který nebude otrocky generovat slova gramatik, ale podívá se jak jsou ty gramatiky sestrojeny. A z toho už se přece musí dát rozhodnout jesli jsou stejné, ne?

-------------
Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?
---------
Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

[Reklama]

[TTTTTTT]

U některých konkrétních gramatik můžeš kouknout, jestli jsou stejné nebo ne a zjistíš to. Ale nelze to u všech. Dokonce ani nedokážeš o (obecné) gramatice rozhodnout, jestli generuje všechna možná slova - dá se to převést na halting problém.

Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

Pro některé TS a vstupy to dokážeš říct. Ale není možné udělat funkci, která by dostala na vstup libovolný TS a k němu vstup a rozhodla, zda se zastaví.

Zkus kouknout na http://www.root.cz/clanky/co-je-to-nenaprogramovatelne/

[Jakub Galgonek]

-------------
Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?
---------
Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

Tohle se asi nejlépe vysvětluje pomocí částečně rekurzivních funkcí, ale nevím, zda vám o nich někdo říkal. Nejlepší asi bude vysvětlit to neformálně pomocí programu v nějakém programovacím jazyce.

Představ si, že existuje program halt(code, input), který vrací true, pokud se program zapsaný v code nad vstupem input zastaví, jinak vrací false. Pak můžeš napsat následující program:

Kód: [Vybrat]

contradiction(code)
{
  if(halt(code, code))
    while(true);
  else
    return;
}

Tento program otestuje, zda se program zapsaný v code nad vstupem code zastaví, a pokud ano, zacyklí se. V opačném případě skončí. Co se stane, pokud programu contradiction dáš na vstup jeho vlastní kód? Pak pokud se contradiction nad vstupem contradiction zastaví, pak se musí contradiction nad tímto vstupem zacyklit. A naopak, pokud se contradiction nad vstupem contradiction nezastaví, pak se musí contradiction zastavit. Což je v obou případech spor a tedy žádný takový program halt nemůže existovat.

[zboj]

HP: Viz Cantorova diagonální metoda (teorie množin  ) - důkaz je triviální.

[student]

Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?
---------
Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

Celkovo je problem vseobecne riesenie, nie konketne jednoduche pripady.

Vysvetlene na priklade: mozes napriklad hladat najmensie cislo s nejakou vlastnostou a take cislo nemusi existovat, tak zacnes od 1, budes skusat stle vacsie a nikdy neskoncis. Napriklad Collatz sa domnieval, ze ked sa s cislom bude opakovat HOTPO, tak sa vzdy pride k cislu 1. Ty si tym nemozes byt isty a spravis Turingov stroj, ktory bude hladat najmensie cislo, ktore po zopakovani krokov da iny cyklus ako 4-2-1. Ked sa Collatz mylil, tak sa TS zastavi; inak sa TS nezastavi. Je to taky jednoduchy predpis a aj tak to tam nie je vidiet a nikto to zatial nevie.
HOTPO=delis 2, ked je vstup delitelny 2; ked delitelny nie je, tak vynasobis 3 a pricitas 1.

To hladanie najmensieho cisla je zakerne, spaja sa s nim aj vyssie spominany halting problem. Tam v podstate hladas najmensi pocet krokov, po ktorych sa Turingov stroj zastavi. A on sa niekedy nezastavi (kod od Jakuba Galgonka).

[Reklama]

[Karel]

-------------
Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?
---------
Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

To je lepší ukázat na příkladě. Máte stroj, který počítá číslo Pi. Vždy vypočítá další číslici a zastaví se ve chvíli, kdy poslední vypočtené číslice budou odpovídat zadané sekvenci (to je to slovo w).

Příklad 1: hledám sekvenci w = "14"
Stroj vygeneruje 3,14 a pak se zastaví.

Příklad 2: hledám sekvenci w = "75"
Stroj vygeneruje 3,141592653589793238462643383279502884197169399375 a pak se zastaví.

Příklad 3: hledám sekvenci w = "12345"
Tak co, zastaví se někdy, nebo ne? Protože se u čísla Pi nezačne sled číslic opakovat, tak teoreticky pokud budu počítat do nekonečna, tak by se 12345 objevit mělo. Nebo ne?

Příklad 4: hledám všechny sekvence sestavené jako kombinace w číslic. Pro w = 1 se to zastaví, každá číslice se tam vyskytuje. Ale co třebas w = 5? Zastaví se to pro všechny kombinace pěti číslic? Není jich mnoho, jen sto tisíc. Není mezi nimi ale nějaká, která se v čísle Pi nikdy neobjeví?

Podstatné je, že příklady nejsme schopni ověřit algoritmicky a prostě to musíme zkusit. Což u některých úloh znamená časové nároky přesahující stáří vesmíru a vyžaduje uchovat více bitů informací, než je atomů ve vesmíru. Ten příklad s paradoxem "zastaví se jen pokud se nezastaví" je lepší, protože je neprůstřelný. Ale osobně dávám přednost praktickým příkladům, které se dají naprogramovat a spustit. Člověk pak týden chodí kolem počítače, kouká a pak nakonec konstatuje, že to vážně tak snadné nebude.

Jo a ještě bacha na ty definice. Mluví se obecně, tedy že existuje takový stroj M a takové slovo w, pro které to neumíte rozhodnout. Samozřejmě existují mraky konkrétních strojů a slov, pro které to rozhodnete snadno.

[Samufaj]

Děkuji za odpověď, teď už to chápu, nicméně v příkladech který Halting problem vysvětloval byly funkce

Zastavi( kód_funkce, vstup )

Automaticky předpokládám, že když tam jde kód funkce, tak se tím myslí kód funkce, tj. že se dá kód funkce analyzovat a rozhodnout to z kódu, ne až ze zpracování vstupu tím kódem. Nicméně na tom příkladě s výpočtem Pi už je to jasné, tam se to nedá rozhodnout ani z kódu funkce, takže děkuji za tento příklad

[Mirek Prýmek]

Ten příklad s paradoxem "zastaví se jen pokud se nezastaví" je lepší, protože je neprůstřelný.

Mně právě vždycky tenhle důkaz přišel divný. Nerozumím tomu, proč se nedá říct, že ten spor dokazuje, že nejde udělat takový TS tímhle způsobem. Jak z tohodle důkazu plyne, že nejde udělat jiným způsobem, mi vždycky bylo záhadou, ale nikdy mě to nerajcovalo natolik, abych se na to někoho ptal nebo se na to snažil přijít

Jak ten důkaz dokazuje, že nemůže existovat třeba TS, který když skončí v jednom stavu, tak se posuzovaný TS zastaví a když v jiném stavu, tak se nezastaví? Možná je to debilní otázka, buďte prosím tolerantní, tyhle věci mě nikdy moc nebavily

Je to tak, že se dá dokázat, že kdyby takový TS existoval, tak by musel existovat i ten, o kterém víme, že existovat nemůže?

[Jenda]

Děkuji za odpověď, teď už to chápu, nicméně v příkladech který Halting problem vysvětloval byly funkce

Zastavi( kód_funkce, vstup )

Automaticky předpokládám, že když tam jde kód funkce, tak se tím myslí kód funkce, tj. že se dá kód funkce analyzovat a rozhodnout to z kódu, ne až ze zpracování vstupu tím kódem.

To je jedno. Respektive zpracování (spuštění v nějakém sandboxu) může být jednou z metod analýzy kódu.

[ttt]

Mně právě vždycky tenhle důkaz přišel divný. Nerozumím tomu, proč se nedá říct, že ten spor dokazuje, že nejde udělat takový TS tímhle způsobem. Jak z tohodle důkazu plyne, že nejde udělat jiným způsobem, mi vždycky bylo záhadou, ale nikdy mě to nerajcovalo natolik, abych se na to někoho ptal nebo se na to snažil přijít

Jak ten důkaz dokazuje, že nemůže existovat třeba TS, který když skončí v jednom stavu, tak se posuzovaný TS zastaví a když v jiném stavu, tak se nezastaví? Možná je to debilní otázka, buďte prosím tolerantní, tyhle věci mě nikdy moc nebavily

Je to tak, že se dá dokázat, že kdyby takový TS existoval, tak by musel existovat i ten, o kterém víme, že existovat nemůže?

Ten důkaz pracuje přesně s takovým TS, který ty popisuješ (tj. TS skončí výpočet v koncovém stavu, pokud se posuzovaný TS zastaví, a v nějakém nekoncovém, pokud se posuzovaný TS nezastaví). Klidně by mohl začínat slovy "Nechť existuje <TS, který jsi popsal>.

Ty TS, které se zastaví a nezastaví když něco, jsou vytvořené v rámci důkazu - dá se na nich ukázat, že by ten "vstupní" TS musel skončit jak ve stavu ANO, tak ve stavu NE, což je spor.

[Jakub Galgonek]

Nerozumím tomu, proč se nedá říct, že ten spor dokazuje, že nejde udělat takový TS tímhle způsobem. Jak z tohodle důkazu plyne, že nejde udělat jiným způsobem, mi vždycky bylo záhadou, ale nikdy mě to nerajcovalo natolik, abych se na to někoho ptal nebo se na to snažil přijít

Ten důkaz ale nepředpokládá žádný konkrétní způsob. Pro spor prostě jen předpokládáš, že máš TS, který umí řešit halting problem.

Je to tak, že se dá dokázat, že kdyby takový TS existoval, tak by musel existovat i ten, o kterém víme, že existovat nemůže?

Ten důkaz je o tom, že pokud by existoval TS řešící halting problem, tak jde upravit na TS, který se zastaví, právě když se nezastaví, což je spor.

[Mirek Prýmek]

Ten důkaz je o tom, že pokud by existoval TS řešící halting problem, tak jde upravit na TS, který se zastaví, právě když se nezastaví, což je spor.

Jasně, no, šel by na něj převést, tak jsem to myslel. Stačilo by vlastně před ten patřičný akceptující stav vrazit "smyčku" a je to. Njn, tak žádná velká záhada, škoda

[Tomaskom]

Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

To co bylo uz zmineno, dukaz sporem:
https://www.youtube.com/watch?v=92WHN-pAFCs