2? A od kiedy 2 jest potęgą? o_O Chyba że nie rozumiem tego języka który opisałeś. Chodzi o akceptowanie ciągów 0 których liczba jest kwadratem liczby naturalnej? A co dokładnie robi ta maszyna którą narysowałeś? Jaki algorytm stosuje? Na jakiej podstawie decydujesz czy liczba jest kwadratem czy nie?
Wydaje mi się że najłatwiejsza opcja to odejmowanie kolejnych liczb nieparzystych bo np. 25 = 1+3+5+7+9 i jest to prawda dla każdego kwadratu. Więc maszyna turinga mogłaby zamazywać najpierw 1, potem 3, potem 5, potem 7 symboli... i jeśli zamaże wszystko to akceptujemy, a jeśli nam brakło
to odrzucamy.
Czyli np.:
- Przygotowanie algorytmu: Idziemy na koniec inputu, stawiamy jakiś delimiter i za nim stawiamy jeden symbol A. Wracamy na początek taśmy.
- Teraz zaczyna sie właściwa pętla.
- Idziemy na koniec aż do delimitera, pomijamy wszystkie B, zamieniamy pierwsze napotkane A na B i wracamy na początek taśmy i usuwamy jeden symbol.
- Powtarzamy krok 3 aż skończyły nam się A (doszliśmy do blanka). Wtedy cofamy się do pierwszego B, zamieniamy wszystkie B na A i dopisujemy dwa A na końcu.
- Powtarzamy to aż:
- szukając znaku do usunięcia trafiliśmy na delimiter inputu, wtedy odrzucamy
- usunęliśmy ostatni symbol i trafiliśmy na delimiter i jednocześnie skończyły nam się wszystkie A, wtedy akceptujemy.
A symbolizują tutaj elementy które chcemy usuwać z inputu, czyli 1, 3, 5, 7..., B symbolizują elementy już usunięte w tej turze. Przykład:
input: 000
Po przygotowaniu: 000|A
Taśma w kolejnych krokach algorytmu:
000|B
_00|B
_00|AAA
_00|BAA
__0|BAA
__0|BBA
___|BBA
___|BBB
i tutaj odrzucamy bo brakło nam symboli do usunięcia.
Analogicznie dla 0000
:
Po przygotowaniu: 0000|A
Taśma w kolejnych krokach algorytmu:
0000|B
_000|B
_000|AAA
_000|BAA
__00|BAA
__00|BBA
___0|BBA
___0|BBB
____|BBB
I tutaj akceptujemy bo zdjęliśmy ostatni symbol inputu a jednocześnie nie mamy już żadnych A