2 스택 PDA와 멀티 테루 튜링 기계의 장점

Question

2 스택 PDA와 멀티 테루 튜링 기계의 장점은 무엇입니까?

2 스택 : 튜링 기계는 하나 왼쪽 테이프와 같은 스택 문맥 sensetive 데이터를 취할 수있는 권리 하나를 사용하는 것과 같이 동작 할 수

2 테이프 : Seperates 입력 및 계산

더 이상?

Answer 1

2 개의 스택 PDA는 튜링 기계처럼 작동 할뿐만 아니라 기능적으로 튜링 기계와 동일합니다. CS 스택 교환에 대한 대답은 This입니다.

This wikipedia 기사에서는 멀티 테일 튜링 기계가 항상 단일 테이프 튜링 기계로 표시 될 수 있으므로 튜링 기계로는 단일 테이프를 계산할 수 없다고 설명합니다. 멀티 테잎 기계가 더 빨라질 것이라는 점에서 여러 개의 테이프를 갖는 것이 이점이 될 수 있습니다. 이 답변의

Answer 2

쌍 조각,

는 첫째, 튜링 기계에 의해 인정 언어의 클래스가 (상황에 맞는 당신이 직접 만든 오토마타에서 얻을 언어의 클래스)는 재귀 적으로 열거의 민감한 상황이 아니다.

두 번째 부분은 우리가 질문을 조정한다고 생각하면 그렇습니다. 2 스택 PDA는 TM만큼 견고합니다. 한 방향으로 만 끊임없이 테이프를 사용하는 TM 모델을 사용하고 있다고 생각하는 것은 다소 간단합니다 (두 방향 모두 훨씬 어렵지 않고 그와 동등 함).

평등을 보려면 첫 번째 스택을 인기있는 위치의 왼쪽에있는 테이프의 내용으로 생각하고 두 번째 스택을 오른쪽의 내용으로 생각하십시오. 두 스택에서 정상적인 "bottom of stack"마커를 눌러 시작한 다음, 오른쪽 스택에서 튀어 나오고 왼쪽으로 밀어 오른쪽으로 이동하거나 왼쪽으로 이동하여 왼쪽으로 이동하여 TM을 시뮬레이션 할 수 있습니다. 왼쪽 스택의 맨 아래에 맞으면 그에 따라 동작합니다 (정지 및 거부 또는 모델에 따라 위치 유지). 오른쪽 스택의 맨 아래에있는 경우 빈 기호를 왼쪽으로 밀면됩니다.

다른 방식과의 관계가 더 분명해야합니다. 즉 TM이있는 2 스택 PDA를 시뮬레이션 할 수 있습니다.

이고 그 내용은 Turing machine tape is infinite in one direction, extending indefinitely to the right. We use one stack to represent the tape content on the finite portion of the tape to the left of the head and another to represent the content of the finite non-blank portion of the tape to the right of the head. The two-stack PDA resembles a move of the TM by suitably pushing and leaping the two stacks입니다.