[Maszyna Turinga] Maszyna akceptująca język

[kazafin]

Jak opisać maszynę Turinga akceptującą język:
\(\displaystyle{ \left\{ ww: w\in \left\{a,b\right\}^{*} \right\}}\)
Maszyna ta nie może zapętlać się. Zasymuluj jej działanie dla słowa: abbabb

[wargol]

Nieformalnie rozwiązanie wygląda miej więcej tak:
1. Sprawdź parzystość długości i wyznacz środek słowa:
i) Zmień a->A, B->b i przejdź do ostatniego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
ii) Zmień a->A, B->b i jeśli na lewo masz a albo b przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\)
iii) jeśli na lewo jest a albo b przejdź do i)

Po tym kroku mamy wyraz zapisany dużymi symbolami a głowica maszyny znajduję się nad pierwszym symbolem drugiej połowy słowa WW.

2. Zmień wszystkie A->a i B->b na lewo od środka
i) przejdź w lewo i zmień A->a i B->b aż dojdziesz do początku

Po tym kroku mamy głowicę nad pierwszym symbolem słowa wW, gdzie pierwsza połowa jest zapisana małymi symbolami.

3 porównaj słowo składające się z małych i dużych liter:
i) zmień a->A lub b->B, przejdź w prawo do pierwszego symbolu \(\displaystyle{ \in \left\{ A, B\right\}}\) i sprawdź czy się zgadzają
ii) przejdź do pierwszego symbolu \(\displaystyle{ \in \left\{ a, b\right\}}\) i wykonaj i)

Formalnie należało by zdefiniować całą maszynę Turinga wraz ze zbiorem stanów, funkcji przejść, etc... i udowodnić poprawność.

Pozdrawiam

[ferdelyszys]

Dzięki wargol!