[Automata] Turing Machine(튜링 기계)

Turing Machine

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

# Turing Machine

Turing machine는 튜링 기계라고 불리는 sequence를 가진 tape를 읽어서 데이터를 처리하는 기계이다.

Automata에서 배우고자 하는 부분은 튜링 기계가 무엇인지보다 어떤 방식으로 데이터를 처리하는지에 대해서 이해해하는 것이 중요하다.

Turing machine, 즉 TM 방식은 Stack을 사용하는 PDA보다 더 효율적이다.

Sequence cell들을 tape을 통해서 읽어나가며 데이터를 처리하면서도 pointer의 개념을 사용하여 특정 cell들을 읽어낸다.

포인터를 오른쪽으로 옮겨가며 하나씩 데이터를 읽어낼지 변경할지 등을 고려하여 작업이 수행되는 방식을 가지고 있다.

또한 원하는 데이터가 아닐 경우에는 Halting state을 사용해서 종료하거나 원하는 결과가 산출되었을 경우 마찬가지로 Halting state를 사용해서 종료할 수 있다.

따라서 Start 또는 Initial state와 Halting state가 TM에는 states로 존재한다.

하지만 PDA나 NFA, DFA처럼 별도의 Final state는 존재하지 않는다.

한마디로 Halting State가 Final state가 될 수도 있고 Fail state가 될 수도 있다는 것이다.

 

---

# Formal Definition

TM의 Formal definition을 보면 아래와 같다.

• K is a set whose elements are called states.
• Σ is an alphabet.
• ▷, ⊔, ->, <- are constant symbols.
• ▷ is a left end symbol.
• ⊔ is a blank symbol.
• -> is a moving right symbol.
• <- is a moving left symbol.
• s is a initial state which is a element of K.
• H is a halting state which is a subset of K.
• σ is a transition function; (K-H) x (Σ U {▷, ⊔}) -> K x (Σ U {⊔, <-, ->}); for every q ∈ (K-H), if σ(q,▷) = (P, b) then b is ->

---