System tagów

System znaczników to deterministyczny model obliczeniowy opublikowany przez Emila Leona Posta w 1943 roku jako prosta forma systemu kanonicznego Posta . System tagów można również postrzegać jako maszynę abstrakcyjną, zwaną maszyną Post-tag (nie mylić z maszynami Post-Turinga ) - krótko mówiąc, maszyną o skończonych stanach , której jedyną taśmą jest kolejka FIFO o nieograniczonej długości, tak że w każdym przejściu maszyna odczytuje symbol na początku kolejki, usuwa stałą liczbę symboli z początku i dołącza do końca ciąg symboli, który zależy wyłącznie od pierwszego symbolu odczytanego w tej kolejce przemiana.

Ponieważ wszystkie wskazane operacje są wykonywane w jednym przejściu, maszyna tagująca ma ściśle tylko jeden stan.

Definicje

System znaczników to trójka ( m , A , P ), gdzie

  • m jest dodatnią liczbą całkowitą, zwaną liczbą usunięcia .
  • A jest skończonym alfabetem symboli, z których jeden jest specjalnym symbolem zatrzymania . Wszystkie skończone (prawdopodobnie puste) ciągi na A nazywane są słowami .
  • P jest zbiorem reguł produkcji , przypisującym słowo P(x) (nazywane produkcją ) do każdego symbolu x w A . Produkcja (powiedzmy P( H ) ) przypisana do symbolu zatrzymania, jak pokazano poniżej, nie odgrywa żadnej roli w obliczeniach, ale dla wygody przyjmuje się, że P( H ) = „H” .

Słowo zatrzymujące to słowo, które albo zaczyna się od symbolu zatrzymującego, albo którego długość jest mniejsza niż m .

Transformacja t (nazywana operacją znacznikową ) jest zdefiniowana na zbiorze słów nieprzerwanych, tak że jeśli x oznacza skrajny lewy symbol słowa S , to t ( S ) jest wynikiem usunięcia m skrajnych lewych symboli S i dodanie słowa P(x) po prawej stronie. W ten sposób system przetwarza głowę m-symbolu na ogon o zmiennej długości, ale wygenerowany ogon zależy wyłącznie od pierwszego symbolu głowy.

Obliczenia przez system znaczników to skończona sekwencja słów tworzonych przez iterację transformacji t , zaczynając od początkowo podanego słowa i zatrzymując się , gdy generowane jest słowo zatrzymujące. (Zgodnie z tą definicją uważa się, że obliczenia nie istnieją, chyba że słowo zatrzymujące jest tworzone w skończonej liczbie iteracji. Alternatywne definicje pozwalają na obliczenia nieprzerwane, na przykład poprzez użycie specjalnego podzbioru alfabetu do identyfikacji słów, które kodują dane wyjściowe).

Termin system znaczników m jest często używany do podkreślenia numeru usunięcia. Definicje różnią się nieco w literaturze (por. Literatura), przy czym ta przedstawiona tutaj pochodzi od Rogożyna.

Użycie symbolu zatrzymującego w powyższej definicji umożliwia zakodowanie danych wyjściowych obliczeń w samym ostatnim słowie, podczas gdy w przeciwnym razie dane wyjściowe byłyby zakodowane w całej sekwencji słów utworzonych przez iterację operacji znacznika.

Powszechna definicja alternatywna nie używa symbolu zatrzymania i traktuje wszystkie słowa o długości mniejszej niż m jako słowa zatrzymujące. Inną definicją jest oryginalna definicja użyta przez Post 1943 (opisana w notatce historycznej poniżej), w której jedynym słowem zatrzymującym jest pusty ciąg.

Przykład: prosta ilustracja z dwoma tagami

Ma to jedynie na celu zilustrowanie prostego systemu z 2 znacznikami, który wykorzystuje symbol zatrzymania.

System dwuznaczników Alfabet: {a,b,c,H} Reguły produkcji: a --> ccbaH b --> cca c --> cc Obliczenia Początkowe słowo: baa acca caccbaH ccbaHcc baHcccc Hcccccca (zatrzymanie).

Przykład: Obliczanie sekwencji Collatza

Ten prosty system 2-tagowy jest adaptacją [De Mol, 2008]. Nie używa symbolu zatrzymania, ale zatrzymuje się na dowolnym słowie o długości mniejszej niż 2 i oblicza nieco zmodyfikowaną wersję sekwencji Collatza .

W oryginalnej sekwencji Collatza następcą n jest albo n / 2 (dla parzystego n ) albo 3 n + 1 (dla nieparzystego n ). Wartość 3 n + 1 jest wyraźnie parzysta dla nieparzystych n , stąd następny wyraz po 3 n + 1 to z pewnością 3 n + 1 / 2 . 3 n + 1/2 dla W sekwencji obliczonej przez system znaczników poniżej pomijamy ten krok pośredni, stąd następnikiem n jest nieparzystych rz .

