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

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?

— 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,

@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

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