튜링 머신(Turing Machine)

이전에 사용했던 Pushdown Automata는 모든 정보를 Stack의 Top에서만 접근했기 때문에, 그 아래의 정보를 얻기 위해선 top이 가리키는 정보를 제거해야만 했습니다. 따라서, 그 과정에서 인식되지 않는 언어가 일부 발생합니다.

 

ex) {a^n b^n c^n | n >= 0} 는 NPDA로 처리할 때, a를 스택에 push하고 a를 pop하며 b를 카운트합니다. 그리고, c를 처리할려고 할 때에는 스택이 empty이므로, 진행할 수 없습니다.

 

튜링 머신 (Turing Machine)

위 문제를 해결하기 위해, 튜링머신은 스택 대신 저장공간을 Tape로 사용합니다. Tape는 Cell로 구성된 무한 확장 가능한 1차원 배열의 형태를 띄고 있습니다. 각 셀은 하나의 문자를 저장할 수 있고, Tape는 무한 확장이 가능하므로, 처음과 끝이 없고 접근 순서는 모든 경우를 허용합니다. Head가 가리키는 셀의 문자를 읽고 쓰면서 왼쪽 혹은 오른쪽으로 이동합니다.

 

튜링머신 M은 다음과 같이 정의됩니다.

 

Turing Machine M = (Q, ∑, Γ, δ, q0, □, F)

Q는 내부 상태를 의미합니다.

∑는 입력 기호들의 집합입니다.

Γ는 테이프 기호들의 집합입니다.

δ는 전이 함수입니다.

□는 셀이 공백임을 표시하는 특수기호입니다.

q0는 시작 상태이고, F는 종료 상태들의 집합입니다.

 

전이함수 δ는 Q X Γ → Q X Γ X {L, R} 로 정의됩니다.

이때, 입력 기호들은 공백 문자를 포함하지 않고, 테이프 기호들의 부분집합입니다. (∑ ⊆ Γ - {□})

전이함수의 작성은 다음과 같이 작성합니다.

 

δ(q, σ) → (p, t, X)

q는 현재 상태이고, σ는 현재 Head가 가리키는 셀의 테이프 기호입니다.

p는 다음 상태, t는 현재 Head가 가리키는 셀에 쓰여질 기호입니다.

X는 Head가 이동할 방향입니다.

 

ex) δ(q0, a) → (q1, b, R) 이면, 상태 q0에서 Head가 a를 가리키고 있을 때, a를 b로 변경하고, Head는 오른쪽으로 한칸 움직이고 상태는 q1으로 변환됩니다.

 

튜링 머신은 처리 유닛(Processing Unit)을 보유하고, 각 테이프 셀 내용을 저장할 메모리와 명령어, 전이 함수를 통해 컴퓨터의 동작 표현(프로그램 코드의 기능)의 기능을 가집니다.

 

튜링 머신은 초기 상태(q0)에서 시작하고, Head는 입력 기호의 시작에 위치하고 있습니다. 테이프 셀의 내용을 여러번 읽고 쓰면서 처리가 가능하고, 그 결과는 계속해서 테이프에 저장되어 남아있습니다.

 

튜링 머신의 순간적 묘사는 현재 상태와 테이프의 내용, 헤드의 위치로 표기합니다.

 

ex) q0aa ├ bq0a ├ bbq0 ├ bq1b or q0aa ├* bq1b

 

튜링 머신이 입력 스트링 W를 인식하지 못하는 경우는 크게 2가지로, w ∉ L(M)일 때, 튜링 머신에 미정의 인 경우이거나 (정지) 무한 루프에 빠져, 최종 상태에 도달하지 못하는 경우 (미정지, Halting Problem)로 나뉩니다.

 

여기서 미정의(undefined)란, 머신에 해당 규칙이 존재하지 않아서, 최종 상태에 도달하지 못하고 정지되는 경우를 의미합니다.

 

Turing Computable (튜링 계산 가능, 계산 가능)은 다음 조건을 만족하는 튜링 머신 M이 존재할 때, Domain에 대한 Function f는 Turing Computable 하다고 합니다.

 

M = (Q, ∑, Γ, δ, q0, □, F)

q0w ├* M qf f(w), qf ∈ F, w ∈ Domain

 

Universal Turing Machine

범용 튜링 머신은 하나의 머신이 여러 형태의 계산을 하기 위한 튜링 머신입니다.

기존 표준 튜링 머신의 전이 함수는 특정 계싼을 위해 정의됐기 때문에, 여러 형태의 계산을 위해서 여러 개의 튜링 머신을 설계해야 했습니다.

 

따라서, 표준 튜링 머신 M을 encoding하여, M 자체가 다른 튜링 머신의 데이터로써 사용되게 합니다.

 

범용 튜링머신 Mu는 Encoding 된 M과 M의 입력 스트링 w를 입력으로 가지고, Mu가 M과 w를 처리합니다.

 

von Neumann 모델은 von Neumann Architecture로 구성되고, RAM의 사용, 현대 컴퓨터 구조의 표준 모델로 사용됩니다. 이 모델은 범용 튜링 머신의 원리를 구현하기 위한 모델로써도 사용됐습니다.

 

따라서, 폰노이만 아키텍처는 범용 튜링 머신의 기능을 아키텍처로 확장하고, 구체화했다고 볼 수 있습니다.