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?
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.
Teraz tutaj jest bardziej wyrazisty niż . Jest tak po prostu dlatego, że ruch taśmy i ograniczenia są ograniczone dla .M A A
Teraz dokonajmy niepoprawnego porównania.
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.A′ M A′ N A N M M
źródło