Tiuringo mašina

Pirmoji užduotis. Tiuringo mašinos kodas. Tiuringo mašinos būsenų aprašas. Tiuringo mašinos testavimas. Antroji užduotis. Tiuringo mašinos kodo analizavimas. Tiuringo mašinos būsenų aprašymas.

Pradiniai duomenys: juosta, kurioje užrašytos ir tarpu atskirtos dvi sekos: pirmoji iš skaičių, antroji – iš raidžių, Γ = Σ{ 1, 2, 3, x, y, z, [, ] } ∪ { }; pradinė galvutės pozicija yra kairiausias simbolis.

Parašykite Tiuringo mašiną, kuri sukeistų sekas vietomis. Rezultatas turi būti užrašytas toje pačioje vietoje.

pradinė seka: [123 xyz] pradinė seka: [232 yyy]

simbolius 1,2,3,x,y,z, keičia būseną į atitinkamą simbolį ir pakeičia tą simbolį į „T“. Radusi pabaigos simbolį , mašina baigia darbą,

būsena. Radusi x pakeičia jį į „1“ ir keičia būseną į x, radusi y pakeičia jį į „1“ ir keičia būseną į y, radusi z pakeičia jį į „1“ ir keičia būseną į z.

būsena. Radusi x pakeičia jį į „2“ ir keičia būseną į x, radusi y pakeičia jį į „2“ ir keičia būseną į y, radusi z pakeičia jį į „2“ ir keičia būseną į z.

būsena. Radusi x pakeičia jį į „3“ ir keičia būseną į x, radusi y pakeičia jį į „3“ ir keičia būseną į y, radusi z pakeičia jį į „3“ ir keičia būseną į z.

x būsena. Juda į kairę ir radusi T pakeičia jį į „x“ ir keičia būseną į 0.

y būsena. Juda į kairę ir radusi T pakeičia jį į „y“ ir keičia būseną į 0.

z būsena. Juda į kairę ir radusi T pakeičia jį į „z“ ir keičia būseną į 0.

Išanalizuoti Tiuringo mašiną, jos veikimą patikrinti su įvairiais pradiniais duomenimis. Išanalizuoti pateiktą Tiuringo mašinos kodą, išsiaiškinti naudojamų simbolių abėcėlę, ką tas kodas daro ir paaiškinti kiekvienos būsenos paskirtį.

TM simbolių abėcėlė: Γ = Σ{ 1, 2, 3 [, ] } ∪ { }

Programa tikrina, ar abejose skaičių sekose, kurios sudarytos iš skaitmenų 1,2,3 yra vienodos.

Jei taip, parašoma T, jei ne, parašoma N. Tikrindama kiekvieną skaitmenį, programa deda „+“, jei tiek 1 oje, tiek 2 oje sekose skaitmuo tas pats, jei ne, dedamas „ “. Baigus tikrinti, jei programa randa bent vieną „ “, spausdinamas simbolis N, priešingu atveju – T.