[오토마타] Turing Machine (튜링 머신)

 

 

 

1. 튜링머신은 저장 장소 및 입력 출력 수단이 Tape인 오토마타이다.

2. 테이프는 셀들로 나누어져 있으며, 각 셀은 한개의 심벌을 저장한다.

3. Read-Write Head 가 왼쪽 또는 오른쪽 셀로 움직이며 각 이동마다 심벌을 읽거나 쓴다.

 

Turing Machine M은 다음과 같이 정의된다.

M = { Q, ∑, Γ, δ, q₀, □, F }

 

Q : 내부 state들의 집합

∑ : Input alphabet ^[각주:1](Σ ⊆ Γ-{ㅁ})

Γ : Tape alphabet, 테이프에 존재하는 알파벳들의 집합

δ : 전이함수 ^[각주:2](partial function of Q×Γ => Q×Γ×{L,R})

q₀ : 초기 상태(Initial state)

□ : Blank symbol. 공백을 나타내는 특별한 심벌

F : Set of final states

 

전이 함수의 예를 보면

δ(q₀, a) = (q₁, d, R)

 

이 전이 함수는 q0라는 스테이트에서 a라는 input이 들어올 경우(테이프에서 a를 읽을 경우) 알파벳을 d로 바꾸고, state를 q1으로 바꾸고 헤드를 오른쪽으로 옮기라는(테이프의 오른쪽 셀로 이동) 뜻이다.

햇갈릴 수도 있지만 아래의 그림을 보면 쉽게 이해가 간다.

 

 

 

 

튜링머신의 그래프는 아래와 같다. State가 전이되는 input, output, 방향을 적어준다.

물론 같은 State에 머무를때도 똑같이 적어주면 된다. 아래 그래프는 q₁에서 b를 입력받으면 그대로 b를 두고 왼쪽으로 헤드를 옮긴 후 q₂로 전이되고, a를 입력 받으면 a를 b로 바꾸고 헤드를 R로 옮긴 후 q₂로 전이 되는 q₁과 q₂의 전이 그래프를 나타낸다.

 

 

각각 한 상태의 묘사는 baq₁bb와 같은 형태로 할 수 있다. 이 형상은 테이프에 babb라는 알파벳이 쓰여 있고, 헤드는 3번째 b에 위치해 있으며 현재 state는 q₁이라는 뜻이다.

 

그리고 한 형상에서 다른 형상으로의 변화는 ├ 기호를 사용한다.

 

baq₁bb├ baaq₂b

 

라고 되어 있으면 q₁에서 b를 입력 받으면 b를 a로 바꾸고 헤드는 오른쪽으로 이동, 그리고 state는 q₂로 바뀜을 의미한다. 여러번의 변이를 결과를 한번에 보여주고 싶다면 ├ 기호에 *(스타)나 숫자를 붙여서 사용 할 수 있다.

1. 입력 알파벳은 공백 심벌을 포함하지 않는 테이프 알파벳의 부분 집합이다. [본문으로]
2. 전이 함수는 Q×Γ 의 부분함수 + 전이 후 이동할 방향을 나타낸다. [본문으로]