No chápu to, co říkal Jakub: zastavení konečného stroje umím řešit hrubou silou jenom větším konečným strojem, takže pokud bych chtěl mít stroj, který by uměl řešit problém zastavení pro libovolný stroj, musí to být stroj s neomezenou pamětí. Je to stejné, jako bych chtěl mít stroj, který si bude umět zapamatovat libovolné přirozené číslo - taky by musel mít neomezenou paměť. Takovou podmínku splňuje jenom TS. Žádný fyzický stroj ji nikdy splňovat nebude.
Ne, Turingova veta je hlubsi. Ta mluvi o tom, ze neexistuje zadny TS, ktery by mohl analyzovat zastaveni nekonecne mnoziny TS. Kazdy ten TS predstavuje nejaky konecny popis. Z toho co rikas Turingova veta neplyne.
Je jasne, ze stroj, ktery resi problem zastaveni pro vsechny konecne stroje, musi mit nekonecnou pamet, protoze uz jenom je potrebuje do te svoji pameti nahrat. Ovsem stejne jako _jakykoli_ jiny algoritmus operujici na mnozine vsech TS! Napriklad muzeme zkonstruovat konecny TS, ktery nam pro zadany TS a jeho stav a vstup vypise nasledujici stav (simulator TS). To je priklad TS (tedy konecne veci), ktery existuje a operuje nad nekonecnou mnozinu vsech TS, a je mozne ho zkonstruovat.
Takze resit problem zastaveni neni nemozne jen proto, ze mnozina TS, nad kterou je ten problem definovan, je nekonecna. To samo o sobe nevadi.
Pokud ale podle tebe tvrzení o vlastnostnostech TS jsou vlastně tvrzení o množinách algoritmů, tak jak bysme do téhle řeči přeložili, že problém zastavení TS je nerozhodnutelný? Co nám tahle věta říká o vlastnostech jednotlivých algoritmů?
Vzhledem k tomu, ze je to negativni vysledek (neco neexistuje), tak o (existujicich) algoritmech to moc nevypovida, ale rika nam to, jake vlastnosti musi mit reseni nejakeho problemu (v tomto pripade, obecne reseni problemu zastaveni nemuze mit podobu algoritmu).
No nevím. Když už, tak je podle mě mnohem praktičtější vědět věci typu "k řešení problému zastavení fyzického stroje se čtyřmi stavy potřebuju fyzický stroj se stavy šestnácti".
To by bylo hezke vedet, bohuzel tyto problemy jsou velice tezke. Ja se treba domnivam, ze P=NP je urcita jemnejsi varianta podobne otazky.
Já tyhlety obecné věty moc nemám rád, když na nich lidi moc lpí. Když mám větu, že obecně nelze rozhodnout, jestli libovolné x z množiny X má vlastnost Y, tak to taky může znamenat, že to umím rozhodnout pro všechna x z X kromě jednoho prekérního prvku, který způsobuje problémy. A typicky to bude prvek obskurní, v praxi irelevantní...
Pointa je, ze to nejsou jednotlive prvky, ktere jsou nerozhodnutelne. To tvrzeni vypovida o nekonecnych mnozinach, a nelze ho tedy nejak "intuitivne" prevest na konecne mnoziny. Navic spousta lidi uz tady uvedlo desitky prikladu nerozhodnutelnych (nekonecnych mnozin) prvku, ktere v praxi irelevantni nejsou.
No a v praxi máme jenom omezené stroje. O to přeci právě jde. Máme jenom stroje, které si dokážou zapamatovat přirozená čísla až do velikosti K a větší už ne. Proto bych chtěl říct, co nám vlastně ona věta o TS vlastně říká o těch věcech, které reálně používáme.
Zase, nechapes, ze to neni jenom o nekonecnu. Timto zpusobem by jsi mohl shodit libovolne matematicke tvrzeni o nekonecne mnozine (coz jsou temer vsechna, protoze pro konecne si to muzeme dopocitat) jako neprakticke.
1675 Odpovědí
288893 Zhlédnutí