Matematické Fórum

NetFenix · 16. 04. 2011 10:52

Mějme standartní TS $M=(Q, \Sigma, \Gamma, \delta, q_0, F)$ . Sestrojme k němu TS M', který předpokládá pouze pravostraně nekonečnou pásku. Tedy z nejlevější buňky nemůže přejít doleva a přesto simuluje stroj M.

Způsob konstrukce:

$Q'=\{q_0', q_1\}\cup\{q_x| x \in \Sigma\}\cup\{q_U| q \in Q\}\cup\{q_D| q \in Q\}$
$\Gamma'=\Sigma\cup(\Gamma\times\Gamma)\cup\{c,\Box \}$
$F'=\{q_U|q \in F\}\cup\{q_D|q \in F\}$
$\delta'(q_0',x)=(q_x,c,+1)...$ pro $x \in \Sigma$
$\delta'(q_x,y)=(q_y,(x, \Box),+1)...$ pro $x,y \in \Sigma$
$\delta'(q_x,\Box)=(q_1,(x, \Box),-1)...$ pro $x \in \Sigma$
$\delta'(q_1,z)=(q_1,z,-1)...$ pro $z \neq c$
$\delta'(q_1',c)=((q_0)_U,c,+1)...$

Obrázkem znázorněte pásku, doplňte instrukce tak aby M' skutečně simuloval M (U v indexu znamená up a D znamená down).

----------------
Čili je mi asi jasný, jak bude fungovat stroj se zleva omezenou páskou:

Zkrátka budu mít dvě pásky. Obě dvě tedy zleva omezené. Budu-li v horní a půjdu doprava, skutečně po pásce půjdu doprava, pokud půjdu doleva, půjdu doleva. Ovšem na začátku pásky budu mít nějaký speciální znak z páskové abecedy, který mi řekne, že jsem dorazil na konec a přepne se na spodní pásku. Ve spodní pásce budou ale otočené směry. To znamená, že jestliže půjdu doleva tak na pásce půjdu doprava a naopak. Pokud opět dojdu nejvíc vlevo na pásce, přepnu se zpátky na horní pásku.

Takhle nějak si představuju, že by to snad mohlo fungovat a snad se i po mě něco takového chce v této úloze. Ale nevím jak to napasovat na tyto instrukce, popřípadě co vůbec ty instrukce znamenají. (ještě v zadání to c je přeškrtnuté, jestli to má nějaký vliv)

Nemohl by mi prosím někdo poradit. Moc děkuji...

Matematické Fórum

#1 16. 04. 2011 10:52

turingův stroj - zleva omezená páska

Zápatí