Kazdy z nas jiste intuitivne tusi co je algoritmus, ale existuje nejaka definice, ktera presne vymezuje co je a co neni algoritmus?
Intuitivne je algoritmem kazda mnozina pravidel, ktera, po konecnem poctu kroku, vrati vysledek, ktery ocekavame. Problem exaktni definice algoritmu vyvstava v okamziku potreby dokazani existence resp. neexistence reseni.
Jednou z moznych definic algoritmu je Churchova teze:
\"Kazdy proces, ktery lze intuitivne nazvat algoritmem, se da realizovat na Turingove stroji.\"
Churchova teze tedy srovnava dva pojmy: \"algoritmicky resitelny\" a \"resitelny Turingovym strojem\". Vzhledem k tomu, ze opet pojem \"algoritmicky resitelny\" je definovan pouze intuitivne, nelze ji dokazat.
Lze vsak nalezt mnoho argumentu potvrzujici jeji platnost:
- krome TM /Turing Machine = Turingovy stroje/ bylo vymysleno mnoho dalsich vypocetnich systemu, ktere jsou vzajemne ekvivalentni ve vypocetni sile.
Jako priklad lze uvest lambda kalkul, while-programy nebo Postovy systemy.
- doposud neni znam zadny algoritmus, ktery by nebylo mozne zrealizovat na TM
Turingovy stroje
jsou pojmenovany podle matematika Alana Turinga, ktery jiz v roce 1936 tento stroj definoval. Pozdeji na jeho pocest byl stroj pojmenovan jako Turinguv stroj. Podnetem k exaktni definici vypoctoveho stroje byla snaha rozdelit problemy na resitelne /vycislitelne/ a neresitelne.
Zaroven bylo nutne vymezit elementarni pravidla jimiz se bude TM ridit:
- vypocet musi byt reprezentovatelny konecnym zpusobem
- kazdy krok musi byt mechanicky realizovatelny
Jak takovy TM vypada?
Kazdy TM obsahuje:
- konecnou mnozinu stavu, do kterych se lze po vykonani libovolneho kroku dostat
- konecnou mnozinu symbolu, ktere je mozne zapisovat na pasku
- pasku, ktera je rozdelena na policka a ta obsahuji vzdy nektery ze symbolu. Paska je jednosmerne nekonecna
- hlavu, ktera v zavislosti na provedenem kroku a aktualnim stavu cteneho symblou z pasky se muze pohybovat bud vpravo nebo vlevo po pasce a zapisovat resp. prepisovat symboly
Vypocet TM:
Vypocet startuje v pocatecnim stavu a hlava snima policko obsahujici levy kraj pasky. Kazdy krok zavisi na aktualnim symbolu, kde je hlava, a na aktualnim stavu. TM muze zmenit stav, prepsat symbol a posunout hlavu doleva nebo doprava.
Stroj akceptuje vstupni slovo prave kdyz jeho vypocet prejde do akceptujiciho stavu resp. zamita vstupni slovo prave kdyz jeho vypocet prejde do zamitajiciho stavu. Stroj samozrejme nemusi do jedno z vyse zminenych stavu dorazit a potom rikame, ze cykli.
O Turinguve stroji, ktery vzdy zastavi /skonci v akceptujicim nebo zamitajicim stavu/ rikame, ze je uplny.
Mozne modifikace TM:
Turingovy stroje lze rozsirit, avsak jejich vypocetni sila zustava stejna. Rozsirenim si v podstate pouze usnadnujeme implementaci a usnadnujeme citelnost.
- nedeterministicky TM
rozdil oproti klasickemu TM je moznost rozhodovat se o pokracovani vypoctu. Nedeterministky stroj neni vazan pouze jednim pravidlem nad danym aktualnim stavem, ale muze volit pokracovani sveho vypoctu. Nedeterministicky stroj akceptuje prave kdyz existuje vypocet koncici v akceptujicim stavu. Prestoze se zda, ze toto rozsireni nam dava mnohonasobne silnejsi vypoctovy stroj neni tomu tak. Lze dokazat, ze ke kazdemu nedeterministickemu TM existuje ekvivalentni deterministicky TM
- TM s obousmerne nekonecnou paskou
- TM s vice paskami
- TM s oddelenou vstupni paskou
- TM se dvema zasobniky
- TM se dvema pocitadly
Univerzalni TM a kodovani TM
Turinguv stroj lze jednoznacne zakodovat napriklad do binarni podoby, coz bych zde nerad rozepisoval, jelikoz je to hodne psani a zaroven se tim stava TM necitelnym :) Proto pro dalsi popis lze TM jednoznacne zakodovat.
Diky zakodovani TM dokazeme sestrojit stroj, ktery pokud na svuj vstup dostane zakodovany TM a jeho vstup, dokaze simulovat jeho vypocet nad danym vstupem a akceptuje prave kdyz puvodni zakodovany TM by akceptoval svuj vstup.
Rozhodnutelnost
Rozhodnutelny problem - problem je rozhodnutelny, kdyz pro kazdy prvek z jeho mnoziny dokazeme urcit zda splnuje danou vlastnost nebo ne, tj. existuje TM ktery akceptuje prvek majici hledanou vlastnost resp. zamitne prvek pri nesplneni vlastnosti
Semirozhodnutelny problem - neboli castecne rozhodnutelny problem je takovy, prot ktery dokazeme nalezt TM, ktery akceptuje kazdy prvek z problemu pokud splnuje vlastnost a zamita nebo cykli na prvcich nesplnujicich danou vlastnost
Nerozhodnutelny problem - prave kdyz neni rozhodnutelny
Pri dukazu rozhodnutelnosti nekterych problemu lze vyuzit metody diagonalizace, redukce atd.
Ja se zde zamerim na redukci. Redukce vychazi z jednoducheho predpokladu:
Pokud mame problem o kterem vime, ze je rozhodnutelny/semirozhodnutelny/nerozhodnutelny, a redukujeme /prevedeme/ ho na problem, ktery resime, obdrzime rozhodovaci mechanismus pro hledany problem. Pokud bychom znali jeho reseni znali bychom i reseni redukovaneho problemu. Redukce samozrejme musi zachovavat prislusnost prvku daneho problemu.
A zaver?
Chtel jsem ukazat, ze bez zakladnich znalosti v CS neni mozne programovat. Nepredpokladam, ze pro kazdeho programatora je nutne znat exaktni definici algoritmu, kterou snad ani prisne exaktne ani dokazat nelze. Presto vsak je dulezite vedet o vecech jako je vycislitelnost, slozitost, rozhodnutelnost a znat alespon nektery z vypocetnich systemu, pomoci kterych muzeme dokazat nektere z vlastnosti algoritmu.
Proc jsem vybral TM? Protoze se o nich moc nemluvi, prestoze to je naprosto genialni vec, kterou vymysleli driv nez pocitace a i v dnesni dobe nam ma co rict. Dalsim podstatnym faktem je to, ze TM uz mam trosku zazity oproti v soucasne dobe studovanym while-programum a lambda-kalkulum :)
Nesnazil jsem se obsahnout vsechno vedeni, ale vybrat pouze to nejdulezitejsi a nejpodstatnejsi k pochopeni problemu.
Zamerne jsem se vyhnul ekvivalenci s mnozinama jazyku, kterym jsem se venovat nechtel. Preskocil jsem tez zakladni veci jako automaty, regularni jazyky, regularni vyrazy atd, coz je sice zaklad ale prave vyjmutim ekvivalence s jazyky sem se snad nedopustil tak velkeho zlocinu :)
Ocekavam zajimavou diskuzi, kterou predcim neologisma :-]
Cerpano ze skript a vedomosti posbiranych na prednaskach: Formalni jazyky a automaty /M.Kretinsky/ a Vycislitelnost a slozitost /L.Brim/ vse na FI MUNIMiS
