Dlaczego maszyny Turinga liniowo ograniczone są bardziej wydajne niż automaty o stanie skończonym?

11

Miałem wrażenie, że nasze komputery, będąc skończone, ostatecznie nie są potężniejsze niż (wyjątkowo duże) skończone maszyny stanowe. Jednak maszyny Turinga liniowo ograniczone są również skończone, ale wydaje się, że zwykłe języki są ściśle niewłaściwym podzbiorem języków wrażliwych na kontekst.

Oczywiście czegoś tu brakuje. Co się dzieje?

Ben I.
źródło

Odpowiedzi:

21

Maszyna Turinga ograniczona liniowo jest ograniczona do taśmy, której długość jest funkcją liniową długości wejścia.

Gdyby limit długości był stały, maszyna nie byłaby mocniejsza niż DFA. Jednak DFA nie może rozwinąć większej liczby stanów, aby poradzić sobie z dłuższym wejściem, co w rzeczywistości może zrobić LBTM (przyjmując stan za całą konfigurację maszyny). Zatem LBTM jest ściśle potężniejszy.

rici
źródło
6
Jest z tym ciekawy wynik. Każda maszyna Turinga działająca w przestrzeni akceptuje zwykły język. o(loglogn)
skankhunt42
@ skankhunt42, dlaczego tak jest?
Ben I.
@ skankhunt42: Popraw mnie, jeśli się mylę, ale… każda TM działająca w przestrzeń musi działać w czas. Ale nietrudno jest pokazać, że dowolna baza TM działająca w czasie decyduje o języku, który można określić również w czasie . Następnie istnieje pewna stała taka, że ​​pierwsze znaków wejścia określają, czy wejście jest w języku. Ale wtedy język jest oczywiście regularny: wystarczy dołączyć stan dla każdego prefiksu w . Czy coś brakuje? Gdzie jest mój błąd? kloglogn2kloglogn=2log(logkn)=logkno(n)O(1)cNc0ic{0,1}i
wchargin 18.04.17
@Choirbean Wymaga dowodu przy użyciu sekwencji krzyżujących. Możesz to sprawdzić tutaj cs.stackexchange.com/questions/7372/… .
skankhunt42 18.04.17
@wchargin Myślę, że błędem może być twierdzenie, że TM działa w czasie ponieważ musisz uwzględnić pozycję głowy taśmy wejściowej również podczas liczenia liczby konfiguracji. Myślę więc, że TM działa w czasie . 2kloglognn2kloglogn
skankhunt42
4

Myślę, że najpierw musimy zrozumieć opis maszyny i rozmiar wejściowy, aby porównanie dotyczyło tylko poprawnych obiektów. Powiedzmy, że N jest rozmiarem wejściowym. Oznacza to, że maszyny będą miały te ograniczenia zasobów.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)MMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Teraz tutaj jest bardziej wyrazisty niż . Jest tak po prostu dlatego, że ruch taśmy i ograniczenia są ograniczone dla .MAA

Teraz dokonajmy niepoprawnego porównania.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)M×2NMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Tutaj i mają tę samą moc ekspresji. Zauważ jednak, że rozmiar zależy od danych wejściowych w sposób wykładniczy. Wcześniej wielkość nie zależą . Oznacza to, że dla każdego wejścia do konieczne będzie wygenerowanie nowego FA, mimo że pozostaje niezmieniony.AMANANMM

Devendra Bhave
źródło