Czy automat zwijający z dwoma stosami jest równoważny maszynie Turinga?

41

W tej odpowiedzi wspomniano o tym

Skończony automat może rozpoznać zwykły język. Język bezkontekstowy wymaga stosu, a język kontekstowy wymaga dwóch stosów (co jest równoważne z twierdzeniem, że wymaga pełnej maszyny Turinga) .

Chciałem wiedzieć o prawdzie odważnej części powyżej. Czy to prawda, czy nie? Jaki jest dobry sposób na uzyskanie odpowiedzi na to pytanie?

computability turing-machines automata pushdown-automata Lazer
źródło
Pogrubiony tekst zawiera dwa twierdzenia, ale tytuł pytania sugeruje, że interesuje Cię tylko jedno z nich.
Tyson Williams,
@TysonWilliams: tak, więc?
Lazer,
To jest mylące. Nie wiem, dla jakiego podzbioru dwóch twierdzeń chcesz uzasadnienia.
Tyson Williams,
Dla pogrubionego , jak wspomniano w pytaniu.
Lazer,
2
@Lazer: pogrubiony tekst zawiera dwie instrukcje („CSL wymaga dwóch stosów”, „dwa stosy są równoważne TM”). Ponieważ CSL jest właściwym podzbiorem RE, tylko jeden może być prawdziwy.
Raphael

Odpowiedzi:

38

Dwa bity do tej odpowiedzi;

Po pierwsze, klasa języków rozpoznawanych przez Turing Machines nie jest zależna od kontekstu , jest rekurencyjnie wyliczalna (kontekstowa to klasa języków, którą otrzymujesz z automatów z liniowym wiązaniem ).

Druga część, zakładając, że dostosujemy pytanie, jest taka, że ​​tak, PDA z dwoma stosami jest tak potężny jak TM. Nieco łatwiej jest założyć, że używamy modelu TM, który ma taśmę, która jest nieskończona tylko w jednym kierunku (chociaż oba kierunki nie są znacznie trudniejsze i równoważne).

Aby zobaczyć równoważność, pomyśl o pierwszym stosie jako zawartości taśmy po lewej stronie bieżącej pozycji, a o drugim jako zawartości po prawej stronie. Zaczynasz tak:

  • Naciśnij normalne znaczniki „dna stosu” na obu stosach.
  • Wepchnij dane wejściowe do lewego stosu (użyj niedeterminizmu, aby „odgadnąć” koniec danych wejściowych).
  • Przenieś wszystko na odpowiedni stos (aby zachować porządek).

Teraz możesz zignorować dane wejściowe i zrobić wszystko na zawartości stosów (która symuluje taśmę). Pop, aby czytać i pchać, aby pisać (abyś mógł zmienić „taśmę”, popychając coś innego niż to, co czytasz). Następnie możemy symulować TM, wyskakując z prawego stosu i popychając w lewo, aby przejść w prawo, i odwrotnie, aby przejść w lewo. Jeśli uderzymy w dolny lewy stos, zachowujemy się odpowiednio (zatrzymaj i odrzuć, lub pozostań tam, gdzie Ty, w zależności od modelu), jeśli uderzymy w dolny prawy stos, po prostu popychamy pusty symbol w lewo.

Aby uzyskać pełny formalny dowód, zobacz odpowiedź na inne pytanie .

Relacja w drugą stronę powinna być jeszcze bardziej oczywista, tzn. Że możemy symulować PDA z dwoma stosami za pomocą TM.

Luke Mathieson
źródło