Dwustanowa maszyna Turinga do dopasowywania nawiasów

9

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.

Cztery zabawy
źródło
Czy wolno nam używać większego alfabetu?
Raphael
@Raphael Według wyniku teoretycznego można wymieniać stany na alfabet i odwrotnie. Zatem zmniejszenie stanów do dwóch oznacza, że ​​najprawdopodobniej będziesz musiał użyć większego alfabetu. Tak więc, krótka odpowiedź brzmi: alfabet może być tak duży, jak pożądany
Four_FUN
Myślę, że w przypadku dwóch taśm TM można tego dokonać bez dodatkowych symboli i.
Karolis Juodelė
@Four_FUN jesteś z MIT?

Odpowiedzi:

8

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:
_ ( ) [ { / \ (gdzie_ jest początkowym pustym symbolem)

q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

Możesz to zobaczyć w pracy za pomocą internetowego symulatora maszyny Turinga ; kod źródłowy to:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

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 ”

Vor
źródło
Czy nie zdecydowaliśmy, że odpowiedzi przedstawiające tylko kod źródłowy nie są dobre dla informatyki ? ;)
Raphael
1
@Raphael: Zgadzam się z tobą, ale moje można traktować jak dodatek do twojego (wydaje się to w porządku, nawet jeśli nie sprawdziłem szczegółów). Dodam notatkę na ten temat.
Vor
1
@Raphael: Kodowałem to dla zabawy, próbując zminimalizować symbole na taśmie, i „wydaje się” :-) działa, więc postanowiłem to opublikować.
Vor
@Vor. Bardzo dziękuję za dodatkowy wkład w ten problem. Wszystko to mówi mi, że potrzebuję więcej praktyki w tym zakresie. Dziękujemy za opublikowanie kodu źródłowego, mimo że teoria była tym, o co mi chodziło.
Four_FUN
1
@Four_FUN: Rogozhin Universal TM (2,18) jest standardową maszyną Turinga (tj. Oprócz wejścia jej początkowa taśma zawiera tylko puste symbole), która symuluje dowolny system 2-znaczników (który jest modelem uniwersalnym). Pierwszy symbol 2 stanu 3 jest maszyną słabo Turinga (początkowa taśma musi być wypełniona nieskończoną sekwencją wzoru), a uniwersalność zostaje „osiągnięta”, symulując automaty komórkowe Regułę 110 (która okazała się być kompletną Turingiem ). Istnieje (twierdzony?) Dowód, że standardowa TM (2,3) nie może być ukończona przez Turinga.
Vor
7

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ątkowy q0 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^.
    Jeżeli nie ma), tzn. trafiliśmy w symbol przerwy #, zastąp to x^ i przejdź do q1.

    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.
    Jeśli znajdziemy)^ lub # po pierwsze, zapętl / odrzuć¹.

  • W q1, 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ć.


  1. Jest to poprawne, ponieważ maszyna pasuje odwrotnie; w danych prawnych są tylkox między parą nawiasów, które są obecnie dopasowane.
Raphael
źródło
Jeśli nie masz nic przeciwko, że zapytam, jak dokładnie moje rozwiązanie obiecuje uniwersalną bazę TM z dwoma stanami? (bardzo sprytne rozwiązanie btw. dziękuję za wkład)
Four_FUN
1
@Four_FUN: ponieważ mówisz w swoim pytaniu: „... Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2 ...” . .. abyś mógł wybrać dowolną uniwersalną maszynę Turinga i zredukować liczbę stanów do zaledwie 2. A jeśli wykonasz jakieś eksperymenty, zdasz sobie również sprawę, że nie jest trudno stworzyć automatyczną procedurę, która przekształci dowolną bazę TM w ekwiwalent 2 stan TM (jeśli nie zależy ci na minimalizacji liczby symboli alfabetu).
Vor