Matematické Fórum

beda · 03. 04. 2010 20:23 — Editoval beda (04. 04. 2010 17:51)

Zdravím,
nepomohl by mi někdo prosím s tímto problémem ? Jedná se o simulaci mezi různými variantami turingových strojů.

Mám TS (s oboustranně nekonečnou páskou) definovaný takto:
$M=(Q, \Sigma, \Gamma, \delta, q_0, F)$

K němu mám sestrojit TS definovaný takto:
$M^'=(Q^', \Sigma, \Gamma^', \delta^', q_0^', F^')$ ,
který předpokládá jednostranně (pravostranně) nekonečnou pásku - z nejlevější buňky hlava nemůže přejít doleva. A přesto má tento TS simulovat stroj M.

Naznačen možný 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\{\cancel{c}, \oblong}$
$F^'=\{q_U \| q \in F\} \cup \{q_D \| q \in F\}$
$\delta^'(q_0^', x) = (q_x, \cancel{c}, +1)$ ... pro $x \in \Sigma$
$\delta^'(q_x, y) = (q_y, (x, \oblong), +1)$ ... pro $x,y \in \Sigma$
$\delta^'(q_x, \oblong) = (q_1, (x, \oblong), -1)$ ... pro $x \in \Sigma$
$\delta^'(q_1, z) = (q_1, z, -1)$ ... pro $z \not= \cancel{c}$
$\delta^'(q_1, \cancel{c}) = ((q_0)_U, \cancel{c}, +1)$

Pozn: asi vás napadne pojem "dvoustopá páska" a písmeno "U" v indexu u stavu znamená "up", "D" znamená "down".
Doplňte instrukce stroje $M^'$ (tedy dodefinujte zobrazeni $\delta^'$ ) tak, aby skutečně simuloval M

Kdyby mi někdo dokázal alespoň trošičku pomoci, byl bych mu velice vděčný.

beda · 04. 04. 2010 15:25 — Editoval beda (04. 04. 2010 21:34)

Tak už jsem mírně pokročil, ale zatím jenom v tom směru, že alespoň tak nějak chápu co dělají ty naznačené instrukce. A taky snad už vím, jak by ten $M^'$ měl vlastně pracovat. Ale popořadě.

U dvou instrukcí si nejsem jistý jak se to má přepisovat. Jedná se o tyto dvě instrukce:
$\delta^'(q_x, y) = (q_y, (x, \oblong), +1)$ ... pro $x,y \in \Sigma$
$\delta^'(q_x, \oblong) = (q_1, (x, \oblong), -1)$ ... pro $x \in \Sigma$
Není mi jasné, jak se to má přepsat, když tam je v závorce $(x, \oblong)$ ? Mám to chápat tak, že se to přepíše buď na $x$ nebo na $\oblong$ ?

EDIT: tak tohle už vím jak to chápat. Jde o to, že u dvoustopé pásky jsou symboly v každé buňce pásky zapsány nad sebou. Tzn. že když se to má přepsat na $(x, \oblong)$ tak v horní části buňky bude $x$ a v dolní částí bude $\oblong$ . Ale zbytek stále platí, takže kdyby se někdo chtěl podělit o nějaký nápad, budu jen rád.

Jinak k té práci toho TS bych měl toto. Ty uvedené instrukce nedělají nic jiného, než přesunou celé původní slovo o jedno políčko doprava a na uvolněné místo nalevo od slova se umístí speciální znak $\cancel{c}$ , který zde figuruje jako ukazatel levého konce pásky. Po dokončení tohoto přejde TS do stavu $(q_0)_U$ a dále je to třeba dořešit.

Celý ten TS, by podle mě měl pracovat tak, že bude jakoby jedna páska, ale se dvěmi stopami nad sebou, přičemž hlava bude pouze jedna. Horní stopa pásky bude simulovat čtení/zápis v rámci vstupního slova a nebo napravo od něj. Když by se něco mělo číst/zapsat nalevo od původního slova, tak se přejde na spodní stopu pásky a bude se pokračovat tam. Přičemž směr na spodní stopě pásky bude muset být přehozený. Tzn. když bude hlava stát na horní stopě úplně vlevo a bude chtít jít doleva, tak přejde na spodní stopu a bude se opticky (na papíře) pohybovat doprava, ale ve skutečnosti v instrukcích půjde TS stále doleva. To samé bude platit když bude hlava stát na spodní stopě pásky úplně vlevo a bude chtít jít doprava (opticky doleva - přehozené směry), tak skočí na horní stopu pásku a bude se pohybovat na horní stopě pásky doprava. Tím se vlastně docílí požadované funkčnosti, kdy bude TS s pravostranně nekonečnou páskou simulovat TS s oboustranně nekonečnou páskou.

Mám ale problém jak toto zapsat pomocí instrukcí, abych doplnil to zobrazení $\delta^'$ . Nevěděl by mi s tím někdo prosím pomoci ?

Kondr · 04. 04. 2010 21:09

Tak to už v podstatě máš, ne? Teď se vezmou všechny pravidla původního stroje typu
(q1,x)->(q2,y,+1)
a udělají se z nich pravidla
(q1U,(x,z))->(q2U,(y,z),+1) (pro všechna $z\in\Sigma\cup\{\oblong\}$ )
(q1D,(x,z))->(q2D,(y,z),-1) (pro všechna $z\in\Sigma\cup\{\oblong\}$ )
analogicky se zpracují všechna pravidla
(q1,x)->(q2,y,-1)
Je potřeba ještě ošetřit začátek pásky
(qU,c)->(qD,c,+1) pro všechny q
(qD,c)->(qU,c,+1) pro všechny q
a rozmyslet, jestli jsme nezapomněli na nějaké další okrajové případy.

beda · 07. 04. 2010 13:46 — Editoval beda (07. 04. 2010 19:06)

@Kondr: Díky moc za tvou pomoc. Hrozně moc mi to pomohlo ;) Dneska jsem to referoval a dopadlo to dobře, takže ještě jednou díky ;)

EDIT:
Jenom tam máš drobnou chybku. V tom pravidle pro dolní část pásky, musí být přehozené pořadí těch symbolů.
Takže místo (q1D,(x,z))->(q2D,(y,z),-1) bude (q1D,(z,x))->(q2D,(z,y),-1)

Je to z toho důvodu, že když pracujeme na spodní části pásky, tak potřebujeme nechat horní část bezezměny, což nám zajistí to z.

BTW: teď mě možná napadlo, že ty jsi ty znaky bral v pořadí (spodní čast, horní část) a v tom případě by bylo dobře i to tvoje.
Já to bral jak pro horní, tak pro spodní část stejně (horní část, spodní část) a proto jsem si to ve spod přehodil.

To ale nemění nic na tom, že si cením tvé pomoci a děkuji ti za ni ;)

Matematické Fórum

#1 03. 04. 2010 20:23 — Editoval beda (04. 04. 2010 17:51)

Turingovy stroje - simulace mezi různými variantami

#2 04. 04. 2010 15:25 — Editoval beda (04. 04. 2010 21:34)

Re: Turingovy stroje - simulace mezi různými variantami

#3 04. 04. 2010 21:09

Re: Turingovy stroje - simulace mezi různými variantami

#4 07. 04. 2010 13:46 — Editoval beda (07. 04. 2010 19:06)

Re: Turingovy stroje - simulace mezi různými variantami

Zápatí