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.
V praxi se nedá dívat na počítač jako na konečný automat. Opravdu model Turingova stroje je mnohem vhodnější. 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. Pokud je něco turingovsky těžko vyčíslitelné (NP-hard nebo až dokonce nevyčíslitelné problémy), ani v reálném světě není jednoduché s takovými problémy pracovat (viz různé np-těžké optimalizační úlohy - rozvrhování, nebo třeba skládání bílkovin...). Proč tomu tak je? Protože prostor všech možných stavů už jen paměti je tak velký, že hrubá síla nejde použít. 2^1G stavů je prostě moc. A to nepočítám fakt, že váš počítač je připojený k internetu :-)
Opravdu se dá v reálném světě vidět, že model Turingova stroje a složitosti téměř přesně vystihuje těžkost problémů v reálném (a pravděpodobně konečném) světě. Pokud mi nevěříte, podívejte se do jádra Linuxu, to je on-topic :-) Většina operací nad datovými strukturami jádra je vývojáři tlačena na pokud možno optimální složitost.
Proto silně nesouhlasím s tvrzením, že Turingův stroj má nekonečně mnoho paměti, a proto je to akademický nesmyslný konstrukt.
1675 Odpovědí
288026 Zhlédnutí