멀티 트랙 튜링 기계

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2018년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

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

멀티랙 튜링 머신은 멀티 테이프 튜링 머신의 특정 유형이다.

표준 n-테이프 튜링 기계에서는 n 헤드가 n 트랙을 따라 독립적으로 움직인다.n트랙 튜링 기계에서는 한 헤드가 모든 트랙에서 동시에 읽고 쓴다.n-트랙 튜링 머신의 테이프 위치에는 테이프 알파벳의 기호가 n개 들어 있다.그것은 표준 튜링 기계와 동등하며 따라서 재귀적으로 열거된 언어들을 정확하게 받아들인다.

형식 정의

A multitrack Turing machine with ${\displaystyle n}$-tapes can be formally defined as a 6-tuple ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$, where

• ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 유한한 상태 집합임
• ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \Sigma}$은(는) 테이프 알파벳이라고 하는 유한한 기호 집합이다.
• ${\displaystyle \Gamma \in Q}$
• ${\displaystyle {q\mathrm{}}_{}}$ 0 ${\displaystyle {}_{}}$ ${\displaystyle Q}$ ${\displaystyle q_{0}\in Q}$이(가) 초기 상태임
• ${\displaystyle F}$ ${\displaystyle \subseteq }$ ${\displaystyle Q}$ ${\displaystyle F\subseteq Q}$은(는) 최종 또는 승인 상태의 집합이다.
• ${\displaystyle \delta :\left(Q\backslash F\times \Sigma ^{n}\right)\rightarrow \left(Q\times \Sigma ^{n}\times \{L,R\}\right)}$ is a partial function called the transition function.

때로는 $\Delta {\displaystyle ({Qi}_{}}$[ x ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$ 2${\displaystyle }$.${\displaystyle }$. . . ${\displaystyle x_{}}$ n${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$,${\displaystyle }$[ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$.${\displaystyle }$. .${\displaystyle }$. . . . . . . .${\displaystyle {}_{}}$. .${\displaystyle }$. . ${\displaystyle d}$) ${\display$ style $\delta \left(Q_{i},$ [$x_{1$},$x_{2$})로 표시되기도 한다$.$$x_{n}]\오른쪽)=(Q_{j},[y_{1},y_{2}...$$y_{n},d$ 여기서 $d{\displaystyle }$ ${\displaystyle \in }${ ${\displaystyle L}$, ${\displaystyle R}$ ${\displaystyle \}}$ ${\displaystyle d\in \{L,R$

A non-deterministic variant can be defined by replacing the transition function ${\displaystyle \delta }$ by a transition relation ${\displaystyle \delta \subseteq \left(Q\backslash F\times \Sigma ^{n}\right)\times \left(Q\times \Sigma ^{n}\times \{L,R\}\right)}$.

표준 튜링 기계와 동등성 증명

이를 통해 투 트랙 튜링 기계가 표준 튜링 기계와 동등하다는 것을 증명할 수 있을 것이다.이것은 N 트랙 튜링 기계로 일반화할 수 있다.L을 반복적으로 열거할 수 있는 언어가 되게 하라.M= $⟨{\displaystyle }$ ${\displaystyle Q}$, ${\displaystyle \mathrm{\sigma }}$ ,${\displaystyle \Delta }$, Δ ,${\displaystyle {q\mathrm{}}_{}}$ , ${\displaystyle {}_{}}$ , F${\displaystyle {}_{}}$⟩ , ${\displaystyle F}$⟩ {\$displaystyle \langle Q,\Sigma ,\Gamma ,\delta ,q_{0}F\rangle }$을(를) L을 받아들이는 표준 튜링 시스템이 되게$$ 하라.렛 M'은 투 트랙 튜링 기계다.M=M'을 입증하려면 M $\subseteq {\displaystyle }$ ${\displaystyle \subseteq }$M$$'과 M' $\subseteq {\displaystyle }$ ${\displaystyle \subseteq }$M으로$$ 표시해야 한다.

• $M\subseteq M'}$

만약 두 번째 트랙을 무시한다면, M과 M'은 분명히 동일하다.

• $M'\subseteq M}$

투 트랙 튜링 기계에 해당하는 원 트랙 튜링 기계의 테이프 알파벳은 순서 쌍으로 구성된다.튜링 기계 M'의 입력 기호 a는 튜링 기계 M의 순서 쌍[x,y]으로 식별할 수 있다.원트랙 튜링 기계는 다음과 같다.

M= ${\displaystyle \langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$ with the transition function ${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x$$_{1},x_{2}]\right)}$

이 기계도 L을 받아들인다.

참조

• 토마스 A.수드캄프(2006년).언어 및 컴퓨터, 제3판.애디슨 웨슬리 ISBN0-321-32221-5.8.6장: 멀티테이프 기계: 페이지 269–271