Univerzalita a robustnostľ^Výpočtový model ^ ^ Univerzalita a robustnost: 11 Výpočtový model HTuringov stroj Hchurchova Turing Bllniverzálný Turin IB110 Podzim 2010 1 Univerzalita a robustnostľ^Výpočtový model ^ ^ Jednoduchý výpočtový model Hľadáme čo najjednoduchší počítač (výpočtový model), ktorý je schopný realizoval! všetký algoritmické výpočty. Prečo? ■ aký najjednodučhší model je sčhopný realizovat! všetký výpočtý? ■ obečnost výsledkov o praktičkej neriešitelnosti a nerozhodnutelnosti ■ presna formuláčia a formálne dokazý tvrdení týkajUčičh sa praktičkej neriesitelnosti a nerozhodnutelnosti IB110 Podzim 2010 2 Univerzalita a robustnosť^Výpočtový model ^ ^ Jednoduchý výpočtový model - dáta data = retazce symbolov ■ poCet rôznych symbolov potrebných na zakódovanie reťazcov je koneCny (podobne ako na zakódovanie všetkých čísel nam stačí v desiatkovej resp. binárnej sústave 10 resp. 2 číslice) ■ data môzeme zapisoval! na jednorozmernú pásku, ktora obsahuje polícka; na kazdom polícku je zapísany jeden symbol, ktory je prvkom vstupnej abecedy Linearizacia datovych struktUr ■ linearizacia zoznamu ■ linearizacia dvojrozmerneho pol'a, matice ■ linearizacia stromu Dynamicke dútove struktury a neohranicenost jednosmernej pasky IB110 Podzim 2010 Univerzalita a robustnosť^Výpočtový model ^ ^ Jednoduchý výpočtový model - riadiaca jednotka Univerzalita a robustnost;S=-Výpočtový model ^ ^ Jednoduchý výpočtový model - riadiaca jednotka ■ výpočet je realizovaný riadiacou jednotkou ■ riadiaca jednotka je vZdý v jednom z konečne vel'a rožných stavov (stav zodpovedá inštrukcii algoritmu) ■ riadiaca jednotka vždý snímá práve jedno políčko jednorozmernej paský (hodnota, s ktorou manipuluje inštrukcia algoritmu) ■ atomicke akcie ■ precitanie sýmbolu z polícka paský ■ zapis sýmbolu na polícko paský ■ posun o jedno polícko na paske ■ zmena stavu riadiacej jednotký ■ zavislost zmený na aktualných hodnotach IB110 Podzim 2010 5 Univerzalita a robustnost;S=-Výpočtový model ^ ^ Jednoduchý výpočtový model - základné operácie jeden krok výpočtu ■ prečítanie symbolu ■ podl'a aktuálneho stavu riadiacej jednotky a prečítaneho symbolu sa výkonía ■ zmena stavu ■ zapis symbolu ■ posun o jedno políčko vpravo alebo vľavo Turingov stroj Alan Turing, 1936 IBllO Podzim 2010 6 Univerzalita a robustnosť^Turingov stroj ^ ^ Univerzalita a robustnost: ■Výpočtový mo< 2 Turingov stroj Bchurchova Tur Buniverzainý Tu IB110 Podzim 2010 7 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj Turingov stroj (TS) pozostáva z ■ (konečnej) mnoZiny stavov ■ (konečnej) abecedy symbolov ■ nekonečnej pásky rozdelenej na políčka ■ čítacej a zapisovacej hlavy, ktora sa pohybuje po paske a sníma vZdy 1 pol íčko pasky ■ prečhodoveho diagramu IB110 Podzim 2010 8 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj - prechodový diagram Prechodový diagram ■ orientovaný graf ■ vrcholy grafu su stavý TS ■ hrana z vrcholu s do vrcholu t reprezentuje prechod a je oznaCená dvojicou tvaru (a/b, L) alebo (a/b, R); ma je sýmbol, ktorý hlava TS z paský čita (tzv. spínac) ■ b je sýmbol, ktorý na pásku zapisuje ■ L resp. R urcuje smer pohýb hlavý doľava resp. doprava ■ pozadujeme, abý diagram bol jednoznacný (deterministický Turingov stroj), tj. zo stavu nesmá výchadzat dve hraný s rovnakým spínacom ■ jeden zo stavov je oznacený ako štartovný (pociatocný) stav (oznacený sípkou) ■ niektore zo stavov sá oznacene ako koncove stavý (oznacene výrazným ohranicením) IB110 Podzim 2010 9 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj - výpočet Krok výpočtu prechod z s do t označený (a/b, L) v prechodovom diagrame ak riadiaca jednotka TS je v stave s a hlava čita sýmbol a, tak hlava prepise sýmbol a symbolom b, posunie sa o 1 políčko doľava a stav riadiacej jednotky sa zmení na t (analogicky pre (a/b, R) a pohyb vpravo) Výpocet Výpocet zacína v pociatocnom stave na najl'avejsom neprazdnom polícku paský. Výpocet prebieha krok po kroku tak, ako predpisuje prechodový diagram. Výpocet sa zastaví ked' dosiahne niektorý z koncových stavov. IB110 Podzim 2010 10 Univerzalita a robustnosť^Turingov stroj ^ ^ Univerzalita a robustnosť^Turingov stroj ^ ^ Univerzalita a robustnosť^Turingov stroj ^ ^ Simulátor Turingových strojov http://www.fi.muni.cz/ xbarnat/tafj/turing IB110 Podzim 2010 14 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj ako algoritmus i Turingov stroj môžeme chápal; ako počítač s jedným, fixovaným programom ■ softwarom je prechodový diagram; hardwarom je riadiaca jednotka a paska ■ jednotlive TS sa líSia iba svojim softwarom, preto často hovoríme o programovaníTuringovho stroja IB110 Podzim 2010 15 Univerzalita a robustnostľ^Turingov stroj ^ ^ Turingov stroj ako algoritmus i Turingov stroj môžeme naprogramoval! tak, abý riesil rozhodovací problíem ■ pre rozhodovací problem P, ktorého množina vstupných instancií je kodovana ako mnozina linearizovaných retazcov, konstruujeme Turingov stroj M s pociatocným stavom s a dvoma koncovými stavmi YES a NO pre každý vstup X, ak M zacne výpočet v stave s na najl'avejsom symbole reťazca X, tak M skončí výpočet v stave YES a NO v zavislosti na tom, či výstupom P pre X je „Áno" alebo „Nie" IB110 Podzim 2010 16 Univerzalita a robustnost^Turingov stroj ^ ^ Turingov stroj ako algoritmus Turingove stroje môžu být! naprogramovane aj pre riesenie inýčh nez rozhodovačíčh problemov. V takomto prípade predpokladíme, ze keď sa TS zastaví (prejde do končoveho stavu), tak výstupom je retazeč zapísaný na paske medzi dvoma spečialnými znakmi (napr. !) Ak sa výpočet zastaví a na paske je iný počet sýmbolov ! ako 2, čhapeme výpočet ako neukončený (tj. ako výpočet, ktorý čýklí donekonečna). IB110 Podzim 2010 17 Univerzalita a robustnosť^Churchova Turingova hypotéza ^ ^ Univerzalita a robustnosť ■Výpočtový model HTuringov stroj ^| Churčhova Turingova hýpoteza Buniverzílný Turingov stroj IB110 Podzim 2010 18 Univerzalita a robustnosť^Churchova Turingova hypotéza ^ ^ Churchova Turingova hypotéza Ake probiemý sU riesitel'ne pomocou vhodne naprogramovaneho TS? Churchova Turingova hýpoteža Každý algoritmický probiem, pre ktorý existuje program v nejakom programovacom jažýku výssej úrovne a je riesitel'ný na nejakom hardwaru, je riesitel'ný aj na Turingovom stroji. Preco hýpoteža? CT hýpoteža formuluje vžtah medži dvoma konceptami: ■ matematický presný pojem riesitel'nosti na Turingovom stroji a ■ neformalný koncept algoritmickej riesitel'nosti, ktorý je postavený na pojmoch „programovací jažýk výssej urovne", „program v programovacom jažýku" IB110 Podzim 2010 19 Univerzalita a robustnosť^Churchova Turingova hypotéza ^ ^ Argumenty pre Churchovovu Turingovu hypotézu CT hypotézu formulovali v 30-tych rokoch nezávisle Alonso Church a Alan Turing. Od tej doby bolo navrhnutých mnoZstvo „univerzálnych" modelov (absolútnych, schopných riesit všetky mechanicky riešitefné problémy) ■ Turingove stroje (Alan Turing) ■ lambda kalkulus (Alonso Church) ■ produkcne systemy (Emil Post) ■ rekurzívne funkcie (Stephen Kleene) ■ kvantove poatace Fakt O vsetkych navrhnutych formalizmoch je dokazane, ze su ekvivalentne v tom zmysle, ze urcuju zhodnu triedu algoritmicky riesitel'nych problíemov. IB110 Podzim 2010 20 Univerzalita a robustnost^Churchova Turingova hypotéza ^ ^ Dosledky Churchovej Turingovej hypotézy ■ extremne výkonne superpočítače nie su silnejsie nez male počítače s jednodučhým programovačím jazýkom; za predpokladu neohraničeneho času a velkosti pamate dokazu obidva riesit tie iste algoritmičkíe problíemý ■ pojem algoritmičký riesitelneho (rozhodnutelneho) problemu je robustný, tj. je nezavislý na konkretnej volbe výpočtoveho modelu resp. programovačieho jazýka CT hýpoteza podporuje spravnost definíčie nerozhodnutelnýčh problíemov IB110 Podzim 2010 21 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Univerzalita a robustnosť ■Výpočtový model HTuringov stroj Hchurchova Turingova hýpoteza Modifikácie Turingovho stroja Huniverzalný Turingov stroj IB110 Podzim 2010 22 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Modifikácie Turingovho stroja Argumentom podporujUčim CT hypotezu je aj robustnost! TS. Modifikačie ■ TS, ktory ma po skončen í vypočtu zap ísany na paske len vstupny a vystupny ret!azeč ■ TS s jednosmerne nekonečnou paskou ■ TS s dvojrozmernou paskou TS s konečnym počtom pasok (kazda mas svoju č ítačiu/zapisovačiu hlavu) Fakt Vsetky uvedene modifikačie su vzajomne ekvivalentne Dokaz tečhnikou simulačie: ukazeme, ze vypočet jedneho zariadenia sa da simulovat! na druhom zariaden í a naopak IB110 Podzim 2010 23 Univerzalita a robustnosť^Modifikácie Turingovho stroja ^ ^ Programy s počítadlami (Counter Programs, CP) ■ programý manipuluju s prirodzenými císlami ulozenými v premenných ■ tri elementárne operacie X — 0 priradí premennej hodnotu 0 X — Y + 1 X — Y — 1 ak hodnota Y je 0, tak X priradí hodnotu 0 ■ jeden elementarný riadiaci príkaz ifX = 0 goto G, kde X je premenna a G je navestie pripojene k príkazu IB110 Podzim 2010 24 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Programy s počítadlami - príklad U — 0 Z — 0 if X = 0 goto G X - X - 1 V - Y + 1 V - V-1 if V = 0 goto A V - V-1 Z - Z+1 if U = 0 goto B výkonanie goto G je ekvivalentom íspesneho ukoncenia výpoctu IB110 Podzim 2010 25 Univerzalita a robustnost;>Modifikáčie Turingovho stroja ^ ^ Turingove stroje a programy s počítadlami TS manipuluju so sýmbolmi, PS s císlami je mozna ich vzajomna simulacia? IB110 Podzim 2010 26 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Simulacia TS na CP obsah paský —> císla pre jednoduchost' predpokladajme, že abeceda TS mía desat' žnakov žnaký ocíslujeme a retažce žnakov prevedieme na císla Príklad #-0 !-1 *-2 a - 3 b - 4 c - 5 d - 6 e - 7 f - 8 g - 9 retazec ... ## ab * eb !# aga ## ... v ktorom je snímaný symbol b, prevedieme na dvojicu čísel 3427 a 393014 IB110 Podzim 2010 27 Univerzalita a robustnost;>Modifikáčie Turingovho stroja ^ ^ Simulacia TS na CP zmena sýmbolu na paske zmena poslednej císlice v druhom císle Príklad ak symbol b prepíšeme symbolom g, tak číslo 393014 sa zmení na 393019, PC pripočíta 5 krat hodnotu 1 posun hlavý doprava prve císlo výnasobíme 10 a pripocítame k nemu poslednu císlicu druheho císla druhe c íslo výdel íme 10 (celoc íselne) analogický pre posun hlavý doľava zmena stavu stavu TS zodpoveda skupina instrukci í CP; zmena stavu je simulovana skokom na novu skupinu instrukci í (pr íkaz goto) CP, ktorý simuluje TS, ma len dve pocítadla! IB110 Podzim 2010 28 Univerzalita a robustnost;>Modifikáčie Turingovho stroja ^ ^ Simulácia CP na TS císla <— sýmbolý hodnota kazdej premennej je zapísaná ako postupnost! sýmbolov = císlic; jednotlive hodnotý su vzajomne oddelene specialným sýmbolom (napr. *) instrukcie <— stavý kazdej instrukcii programu zodpoveda skupina stav TS, výkonenie instrukcie je simulovane prechodom do príslusneho stavu a realizacia postupnosti krokov, ktoríe potrebníým spôosobom upravia obsah premennej IB110 Podzim 2010 29 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Simulácie ako redukcie Ak model A simuluje model B, tak mame redukciu medzi týmito modelmi. Redukcia prevedie program modelu A a jeho vstup X na program modelu B a jeho vstup Y. CT hýpoteza ukazuje, ze nase uvahý pri konstrukcii redukcií boli korektne. IB110 Podzim 2010 30 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Simulacie ako redukcie Ak model A simuluje model B, tak mame redukčiu medzi týmito modelmi. Redukčia prevedie program modelu A a jeho vstup X na program modelu B a jeho vstup Y. CT hýpoteza ukazuje, ze nase uvahý pri konstrukčii redukčií boli korektne. Príklad nerozhodnutefnost problému zastavenia ^ formálne dokážeme nerozhodnutefnost problému pre TS ^ podl'a CT hypotezy problám zastavenia nemôže byt rozhodnutelný ani pre žiaden iná programovací jazyk vyššetj úrovne (je ekvivalenty TS!) Fenomen algoritmus, ktoreho vstupom je iný algoritmus IB110 Podzim 2010 30 Univerzalita a robustnostľ^Univerzálny Turingov stroj ^ ^ Univerzalita a robustnosť Výpočtový model Turingov stroj Churchova Turingova hýpo Modifikácie Turingovho str Univerzálny Turingov stroj IB110 Podzim 2010 31 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzainy algoritmus jeden z najdolezitejsích dôsledkov CT hýpotezý Existencia univerzalneho algoritmu, ktorý ma schopnost! choval! sa ako akýkoľvek iný algoritmus. ■ vstupom pre univerzýlný algoritmus je popis akehokol'vek algoritmu A a akehokol'vek jeho vstupu X ■ univerzýlný algoritmus simuluje výpocet A na X m výpocet univerzalneho algoritmu sa zastaví prýve ak výpocet A na X sa zastaví; ako výstup poskýtne univerzalný algoritmus presne tý istu odpoved' ako poskýtne A na X ak fixujeme algoritmus A a meníme X, tak univerzálny algoritmus sa chova presne ako algoritmus A IB110 Podzim 2010 32 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzálny algoritmus ■ moze být! vstupom univerzílneho algoritmu program v akomkoľvek programovacom jazýku? ■ výuzijeme CT hýpotezu a poznatok o ekvivalencii vsetkých znamých formalizmov pre popis algoritmov ■ ku konstrukcii univerzílneho algoritmu potrebujeme len jazýk L1, v ktorom napíšeme program U pre univerzalný algoritmus; program akceptuje ako vstup ľubovoľný program napísaný vo fixovanom konkríetnom jazýku L2 i program U je nezívislý na výbere modelu, pretoze podľa CT hýpotíezý | môze být! napísaní v akomkoľvek jazýku ] dokaze simulovat! akýkoľvek algoritmus popísaný v akomkoľvek jazýku Vhodným kandidátom pre jazyky L1 a L2 sú Turingove stroje. IB110 Podzim 2010 33 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzainy Turingov stroj ■ potrebujeme popísať Turingov stroj ako linearný retažec nad konecnou abecedou sýmbolov ■ stací linearižovat prechodový diagram ■ mark ** mark YES (#/#, L) * mark movea {a/#, R) * movea movea {a/a/, R) *... ■ linearižovaný prechodový diagram prevedieme standartným spôsobom na retažec nad fixovanou abecedou (napr. binarnou) ■ podobne linearižujeme a kódujeme aj vstup simulovaneho TS ■ samotný program univeržílneho TS je jednoduchý svojim princípom: uchovíava si aktuíalný stav simulovaníeho TS, obsah jeho píaský a cítaný sýmbol; ž linearižovaneho popisu simulovaneho TS odvodí, ake akcie sa maju realižovať v d'alsom kroku výpoctu simulovaneho TS IB110 Podzim 2010 34 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzálny program s poCítadlami vstupom je dvojiča č ísel; prve č íslo je kódom nejakeho programu s poč ítadlami, druhe č íslo je kodom jeho vstupu univerzalny program je mozne skonstruovat tak, aby vyuz íval len dve poč ítadla IB110 Podzim 2010 35 Univerzalita a robustnost;>Robustnost triedý praktický riešiteľných problýmov ^ ^ Univerzalita a robustnosť Výpočtový model Turingov stroj Churchova Turingova hypoteza Univerzálny Turingov stroj Robustnost! triedy prakticky riesitel'nych problemov IB110 Podzim 2010 36 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Modifikovane programy s poCítadlami Motivacia ■ TS manipuluje jednom kroku výpoctu s jedným sýmbolom paský (s jednou číslicou čísla) ■ CP men í jednou instrukciou hodnotu premennej o 1 (exponenciálne menej efektívne v porovnaní s TS) ■ narovnanie diskrepancie ■ CP musí mat moznost k c íslu pridal! alebo odobral! c íslicu v konstantnom case Modifikacia mnozinu instrukci í CP rozsírime o 2 nove instruckie X — X/10 celoc íselne delenie IB110 Podzim 2010 37 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problémov ^ ^ Polynomiálna redukcia Existencia redukcií medzi programovacími jazykmi vyššej úrovne (dostatočne silnými vypoCtovymi modelmi) ukazuje, Ze trieda rozhodnutelných probiemov je invariantna voči vol'be jazyka (modelu). Ota'zka Aka je zlozitost redukcie? Fakt Ak oba modely manipuluju s císlami v inej nez unarnej sústave, tak redukcia mú polynomiúlnu casovú zlozitost . IB110 Podzim 2010 38 Univerzalita a robustnost;>Robustnost triedý praktický riešiteľných problýmov ^ ^ ZloZitost redukcií medzi TS a modifikovanými CP Zlozitost vypočtu TS pocet krokov vypočtu CP pocet vykonanych instrukcií Zlozitost vypočtu je funkciou dlzky vstupu; hodnota funkcie pre argument N zhora ohranicuje zlozitost vypočtov na vsetkyh vstupoch dlzky N. Dlzkou vstupu pre TS je pocet znakov vstupneho retazca, dlzkou vstupu pre CP je pocet císlic pociatocnych hodot premennych. Redukcia TS —> modifikovane CP krok vypoctu je simulovany zmenou hodnoty kazdeho pocítadla; zmena je realizovatel'na konstantnym poctom instrukcií Redukcia modifikovane CP —> TS kačzda inčstrukcia je simulovana končstantnym počctom krokov TS a modifikovane CP su polynomialne ekvivalentne IB110 Podzim 2010 39 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Polynomialna redukcia - dosledky Nečh výpočtove modelý A a B sí polýnomiílne ekvivalentne. Ak algoritmičký problem P je riesitelný na A s časovou zlozitostou O(f(N)) ( f je funkčia dlzký vstupu), tak existuje program pre B, ktorý riesi problem P a jeho časova zlozitost je O(p(f(N))), pričom p je nejaka (fixovana) polýnomialna funkčia. Naopak, ak P je riesitelný na B v čase O(g(N)), tak existuje program pre A, ktorý riesi P s časovou zlozitostou O(q(f(N))), pričom q je nejaka (fixovana) polýnomiílna funkčia. Ak TS rieši problém v polynomiálnom čase, tak aj modifíkový CP rieši tento problém v polynomiálnom čase (a naopak). Ak neexistuje polynomialny TS pre daný problem, tak neexistuje ani polynomialny modifikoaný CP pre tento problem. IB110 Podzim 2010 40 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Robustnosť triedy prakticky riešiteľných problémov CT hypoteza ukazuje robustnost! pojmu rozhodnutelny problem. Polynomialna ekvivalenčia zjemňuje toto pozorovanie na praktičky riesitel'ne problemy. Sekvenčna vypočtova hypoteza Pojem praktičky rieňsitel'neho problemu je robustny, tj. je nezavisly na konkretnej vol'be vypoňčtoveho modelu resp. programovačieho jazyka. Hypotéza sa nevzťahuje na modely s neohraničeným zdrojom paralelizmu, preto sa označuje ako „sekvenčná". Triedy P, NP, PSPACE, EXPTIME su robustne Triedy s lineárnou časovou zložitostou nie sá robustná. IB110 Podzim 2010 41 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Nedeterministické Turingove stroje pre rozhodovacie problemý ■ v prechodovom diagrame je povolene, abý s jedneho stavu výchýdzal ľubovoľný pocet hran oznacených zhodým spínacom (symbolom, ktorý sa cíta) ■ stroj ma moznost výberu, ktorý z prechodov pouzije i pre vstup X dý TS odpoved' „/Áno" (akceptuje) prýve ak existuje taka postupnost výberu prechodov, pre ktom výpocet skoncýv koncovom stave YES (stroj uvíazi vsetky mozníe víypocty na X a akceptuje X praíve ak aspon jeden z výpočtov skoncí v stave YES) m v opacnom prípade, tj. ak ziaden výpocet neskoná v stave YES, da odpoved' „Nie" Nedeterministicke TS sý ekvivalentne (deterministickým) TS. IB110 Podzim 2010 42 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ P=NP? problém - revízia Formalna definícia tried P a NP Trieda P (NP) obsahuje rozhodovacie problemý, ktore su riesiteľne Turingovými strojmi (nedeterministickými TS) s polýnomiílnou casovou zlozitostou. P=NP? problém Sú deterministické a nedeterministické Turingové strojé polynomiálné ekvivalentné? IB110 Podzim 2010 43 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ P=NP? probiem - revízia Definícia NP-tazkeho a NP-íplneho probemu Rozhodovací problem sa nazýva NP-tazký ak kazdý problem z triedý P je na neho polýnomiílne redukovatel'ný. Rozhodovací problem sa nazýva NP-íplný ak je NP-tazký a naviac patrí do triedý NP. Faktý Ak nejaký NP-íplný problem patrí do triedý P, tak P = NP. Ak P = NP, tak ziaden NP-íplný problem nieje riesitel'ný algoritmom polýnomialnej zlozitosti. IB110 Podzim 2010 44 Univerzalita a robustnost;>Robustnost triedý praktický riešiteľných problýmov ^ ^ Turingove stroje a dolne odhadý zloZitosti problemov ■ dôkaz nerozhodnutel'nosti problemu redukcia problemu o ktorom je uz dokízane, zeje nerozhodnutelny, na problíem o ktorom chceme dokaízat', čze je nerozhodnutel'níy príklad redukcia problemu zastavenia na problem domina ■ dokaz vztahu medzi zlozitostnymi triedami metíoda diagonalizaície príklady P C EXPTIME, PSPACE c EXPSPACE ■ dokaz, ze problem nepatrí do zlozitostnej triedy dôosledok uíplnosti príklad ziaden EXPTIME-íplny problem nepatrí do triedy P pre dokaz horných odhadov zložitosti problémov nie sú TS vhodné; naopak je vhodné pouzit programovací jazýk výSSej úrovne IB110 Podzim 2010 45 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Rédukcia problému zastavenié na problém domina a ílohou je pokrýt horní polovicu nekonecnej plochý s podmienkou, že prví dlaždica v T (nažveme ju t) je umiestnenía niekde v spodnom riadku a odpoved' „Ano" pre vstup {M, X) takí, že výpocet M na X sa nežastaví IB110 Podzim 2010 46 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Redukcia probiemu zastavenie na probiem domina Redukcia Vstup dvojica (M, X) Výstup mnozina týpov dlazd íc T a dlazdica t Princ íp konstrukcie (T, t) pokrýtie dlazdicami koresponduje s výpoctom; pokrýtie nekonecnej plochý je mozne len v pr ípade existencie nekonecneho výpoctu IB110 Podzim 2010 47 Univerzalita a robustnost^-Robustnost triedy prakticky riesiteľnych problémov ^ ^ IB110 Podzim 2010 48 Univerzalita a robustnost^-Robustnost triedy prakticky riesiteľnych problémov ^ ^ IB110 Podzim 2010 49