W tym systemie znaczników dodatnia liczba całkowita n jest reprezentowana przez słowo aa...a z n a. 

System 2-tagowy Alfabet: {a,b,c} Reguły produkcji: a --> bc b --> a c --> aaa Obliczenie Początkowe słowo: aaa <--> n=3 abc cbc caaa aaaaa <--> 5 aaabc abcbc cbcbc cbcaaa caaaaaa aaaaaaaa <--> 8 aaaaaabc aaaabcbc aabcbcbc bcbcbcbc bcbcbca bcbcaa bcaaa aaaa <--> 4 aabc bcbc bca aa <--> 2 pne a <--> 1 (stop)

Kompletność Turinga systemów m -tag

Dla każdego m > 1 zbiór systemów m -znaczników jest kompletny według Turinga ; tj. dla każdego m > 1 jest tak, że dla dowolnej maszyny Turinga T istnieje system znaczników m , który emuluje T . W szczególności, system 2-tagowy może być skonstruowany tak, aby naśladował uniwersalną maszynę Turinga , jak to zrobili Wang 1963 oraz Cocke i Minsky 1964.

I odwrotnie, można wykazać, że maszyna Turinga jest uniwersalną maszyną Turinga, udowadniając, że może emulować kompletną dla Turinga klasę systemów m -tag. Na przykład Rogozhin 1996 udowodnił uniwersalność klasy systemów dwuznacznikowych z alfabetem { a 1 , ..., an a , H } i odpowiadającymi im produkcjami { n a n W 1 , ..., a n a n W n- 1 , a na n , H }, gdzie W k to słowa niepuste; następnie udowodnił uniwersalność bardzo małej (4-stanowej, 6-symbolowej) maszyny Turinga, pokazując, że może ona symulować tę klasę systemów znaczników.

Problem zatrzymania 2 znaczników

Ta wersja problemu zatrzymania należy do najprostszych, najłatwiejszych do opisania nierozstrzygalnych problemów decyzyjnych :

Biorąc pod uwagę dowolną dodatnią liczbę całkowitą n i listę n +1 dowolnych słów P 1 , P 2 ,..., P n , Q w alfabecie {1,2,..., n }, czy wielokrotne zastosowanie znacznika operacja t : ijX → XP i ostatecznie przekształcę Q w słowo o długości mniejszej niż 2? To znaczy, czy ciąg Q , t 1 ( Q ), t 2 ( Q ), t 3 ( Q ), ... zakończyć?

Uwaga historyczna dotycząca definicji systemu znaczników

Powyższa definicja różni się od tej z Post 1943, której systemy znaczników nie używają symbolu zatrzymania, ale raczej zatrzymują się tylko na pustym słowie, przy czym operacja znacznika t jest zdefiniowana w następujący sposób:

  • Jeżeli x oznacza skrajny lewy symbol niepustego słowa S , to t ( S ) jest operacją polegającą na dołączeniu najpierw słowa P(x) do prawego końca S , a następnie usunięciu m skrajnych lewych symboli wyniku — usunięciu wszystkich jeśli jest mniej niż m symboli.

Powyższa uwaga dotycząca zupełności Turinga zbioru m -systemów znaczników, dla dowolnego m > 1, odnosi się również do tych systemów znaczników pierwotnie zdefiniowanych przez Posta.

Pochodzenie nazwy „tag”

Zgodnie z przypisem w Post 1943, BP Gill zasugerował nazwę dla wcześniejszego wariantu problemu, w którym pierwsze m symboli pozostaje nietkniętych, ale raczej znacznik wskazujący aktualną pozycję przesuwa się w prawo o m symboli na każdym kroku. Nazwa problemu ustalenia, czy znacznik wyboru kiedykolwiek dotknie końca sekwencji, została następnie nazwana „problemem tagu”, odnosząc się do dziecięcej gry w tag .

Cykliczne systemy tagów

0 Cykliczny system tagów jest modyfikacją oryginalnego systemu tagów. Alfabet składa się tylko z dwóch symboli i 1 , a zasady produkcji obejmują listę produkcji rozpatrywanych sekwencyjnie, z powrotem na początek listy po rozważeniu „ostatniej” produkcji na liście. Dla każdej produkcji badany jest najbardziej wysunięty na lewo symbol słowa — jeśli symbolem jest 1 , bieżąca produkcja jest dodawana na prawym końcu słowa; jeśli jest symbolem 0 , do słowa nie są dołączane żadne znaki; w obu przypadkach symbol znajdujący się najbardziej po lewej stronie jest następnie usuwany. System zatrzymuje się, jeśli i kiedy słowo staje się puste.

Przykład 

Cykliczny system znaczników Produkcje: (010, 000, 1111) Słowo początkowe obliczeń: 11001 Słowo produkcji ---------- -------------- 010 11001 000 1001010 1111 001010000 010 01010000 000 1010000 1111 010000000 010 10000000 . . . .

