Naloga: Realiziraj univerzalni turingov stroj/Rešitev (Mathematica)

Iz MaFiRaWiki

Univerzalni turingov stroj mora na traku prebrati opis nekega turingovega stroja (TS) in sam trak tega stroja (t). Univerzalni turingov stroj mora na trak, potem ko preteče opis(TS) in t, zapisati enak zapis, kot bi ga stroj TS ob vhodu t. Če se turingov stroj ustavi v sprejemnem (oziroma v zavrnitvenem) stanju se mora tudi univerzalni turingov stroj ustaviti v sprejemnem (zavrnitvenem) stanju.

V Mathematici si lahko poenostavimo opis(TS) tako, da bo program najlažje razbral zahtevane podatke: vhodno, tračno abecedo itn., še posebej pa prehodno funkcijo. Zato bo naš opis poljubnega turingovega stroja in traku podan na naslednji način:

[{stanja},

{znaki vhodne abecede},

{znaki tračne abecede},

{prazen znak},

{prvi del prehodne funkcije}, {drugi del prehodne funkcije},

...,

{zadnji del prehodne funkcije},

{začetno stanje}, {sprejemno stanje}, {zavrnitveno stanje},

{beseda na traku}].

Konkretno v Mathematici naš opis turingovega stroja, ki razpoznava liha števila (glej turing.nb) in traku "0100010", izgleda tako:

TS = opisT[{q0, q1, qs, qz},
           {"0", "1"},
           {"0", "1", "$"},
           {"$"},
           {q0,"1", q0, "1", 1}, {q0, "0", q0, "0", 1}, {q0, "$", q1, "$", -1},
           {q1, "1", qz, "1", 0}, {q1, "0", qs, "0", 0}, {q1, "$", qz, "$", 0},
           {q0}, {qs}, {qz},
           {"0100010"}];

Najbolj pomembno je razbrati podatke o prehodni funkciji. V opisu je prehodna funkcija podana s peterko: {trenutno stanje, znak pod glavo, novo stanje, nov znak, premik}. Naš program mora zato definirati prehodno funkcijo, ki pravi: če je stroj v stanju trenutno stanje in je pod glavo znak pod glavo, potem pojdi v stanje novo stanje, na trak zapiši nov znak in se premakni za premik.

Definirajmo za naš konkretni primer nekaj pomožnih funkcij, ki bodo iz opisa razbrale podatke potrebne za sestavo prehodne funkcije - v programski kodi jo imenujemo de1.

stanjeStroja[i_]:=Part[{Part[Part[TS,i + 4], 1], InputForm[Part[Part[TS, i + 4], 2]]}, 1];
znakPodGlavo[i_]:=Part[{Part[Part[TS, i + 4], 1], InputForm[Part[Part[TS, i + 4], 2]]}, 2];
novoStanje[i_]:=Part[{Part[Part[TS,i + 4], 3], InputForm[Part[Part[TS, i + 4], 4]], Part[Part[TS, i + 4], 5]}, 1];
zapišiZnak[i_]:=Part[{Part[Part[TS, i + 4], 3], Part[Part[TS, i + 4],4], Part[Part[TS, i + 4], 5]}, 2];
premik[i_]:=Part[{Part[Part[TS, i + 4], 3], InputForm[Part[Part[TS, i + 4], 4]], Part[Part[TS, i + 4], 5]}, 3];

drugaPomožna[i_] := {novoStanje[i], zapišiZnak[i], premik[i]};

de1[u_, v_]:= de1[u, v, 1];
de1[u_, v_, i_]:=drugaPomožna[i] /; (u === stanjeStroja[i] && InputForm[v] === znakPodGlavo[i]);
de1[u_, v_, i_] := de1[u, v, i + 1];

Zdaj, ko imamo prehodno funkcijo, lahko sestavimo univerzalni turingov stroj, ki bo podan na klasičen način (glej turing.nb):

UTS = turingovStroj[Part[TS, 1],
                    Part[TS, 2],
                    Part[TS, 3],
                    Extract[Part[TS,4], 1],
                    de1,
                    Extract[Part[TS, Length[TS] - 3], 1],
                    Extract[Part[TS, Length[TS] - 2],1],
                    Extract[Part[TS, Length[TS] - 1], 1]
                   ];

Preverimo lahko delovanje našega turingovge stroja UTS:

prazenZnak[s_turingovStroj]:=s[[4]];
prehodnaFunkcija[s_turingovStroj]:=s[[5]];
zacetnoStanje[s_turingovStroj]:=s[[6]];
sprejemnoStanje[s_turingovStroj]:=s[[7]];
zavrnitvenoStanje[s_turingovStroj]:=s[[8]];

sprejema[s_turingovStroj, st_opisT]:=sprejema[s, Extract[Last[st], 1]];
sprejema[s_turingovStroj, w_]:=sprejema[s, zacetnoStanje[s], w];
sprejema[s_turingovStroj, qt_, ""]:=sprejema[s, qt, {"",prazenZnak[s], ""}];
sprejema[s_turingovStroj, qt_, w_String]:=sprejema[s, qt, {"", StringTake[w, 1], StringDrop[w, 1]}];
sprejema[s_turingovStroj, qt_, {t1_, tt_, t2_}] /; sprejemnoStanje[s] == qt := {True, {t1, tt, t2}};
sprejema[s_turingovStroj, qt_, {t1_, tt_, t2_}] /; zavrnitvenoStanje[s] == qt := {False, {t1, tt, t2}};
sprejema[s_turingovStroj, qt_, {t1_, tt_, t2_}]:=
sprejema[s, First[prehodnaFunkcija[s][qt,tt]], novTrak[s, prehodnaFunkcija[s][qt, tt], t1, t2]]

novTrak[s_turingovStroj, {_, nz_, 0}, t1_, t2_]:={t1, nz, t2};
novTrak[s_turingovStroj, {_, nz_, 1}, t1_, ""]:={StringJoin[t1, nz], prazenZnak[s], ""};
novTrak[s_turingovStroj, {_, nz_, 1}, t1_, t2_]:={StringJoin[t1, nz], StringTake[t2, 1], StringDrop[t2, 1]};
novTrak[s_turingovStroj, {_, nz_, -1}, "", t2_]:={"", prazenZnak[s], StringJoin[nz, t2]};
novTrak[s_turingovStroj, {_, nz_, -1}, t1_, t2_]:={StringDrop[t1, -1], StringTake[t1, -1], StringJoin[nz, t2]};

sprejema[UTS, TS]

{True, {010001, 0, $}}

Glej tudi

Osebna orodja