Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2.
Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. (()()()))()()()
Jest zrównoważony (poprzedni przykład zwróciłby 0 za niezrównoważone).
Staram się, jak mogę, że mogę być tylko maszyną trójstanową. Chciałbym wiedzieć, czy ktokolwiek może sprowadzić to do teoretycznego minimum 2 i jakie było ich podejście / stany / symbole!
Dla wyjaśnienia, nawiasy są „umieszczone” pomiędzy pustą taśmą, więc w powyższym przykładzie
- - - - - - - (()()()))()()() - - - - - - -
byłoby wejściem na taśmę. Alfabet obejmowałyby (
, )
, 1
, 0
, -
, a *halt*
państwo nie liczy się jako państwo.
Dla porównania, trzy podejście stanowe, które mam, jest następujące: Opis stanów:
State s1: Looks for Closing parenthesis
State s2: Looks for Open parenthesis
State s3: Checks the tape to ensure everything is matched
Symbols: ),(,X
Przejścia wymienione jako:
Action: State Symbol NewState WriteSymbol Motion
// Termination behavior
Action: s2 - *halt* 0 -
Action: s1 - s3 - r
//Transitions of TM
Action: s1 ( s1 ( l
Action: s1 ) s2 X r
Action: s1 X s1 X l
Action: s2 ( s1 X l
Action: s2 X s2 X r
Action: s3 ( *halt* 0 -
Action: s3 X s3 X r
Action: s3 - *halt* 1 -
Wybacz nieformalny sposób zapisywania tego wszystkiego. Wciąż uczę się teoretycznych konstrukcji.
źródło
Odpowiedzi:
Po prostu „kompendium kodu źródłowego” odpowiedzi Raphaela: to działająca wersja, która używa tej samej sztuczki (w stanie q1) i ma alfabet taśmy:
_ jest początkowym pustym symbolem)
_ ( ) [ { / \
(gdzieMożesz to zobaczyć w pracy za pomocą internetowego symulatora maszyny Turinga ; kod źródłowy to:
Ostatnia uwaga: jeśli chcesz zobaczyć, jak tę technikę można wykorzystać do granic możliwości, przeczytaj (i spróbuj zrozumieć :-) budowę uniwersalnej maszyny Turinga z 2 stanami i 18 symbolami autorstwa Y. Rogozhina w „Small Universal Turing” maszyny ”
źródło
Głupia odpowiedź: twój wynik obiecuje, że istnieje uniwersalna maszyna Turinga z dwoma stanami. Skonstruuj dowolną bazę TM dla języka Dyck, oblicz jej indeks i zakoduj na stałe w uniwersalnej maszynie.
Ale to oczywiście nie jest bardzo satysfakcjonujące. Twoje podejście faktycznie działa, jeśli „oszukasz” różnicę między ruchem w lewo a ruchem w prawo, jednocześnie dopasowując pary nawiasów do rozszerzenia alfabetu. Potrzebujemy{ # , ( , ) , x } i oznaczone wersje za^ wszystkich symboli za .
Stan początkowyq0 działa w następujący sposób.
Znajdując nieoznakowane symbole, przesuń w prawo, aż do pierwszego) jest znaleziony. W ten sposób zastąp wszystkie symboleza z za^ . Zastąp znalezione) z x^ . ) , tzn. trafiliśmy w symbol przerwy # , zastąp to x^
i przejdź do q1 .
Jeżeli nie ma
Znajdując oznaczone symbole, przesuń się w lewo, aż do pierwszego(^ znaleziono, zastępując wszystkie przekazane (oznaczone) symbole ich nieoznakowanymi wariantami. Zastąp znalezione(^ z x . )^ lub # po pierwsze, zapętl / odrzuć¹.
Jeśli znajdziemy
Wq1 , sprawdzamy, czy wszystko zostało dopasowane; wciąż mogą istnieć prefiksy formularza(^+ na taśmie. To znaczy, przesuń się w lewo, dopóki znajdziemyx^ . Jeśli tak znajdziemy# , zaakceptować; jeśli znajdziemy inny symbol, ale
x^ po pierwsze, zapętl / odrzuć.
źródło