Vycislitelnost je veda krasna, lec jeste v ni zustava nekolik problemu nevyresenych. Snad se to podari rozlousknout v tomto stoleti.
Diky za pekny clanek. :-)
Mne to teda vyčíslitelnost nepřipomíná. Když už tak složitost (redukce všech problémů na problém zastavení, který nelze řešit a proto mají všechny uvedené úlohy stejnou složitost NP), ale spíš docela obyčejné formální jazyka a gramatiky typu 0 v Chomského hierarchii... Vyčíslitelnost mi přijde jako podstatně větší věda.
Halting problem je problem vycislitelnosti - staci si zajit na zakladni prednasku z ni. Ve slozitosti se jiste tak dukladne nerozebira, protoze z hlediska slozitosti neni az tak zajimavy (naproti tomu ve vycislitelnosti se pak vede mimo jine i teorie kolem relativizovaneho halting problemu atd.). Kdyz zminujes jazyky typu 0 a vubec Chomskeho hierarchii, tak ty problemy jsou ovsem provazane - v teorii gramatik se halting problem vynori opet v podobe problemu rekurzivnich a rekurzivne spocetnych jazyku.
Slozitost se zabyva totalne vycislitelnymi funkcemi, coz problem zastaveni neni (neni totalni). I NP problemy jsou totalne vycislitelne, a proto z hlediska vycislitelnosti nezajimave.
Popularizacni clanky o teoreticke informatice jsou jiste zajimavym ozivenim, skoda jen, ze ROOTa ctou z velke casti lide, kteri se s problematikou potkali ve skole mnohem podrobneji.
Dovolil bych si podotknout, ze mezi NP a problemem zastaveni (ktery neni vycislitelny) je priblizne stejny rozdil, jako mezi zidli a kridou. Predstavou, ze je to totez, by rozhodne nekdo, kdo netrivialni dobu pobyval na slusne skole v oboru informatiky, nemel trpet.
Jsi vedle jak ta jedle. Slysel jsem z tajnych zdroju, ze na Mendelu uz dokazali resit problem zataveni v NP. Dosali za to nejake penize a ted za ne stavi novou budovu. Ja to vim, ja jsem bydlel kousek od Mendelu, tam se nic neutaji. :)
Letos jsem promoval z informatiky na Mendelu, takže můžu potvrditm že tento problém jsme vyřešili a za utržené peníze se staví nová budova (5 pater podzemních garáží a protiatomový kryt, 8 pater nad zemí - horní polovina "Top secret" výzkumná část). CIA prostě platí "very well"...
A dávejte si bacha, velký bratr se dívá
> (redukce všech problémů na problém zastavení
> ,který nelze řešit a proto mají všechny uvedené
> úlohy stejnou složitost NP)
Velmi vtipne :)
Mate na mysli skutecne NP? Nemel jste temi "problemy ktere nejdou resit" na mysli tridu problemu NP-uplnych? (ale i tak je to scestne).
NP je podle Vas trida problemu ktere nejdou resit? Spise se jedna o tridu problemu ktere se daji resit nedeterminsiticky v polynomialnim case, ne? Jak s touto tridou problemu souvisi halting problem, ktery nejen ze se neda resit ani nedeterministicky v polynomialnim case, on je proste nerozhodnutelny.
No, maly ulet se obcas stane kazdemu, ale mel jsem za to, ze jste "head of Institute for Informations and Informatics Mendel University", coz pokud je pravda, tak jste se, s dovolenim, ponekud ztrapnil.
Mr. Milan Sorm
head of Institute for Informations and Informatics
Mendel University of Agriculture and Forestry
5 Zemedelska, Brno
Europe, Czech Republic
