Pokiaľ nie je povedané ináč, všetky jazyky, gramatiky a automaty v zadaniach sú všeobecné (t.j. môžu byť ľubovoľné). Pokiaľ bola odprednášaná štandardná konštrukcia, používajte ju! V opačnom prípade musíte zdôvodniť správnosť svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú" prezentáciu si prípadné slovo zdôvodnite nahraďte slovom dokážte.

Znakom C označujeme cent a znakom S dolár.

1. Majme orientovaný graf G, ktorého počet vrcholov nie je dopredu známy. Nech TS A akceptuje jazyk
   L = {u#v | u,v sú binárne zápisy čísel vrcholov, z u do v vedie v G hrana}
   Pre daný kód stroja A: Je rozhodnuteľné, či v G existuje cesta z vrchola 0 do vrchola 1?
2. Majme triedu Turingovych strojov takých, ktoré nemôžu zapisovať na pásku blank. Je pre takéto stroje rozhodnuteľný problém: "Pre daný TS A, vstupné slovo w a konfiguráciu k, existuje výpočet A na w, ktorý prechádza cez konfiguráciu k ?"
3. Je nasledujúci problém rozhodnuteľný? "Pre daný TS A, slovo w a stavy p1,p2,p3: prejde A pri výpočte na w niekedy postupnosťou stavov p1,p2,p3?"
4. Dokážte, že problém: "pre daný TS zistiť, či zastaví na každom vstupe" je nerozhoduteľný.
5. Nech L je rekurzívne vyčísliteľný jazyk. Existuje TS ktorý na výstupnej páske postupne generuje všetky slová z L, pričom každé z nich práve raz?
6. Daný je k-páskový TS A pracujúci v priestore log n. Napíšte delta funkciu pre jednopáskový Turingov stroj A' pracujúci v priestore log n taký, že L(A')= L(A). (Použite konštrukciu z prednášky.)