Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym , stan akceptacji i stan odrzucenia ). Zauważ, że zezwalam na dowolne (skończone) alfabety taśmowe (tzn. Alfabet na taśmie nie jest ograniczony do równego alfabetowi wejściowemu).
Dla wygody zadzwoń do klasy języków rozpoznawalnych przez takie TM . Mam kilka pytań na temat tej klasy:
- Czy był wcześniej badany?
- Czy wiadomo, że równa się innym interesującym klasom złożoności / obliczalności?
- Czy klasa odporna na zmiany w modelu. Na przykład, jeśli zastosowane bazy TM mogą pozostać na miejscu podczas jednego przejścia (w przeciwieństwie do zawsze poruszania się w lewo lub w prawo) lub jeśli taśma ma być nieskończona w obu kierunkach zamiast tylko w prawo, to klasa języków rozpoznawalnych przez 3-stanowe 1-taśmy TM zmieniają się?
- Jak odnosi się do klasy zwykłych języków, ? (W szczególności, czy każdy zwykły język w ?)
(Raczej pobieżne) wyszukiwanie przyniosło tylko ten post cs.stackexchange, który jest istotny, ale nie odpowiada na moje pytania i ten artykuł , którego nie przeczytałem wystarczająco szczegółowo, aby mieć pewność, że dotyczy on dokładnie klasy a nie podobna, ale inna klasa (praca twierdzi, że (1) każdy język w jest rozstrzygalny oraz (2) że i są odrębnymi klasami z niepustym przecięciem). Jak wskazano w komentarzach postu cs.stackexchange, tego rodzaju TM można uznać za bardzo szczególne automaty komórkowe, więc może ktoś, kto zna literaturę na temat teorii automatów komórkowych, mógłby pomóc.
źródło
Odpowiedzi:
Bestia jest niezwykle potężna , na przykład możemy zbudować TMM który akceptuje każdy ciąg formularza
i odrzuca każdy ciąg formularza
Chodzi o przekształcenie pierwszegor w R a następnie pozwólcie głowie sięgnąć do środka struny, a następnie wykonać „bezpaństwowy” zygzak; jeśli to osiągnieA przed R to akceptuje.
Nieformalny opis:
Przykład:
Ta technika zygzakowata jest stosowana w najmniejszej 2-stanowej uniwersalnej maszynie Turinga (ma 18 symboli) zbudowanej przez Rogozhina (Rogozhin 1996. TCS, 168 (2): 215–240)).
Należy na to zwrócić uwagę, aby to udowodnićM zatrzymuje się na wszystkich wejściach (pamiętaj tylko, że odrzuca na pustych wejściach, a wszystkie symbole nie-zatrzymujące się „zbiegają”) < lub > które nie mogą prowadzić do nieskończonej pętli).
Jak skomentował DavidG, językL(M) rozpoznawane przez M jest nadzbiorem LY (to znaczy LY⊂L(M) ), ale nie zawiera żadnego ciągu z LN (to znaczy L(M)∩LN=∅ ) i - jak skomentował MikhailRudoy - wystarczy, aby to udowodnić L(M) nie jest regularny.
Rzeczywiście, jeśliL(M) jest również regularny L(M)∩{r0∗1∗A}=LY={r0n1mA∣m≤n} byłoby regularne (co nie polega na prostym zastosowaniu lematu pompującego); prowadząc do sprzeczności.
WięcL(M) nie jest regularny .
... Ale jak wszyscy superbohaterowieC3 ma piętę Achille'a: nawet nie rozpoznaje regularności:
Nieformalnie może korzystać tylko z lewej stronyb1... (b jest pustym symbolem) lub prawą mgłą 1b... jako haczyk i „rozszerzać się” w przeciwnym kierunku; ale ostateczna akceptacja lub odrzucenie nie może znajdować się na pustym symbolu po przeciwnej stronie, więc można to zrobić tylko na wewnętrznej stronie1 i zaczynając od wystarczająco długiego wejścia, można go „sfałszować”, rozciągając go o jeden.
Wreszcie - po przeczytaniu artykułu - mogę potwierdzić, że opisana w nim jednostanowa TM pasuje do twojegoC3 klasa ... (więc nic nowego tutaj :-) ... a język użyty przez autora do udowodnienia, że zawiera nieregularne języki, jest bardzo podobny do mojego.
źródło
Nie doceniłem mocyC3 ... właściwie to nie jest zbyt daleko od Hyperkomputera !
(Publikuję to jako osobną odpowiedź dla większej przejrzystości)
Możemy zbudować maszynę Turinga w jednym stanieM który akceptuje ciągi formularza:
i odrzuca ciągi formularza:
Pomysł i konstrukcja jest podobna do tej z poprzedniej odpowiedzi: przekształć pierwsząa w A , niech głowa dotrze do środka struny, a następnie wykona „bezstanowy” zygzak, ale przejścia „implementują” „licznik binarny” w pierwszej połowie w ten sposób: Z (Zero) odbij głowę z powrotem w prawo i przekonwertujZ w S (Jeden) następnym razem, gdy głowa dotrze do S przekształć go w ) i niech głowa przesunie się w lewo; kiedy głowa osiągnie) przekształć to w Z . Druga połowa łańcucha zachowuje się jak jednoargumentowy licznik.
Przejścia są następujące:
Przykład:
Należy na to zwrócić uwagę, aby to udowodnićM zatrzymuje się na wszystkich wejściach (pamiętaj tylko, że odrzuca na pustych wejściach, a wszystkie nie zatrzymujące się symbole przechodzą cyklicznie) (,S,Z lub <,> które nie mogą prowadzić do nieskończonej pętli).
JęzykL(M) jest nadzbiorem LY (LY⊂L(M) ) i nie zawiera ciągów z LN (L(M)∩LN=∅ ).
Przypuszczam, żeL(M) jest bezkontekstowy , a zatem - poprzez właściwości zamykania świetlówek kompaktowych, przecinając je ze zwykłym językiem{r0∗1∗A} stworzyć język CF:
Ale poprzez proste zastosowanie Lemmy Ogdena dla CFL możemy to udowodnićLY∉CFL : wybierz wystarczająco długo s∈LY i zaznacz wszystkie 0 s; co najmniej jedno zero może być pompowane i niezależnie od liczby1s w ciągu pompującym wykładniczy wzrost 2n prowadzi do łańcucha ∉LY ).
WięcL(M) nie jest wolny od kontekstu .
... teraz zastanawiam się, czy jest to kolejna odpowiedź „odkrywania koła”, czy jest to nowy (mały) wynik.
źródło
W tej odpowiedzi zakłada się, że maszyny Turinga mają dwustronne nieskończone taśmy. Roszczenia nie dotyczą jednokierunkowych taśm nieskończonych.
Pozwól mi najpierw zdefiniować klasę językówC′3 jako klasa wszystkich języków rozstrzygalna przez maszyny Turinga z jedną taśmą z 3 stanami (C3 została zdefiniowana jako klasa języków rozpoznawalna przez maszyny Turinga z jedną taśmą z 3 stanami). Przedstawiłem klasęC′3 ponieważ w mojej oryginalnej odpowiedzi nieświadomie zamieniłem klasy C3 i C′3 (Rozważyłem tylko klasę C′3 ).
Ta odpowiedź jest bardziej uzupełnieniem odpowiedzi @MarzioDeBiasi. Pokazał, że zajęciaC3 i C′3 nie są zawarte w CFL, a zatem zawierają dość interesujące języki. Jednak, jak pokażę w tym poście, każdy językL w C′3 ma właściwość ustawioną {1n;n∈N∖{0}} jest albo w L lub w jego uzupełnieniu LC . A zatemC′3 jest również bardzo restrykcyjne, np. zawiera tylko trywialne, jednoargumentowe języki{} , {ε} , {1n;n∈N} i {1n;n∈N∖{0}} . KlasaC3 zawiera nieco więcej jednojęzycznych języków. Utrzymuje jednak, że jeśliL∈C3 i 1n∈L dla n≥1 , następnie 1m∈L dla wszystkich m≥n . Prostym następstwem jest to, że nie wszystkie zwykłe języki są w językuC3 ani w C′3 . Również język{1} nie jest w C3 ani w C′3 .
Za roszczenie (pogrubione) okołoC′3 , wystarczy udowodnić, że maszyna Turinga z jedną taśmą M z 3 stanami, które zawsze zatrzymują albo akceptują, albo odrzucają wszystkie ciągi {1n;n∈N∖{0}} . Załóżmy, że ciąg formularza1n , n∈N∖{0} , jest podane do M . Istnieją trzy przypadki:
1) KiedyM czyta 1, przyjmuje lub odrzuca.
2) KiedyM czyta 1, przesuwa głowę w lewo. Jeśli chcemyM aby zatrzymać na tym wejściu, musi zaakceptować, odrzucić lub przejść w prawo na pusty symbol. Dlatego nigdy nie odwiedza komórki po prawej stronie początkowej komórki taśmy. Gdyby tak było, działałoby wiecznie na wejściu 1.
3) KiedyM odczytuje 1, przesuwa głowę w prawo. Wynika z tego, że pon kroki, zawartość taśmy jest An gdzie A to jakiś symbol z alfabetu taśmy i nagłówka M jest na lewym pustym symbolu po prawej stronie ostatniego A . Jeśli chcemyM aby zatrzymać na tym wejściu, musi zaakceptować, odrzucić lub przesunąć w lewo na pusty symbol. Jak w przypadku 2), szefM will now never visit the cell directly to the left of the rightmost A . If it would, then M would run forever on input 1.
It is clear that in all three casesM accepts all strings from the set {1n;n∈N∖{0}} or it rejects them all.
The proof of the claim (in bold) aboutC3 follows the same line as above. We take a one-tape 3-state Turing machine M that accepts a string 1n for some n≥1 . Suppose M is given an input 1m for m≥n . We have to prove that M accepts this input. We have 3 cases:
1) WhenM reads 1, it accepts.
2) WhenM reads 1, it moves the head to the left. Because M accepts the input 1n , it has to accept or move to the right on the blank symbol. Hence, it never visits the n th cell to the right of the initial cell. If it would, it would run forever on input 1n .
3) WhenM reads 1, it moves the head to the right. It follows that after m steps, the content of the tape is Am where A is some symbol from the tape alphabet and the head of M is on the leftmost blank symbol to the right of the last A . Because M accepts the input 1n , it must accept or move to the left on the blank symbol. As in case 2), the head of M will now never visit the n th cell to the left of the rightmost A . This is because on the input 1n , M does not visit the cell directly left of the initial cell, because it contains the blank symbol and if it would read it, it would run forever.
It is clear that in all three casesM accepts all strings from the set {1m;m≥n} .
źródło