DMT - długość najdłuższego ciągu bitów

Muszę zaprojektować Jednotaśmową Maszynę Turinga zwracającą jako stan ilość bitów w najdłuższym podciągu liczby. Czyli np. podanie 001 zakończyłoby się stanem q2, 1110 stanem q3, 10 stanem q1, 100001101 stanem q4 itp. Długość takiego podciągu w założeniu nie może przekraczać 30. Jak to zrobić?

Myślałem nad:

<0, q0, 0, q1, R>
<0, q1, 0, q2, R>
...
<0, q30, 0, END, x>

<1, q0, 1, q1, R>
<1, q1, 0, q2, R>
...
<1, q30, 1, END, x>

Ale coś takiego resetowało by ilość bitów gdyby podciąg miał mniej niż 30 znaków, czyli np. 00010 zwróciłby q1, co jest błędem...

Za bardzo upraszczasz. Moim zdaniem stanów musisz mieć po prostu więcej niż te 30 (przy założeniu algorytmu jaki prezentujesz) ;) Szczególnie musisz mieć stany służące do "poszukiwania dłuższego podciągu" a to wymaga żebyś wiedział czy szukasz 0 czy 1 więc nie wystarczy ci informacja ile wystąpień symbolu już miałeś (tzn q1,q2,q3...). Ergo stanów musiałbyś mieć przynajmniej 2 razy wiecej albo musiałbyś gdzieś "zapisać" sobie czego szukasz.

Poza tym samo poszukiwanie musiałoby działać tak:

• liczysz ile elementów ma pierwszy podciąg i następnie szukasz dłuższego w dalszej części ciągu (niestety kolejne dublowanie stanów) i jak nie znajdziesz to kończysz w odpowiednim stanie
• jeśli znalazłes dłuższy to przesuwasz sie na tamten podciąg i powtarzasz cały algorytm

Albo tak:

• liczysz ile elementów ma pierwszy podciąg i zapisujesz na początku taśmy (np. poprzez odpowiednią liczbę jedynek)
• przesuwasz się na następny podciag, liczysz ile elementów ma a potem porównujesz z zapisanym i jeśli ma mniej to olewasz, a jesli ma wiecej to dodajesz brakujace jedynki
• jak dojdziesz do końca liczby z wejścia to zliczasz jedynki zapisane na początku taśmy i na tej podstawie ustawiasz sobie stan wyjściowy.
  W tej wersji stanów nie trzeba w sumie zbyt wiele do samego chodzenia po taśmie :)