Cykliczne systemy znaczników zostały stworzone przez Matthew Cooka i zostały użyte w demonstracji Cooka, że ​​automat komórkowy Reguły 110 jest uniwersalny. Kluczową częścią demonstracji było to, że cykliczne systemy znaczników mogą emulować klasę systemów znaczników Turinga .

Emulacja systemów znaczników przez cykliczne systemy znaczników

System m-tag z alfabetem { a 1 , ... , an Q } i odpowiadającymi mu produkcjami { P 1 , ..., P n } jest emulowany przez cykliczny system tagów z m*n produkcjami ( 1 , .. ., Q n , -, -, ..., -), gdzie wszystkie oprócz pierwszych n produkcji są łańcuchem pustym (oznaczonym przez ' - '). Qk _ są Pk kodowaniami odpowiednich , uzyskany przez zastąpienie każdego symbolu alfabetu systemu znaczników ciągiem binarnym o długości n w następujący sposób (należy je zastosować również do początkowego słowa w obliczeniach systemu znaczników): 

 za  1  = 100...00  za  2  = 010...00 . .  .   za  n  = 000...01

0 Oznacza to, że k jest zakodowane jako łańcuch binarny z 1 na k- tej pozycji od lewej i gdzie indziej. Kolejne wiersze obliczeń systemu znaczników będą wówczas zakodowane jako co ( m*n ) wiersz jego emulacji przez cykliczny system znaczników.

Przykład

Jest to bardzo mały przykład ilustrujący technikę emulacji.

System 2-tag Reguły produkcji: (a --> bb, b --> abH, H --> H) Kodowanie alfabetu: a = 100, b = 010, H = 001 Kodowanie produkcji: (bb = 010 010, abH = 100 010 001, H = 001) Cykliczny system znaczników Produkcje: (010 010, 100 010 001, 001, -, -, -) Obliczenie systemu znaczników Słowo początkowe: ba abH Hbb (zatrzymanie) Obliczenie systemu znaczników cyklicznych Słowo początkowe: 010 100 (=ba) Słowo produkcji ------------------------ ---------------- * 010 010 010 100 (=ba) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 emulowane zatrzymanie --> 001 010 010 (=Hbb) 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ...

Co szósta linia (oznaczona przez „ * ”) generowana przez cykliczny system znaczników jest kodowaniem odpowiedniej linii obliczeń systemu znaczników, aż do osiągnięcia emulowanego zatrzymania.

Zobacz też

  •   Cocke, Jan ; Minsky, Marvin (1964). „Uniwersalność systemów znaczników z P = 2”. dr hab. Oblicz. Mach . 11 : 15–20. doi : 10.1145/321203.321206 . hdl : 1721.1/6107 . S2CID 2799125 .
  • De Mol, Liesbeth (styczeń 2008). „Systemy tagów i funkcje podobne do Collatza” . Informatyka teoretyczna . 390 (1): 92–101. doi : 10.1016/j.tcs.2007.10.020 . hdl : 1854/LU-436211 .
  •   Marvin Minsky 1961, Recursive Unsolvability of Post's Problem of „Tag” and other Topics in Theory of Turing Machines”, The Annals of Mathematics, 2 ser., Vol. 74, nr 3. (listopad 1961), s. 437 –455. JSTOR 1970290 .
  •   Minsky, Marvin (1967). Obliczenia: maszyny skończone i nieskończone . Englewoord Cliffs, NJ: Prentice – Hall, Inc., str. 267–273. LCCN 67-12342 .
W rozdziale 14 zatytułowanym „Bardzo proste podstawy obliczalności” Minsky przedstawia bardzo czytelny (i przykładowy) podrozdział 14.6 Problem „znaczników” i monogenicznych systemów kanonicznych ( s. 267–273 ) (ta podsekcja jest indeksowana jako „ system znaczników"). Minsky odnosi swoje frustrujące doświadczenia do ogólnego problemu: „Post uznał ten (00, 1101) problem za„ nierozwiązywalny ”, podobnie jak ja, nawet z pomocą komputera”. Komentuje, że „skuteczny sposób decydowania, dla dowolnego ciągu S, czy ten proces kiedykolwiek się powtórzy, gdy zacznie się od S”, jest nieznany, chociaż udowodniono, że kilka konkretnych przypadków jest nierozwiązywalnych. W szczególności wspomina twierdzenie i wniosek Cocke'a 1964.
  • Post, E .: „Formalne redukcje kombinatorycznego problemu decyzyjnego”, American Journal of Mathematics , 65 (2), 197–215 (1943). (Systemy znaczników są wprowadzone na s. 203ff .)
  • Rogozhin, Yu .: „Małe uniwersalne maszyny Turinga”, Theoret. Oblicz. nauka 168 , 215-240, 1996.
  • Wang, H .: „Systemy znaczników i systemy opóźnień”, Math. Annalen 152 , 65–74, 1963.

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Tag_system&oldid=1137881217 ”