멀티테이프 튜링 기계

튜링 머신
기계
튜링 기계 등가물 튜링 머신의 예 튜링 머신 갤러리
변형
교류 튜링 기계 신경 튜링 기계 비결정적 튜링 기계 양자 튜링 기계 포스트 튜링 머신 확률적 튜링 기계 읽기 전용 튜링 기계 읽기 전용 우측 이동 튜링 머신 멀티테이프 튜링 기계 멀티 트랙 튜링 기계 대칭 튜링 기계 토탈 튜링 머신 언앰비지터 튜링머신 유니버설 튜링 기계 제노머신
과학
앨런 튜링 범주:튜링머신
v t

멀티 테이프 튜링 기계는 여러 개의 테이프를 사용하는 튜링 기계의 변형이다.각 테이프에는 읽고 쓰는 데 사용되는 고유의 머리가 있다.처음에 입력은 테이프 1에 나타나고, 다른 입력은 공백으로 시작한다.^[1]

이 모델은 직관적으로 단일 테이프 모델보다 훨씬 더 강력해 보이지만, 어떤 멀티 테이프 기계(테이프가 아무리 많더라도)는 2차적으로 더 많은 계산 시간만을 사용하여 단일 테이프 기계로 시뮬레이션할 수 있다.^[2]따라서 다중 테이프 기계는 단일 테이프 기계보다 더 많은 기능을 계산할 수 없으며,^[3] 단일 테이프 기계와 다중 테이프 기계 사이의 변화에 영향을 받는 강력한 복잡성 등급(다항식 시간 등)은 하나도 없다.

형식 정의

k-tape Turing 기계는 6-tuple $M{\displaystyle }$= ${\displaystyle ⟨}$ ${\displaystyle \mathrm{Q}}$,${\displaystyle b}$, ${\displaystyle s}$, b ${\displaystyle ,}$ F , ${\displaystyle \Delta }$ ${\displaystyle ⟩}$ ${\displaystyle$ M$=\langle Q,\Gamma ,s ,b,F,\delta \rangle }$로 설명될 수 있다. 여기서$$:

• ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 유한한 상태 집합임
• ${\displaystyle \mathrm{\gamma }}$ ${\displaystyle \Gamma}$은(는) 테이프 알파벳의 유한 집합이다.
• ${\displaystyle s}$ ${\displaystyle \in }$ ${\displaystyle Q}$ ${\displaystyle s\in Q}$이(가) 초기 상태임
• ${\displaystyle \mathrm{b}}$ ${\displaystyle \in }$ { ${\displaystyle b\in \Gamma}$은(는) 공백 기호임
• ${\displaystyle F}$ ${\displaystyle \subseteq }$ ${\displaystyle Q}$ ${\displaystyle F\subseteq Q}$은(는) 최종 또는 승인 상태의 집합이다.
• ${\$$$$Q\times \Gamma ^{$k}\$오른쪽$화살표 Q\$times \{L,R,S$\}}^{k$}}}}}}}}}}$은 전환 함수라고 하는 부분 함수인데$$, 여기서 k는 테이프 수, L은 좌측 시프트, R은 우측 시프트, S는 시프트가 아니다.

투스택 튜링 머신

2스택 튜링 머신에는 읽기 전용 입력과 2개의 스토리지 테이프가 있다.만약 머리가 테이프에서 왼쪽으로 움직이면, 그 테이프에 빈칸이 인쇄되지만, "도서관"의 한 기호는 인쇄될 수 있다.

참고 항목

• 튜링머신
• 유니버설 튜링 기계
• 교류 튜링 기계
• 확률적 튜링 기계
• 튜링 기계 등가물

참조