Maszyna Turinga dla palindromów. Bartek: Skonstruować maszynę Turinga. Witam, nie bardzo wiem jak zabrać się za zadanie z maszyną Turinga, a mianowicie: Przykładowo chciałbym skonstruować maszynę która akceptuje język PALINDROMY ∊ {a,b}* Czyli "abba" ∊ PALINDROMY, zaś "aabb" nie należy do PALINDROMY. Zakładam że na "początku" i "końcu" taśmy znajdują się symbole "pusty", które umownie oznaczę wielkim "O" Czyli taśma wygląda tak O|O|O|a|b|b|a|O|O|O Chciałbym wstępnie rozwiązać to zadanie dla maszyny z jedną taśmą. Zaczynam od stanu zerowego Q0, głowica znajduje się na pierwszym niepustym symbolu, czyli na 'a'. Zapamiętuje symbol, w kolejnym stanie przechodzę głowicą ciągle w prawo aż do napotkania symbolu pustego O. W momencie napotkania symbolu pustego przechodzę o jedną komórkę w lewo i porównuje symbol z zapamiętanym symbolem. Następnie pojawia się problem, co dalej. Jeden z moich pomysłów to: Gdy jestem w stanie początkowym na literce 'a' zamieniam ją np na gwiazdkę '*'. Przechodzę w prawo aż do symbolu pustego, cofam się o jedną komórkę i sprawdzam czy znajduje się tam zapamiętany symbol. Jeżeli tak to wstawiam '*'. Przesuwam głowice w lewo aż do gwiazdki, przesuwam o jedną komórkę w prawo, zapamiętuje symbol, przesuwam głowice w prawo aż do napotkania gwiazdki, przesuwam o jedną komórkę w lewo i porównuje znak. Jeżeli jest taki sam wstawiam gwiazdkę i tak w kółko, aż taśma się wypełni gwiazdkami, wtedy wiemy że wyraz należy do języka PALINDROMY. Jednak zastanawiając się nad tym, wpadam w pętle, bo nie potrafię zatrzymać. Zamieniać na symbole puste? Czyli przechodzę w prawo, napotkam symbol pusty, przechodzę o komórke w lewo i jeżeli jest też symbolem pustym to przechodze to stanu końcowego? Poproszę o wskazówki jak rozwiązać takie zadanie. Następnie postaram się zapisać stany takiej maszyny. Pozdrawiam serdecznie.