Tiuringo mašinos laboratorinis darbas

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. Tiuringo mašinos testavimos.

Simbolis. Parašykite Tiuringo mašiną, kuri sukeistų sekas vietomis. Rezultatas turi būti

0 [ * r 0 ; Pradinė būsena. Praleidžia bet kokius simbolius iki pirmos sekos pradžios.

0 * * r 0 ; Ignoruoja tarpus ir juda į dešinę iki pirmojo skaičiaus.

0 1 x r 1 ; Kai aptinkamas skaičius 1, jis pakeičiamas į x ir mašina pereina į būseną 1

0 2 x r 2 ; Kai aptinkamas skaičius 2, jis pakeičiamas į x ir mašina pereina į būseną 2

0 3 x r 3 ; Kai aptinkamas skaičius 3, jis pakeičiamas į x ir mašina pereina į būseną 3

0 a x r a ; Kai aptinkama raidė a, ji pakeičiama į x ir mašina pereina į būseną a

0 b x r b ; Kai aptinkama raidė b, ji pakeičiama į x ir mašina pereina į būseną b

0 c x r c ; Kai aptinkama raidė c, ji pakeičiama į x ir mašina pereina į būseną c

0 * * halt ; Jei aptinkama tuščia vieta , programa baigiasi.

1 * * r 1 ; Praleidžia simbolius ir juda į dešinę, kol suranda sekos pabaigą

1 * r 1 ; Ignoruoja tarpus esančius prieš sekos galą ir juda į dešinę

1 a 1 L a ; Kai aptinkama a, mašina grįžta į kairę

1 b 1 L b ; Kai aptinkama b, mašina grįžta į kairę

1 c 1 L c ; Kai aptinkama c, mašina grįžta į kairę.

2 * * r 2 ; Praleidžia simbolius ir juda į dešinę, kol suranda sekos pabaigą.

2 * r 2 ; Ignoruoja tarpus esančius prieš sekos galą ir juda į dešinę.

2 a 2 L a ; Kai aptinkama a, mašina grįžta į kairę.

2 b 2 L b ; Kai aptinkama b, mašina grįžta į kairę.

2 c 2 L c ; Kai aptinkama c, mašina grįžta į kairę.

3 * * r 3 ; Praleidžia simbolius ir juda į dešinę, kol suranda sekos galą

3 * r 3 ; Ignoruoja tarpus esančius prieš sekos galą ir juda į dešinę.

3 a 3 L a ; Kai aptinkama a, mašina grįžta į kairę.

3 b 3 L b ; Kai aptinkama b, mašina grįžta į kairę.

3 c 3 L c ; Kai aptinkama c, mašina grįžta į kairę.