읽기 전용 튜링 기계

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

읽기 전용 튜링 기계 또는 양방향 결정론적 유한 상태 자동(2DFA)은 표준 튜링 기계처럼 동작하는 연산성 모델의 일종이며 입력 테이프에 쓸 수 없는 경우를 제외하고 입력 전반에 걸쳐 양방향으로 이동할 수 있다.베어 형태의 기계는 계산력에서 결정론적 유한 자동화와 동등하므로 정규 언어만 구문 분석할 수 있다.

이론

9-투플에 의해 표준 튜링 머신을 정의한다.

${\displaystyle M}$=${\displaystyle }$( Q${\displaystyle }$, ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle \mathrm{\delta }}$ ,${\displaystyle \Delta }$, s${\displaystyle }$, ${\displaystyle t}$, ${\displaystyle r}$) ${\displaystyle M=(Q,\Sigma ,\Gamma ,\dash ,\_,\delta ,s,t,r)$ 여기서$$

• ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 유한한 상태 집합이다.
• ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \Sigma}$은(는$$) 입력 알파벳의 유한 집합이다.
• ${\displaystyle \mathrm{\gamma }}$ ${\displaystyle \Gamma}$은(는) 유한 테이프 문자임.
• ${\displaystyle ⊢\in }$ - -${\displaystyle }${ ${\displaystyle \vdash \in \Gamma$ -$\Sigma }$이(가) 왼쪽 엔드마커;
• ${\displaystyle \mathrm{\_}}$∈ -${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \_\in \Gamma$ -$\Sigma }$이(가) 빈 기호임.
• ${\displaystyle \delta$$$$Q\time \Gamma \rightarrow Q\time \Gamma \times \{L,R\}}$은(는) 전환 기능이다.
• ${\displaystyle s}$ ${\displaystyle \in }$ ${\displaystyle Q}$ ${\displaystyle s\in Q}$이(가) 시작 상태임.
• ${\displaystyle t}$ ${\displaystyle \in }$ ${\displaystyle Q}$ ${\displaystyle t\in Q}$이(가) 허용 상태임.
• ${\displaystyle r}$ ${\displaystyle \in }$ Q${\displaystyle }$, ${\displaystyle r}$ ${\displaystyle \ne }$ t ${\displaystyle r\in$Q$,$ $~r\neq t}$이(가) reject 상태임.

So given initial state ${\displaystyle q}$ reading symbol ${\displaystyle a}$, we have a transition defined by ${\displaystyle \delta (q,a)=(q_{2},a_{2},d)}$ which replaces ${\displaystyle a}$ with ${\displaystyle a_{2}}$, transitions to state ${\displa$$ystyle q_{2$ "읽기 헤드"를 d $방향{\displaystyle }$ d ${\displaystyle d}($왼쪽 또는 오른쪽)으로 이동하여 다음 입력을 읽는다.^[1]그러나 당사의 2DFA 읽기 전용 기계에서는 $a{\displaystyle }$= ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}: 항상$$

이 모델은 현재 DFA와 동등하다.그 증거는 주어진 상태에서 제어장치를 사용하여 역추적 결과를 나열하는 표를 만드는 것을 포함한다. 계산을 시작할 때, 이것은 단순히 그 상태에서 왼쪽 엔드마커를 지나치려고 한 결과일 뿐이다.각 오른쪽 이동 시 이전 표 값과 이전 셀에 있던 문자를 사용하여 표를 업데이트할 수 있다.원래의 헤드 컨트롤은 일정한 수의 상태를 가지고 있었고, 테이프 알파벳에는 일정한 수의 상태가 있으므로, 테이블은 고정된 크기를 가지므로, 따라서 다른 유한 상태 기계에 의해 계산될 수 있다.그러나 이 기계는 절대 후진할 필요가 없으며, 따라서 DFA이다.

변형

이 모델의 몇 가지 변형도 DFA와 동등하다.특히 비결정론적 사례(한 상태에서 동일한 입력으로 여러 상태로 전환될 수 있는 경우)는 DFA로 축소할 수 있다.

이 모델의 다른 변형들은 더 많은 계산 복잡성을 허용한다.단일 무한 스택으로 모델은 튜링 기계에 의해 계산 가능한 모든 언어를 선형 시간으로 구문 분석할 수 있다(^[2]적어도).특히 {abcⁿⁿⁿ} 언어는 a와 b의 수가 동일한지 먼저 확인한 다음 b와 c의 수가 동일한지 되감아 확인하는 알고리즘으로 구문 분석할 수 있다.비결정적인 언어의 추가적 도움으로 그 기계는 문맥이 없는 언어를 구문 분석할 수 있다.두 개의 무한 스택이 있는 이 기계는 튜링과 동등하며 모든 반복적인 공식 언어를 구문 분석할 수 있다.

기계에 여러 개의 테이프 헤드가 허용되면 비결정성 허용 여부에 따라 L 또는 NL로 모든 언어를 구문 분석할 수 있다.^[3]

적용들

범용 튜링 기계의 정의에 읽기 전용 튜링 기계가 사용되어 모델링할 튜링 기계의 정의를 수용하며, 그 이후에는 표준 튜링 기계의 연산이 계속된다.

현대 연구에서 모델은 양자 유한 자동 또는 결정론적 확률론적 자동자의 새로운 복잡도 등급을 설명하는 데 중요해졌다.^[4][5]

참고 항목

• 계산성
• 튜링 기계 등가물
• 스택 머신
• 큐 오토매틱
• 양자 컴퓨터

참조

외부 링크

• 아담 웨버의 유한 상태 오토마타에 관한 연구