[암호학] 12. Turing Machine

Turing Machine

이제 우리의 컴퓨터와 가장 가까운 튜링 머신이다.

튜링 머신이 가장 강력한 머신임은 모르지만 모든 문제를 풀 수 있는 General Machine이라고 한다.

다른 말로 튜링 머신으로 풀 수 없는 문제는 어떤 머신을 가지고 와도 해결할 수 없다.

 

우선 튜링머신의 구조는 아래와 같다.

Turing Machine

가장 위쪽부터 작은 네모들의 집합이 Tape이다.

Tape에 symbol을 남길 수 있다.

그리고 Tape에 들어있는 각 네모 칸이 Cell이고 이 곳 하나당 symbol하나를 기록할 수 있다.

현재 Cell위치를 가리키는 화살표가 R/W head이다.

head를 이용하여 현재 Cell에 적힌 symbol을 읽거나 새로 쓸 수 있다.

밑에 있는 P, Q, R, S는 각각 state를 의미하고 현재 Q를 가리키는 화살표가 Finite Control이다.

 

튜링머신은 상태가 변화할 때 head의 위치와 현재 셀의 symbol을 바꿀 수 있다.

Deterministic Turing Machine

Turing Machine도 오토마타와 같이 결정적과 비결정적으로 나뉘는데 Deterministic부터 알아보자.

$M = (Q, \Sigma, T, q, F, s)$

• $Q$ : 상태들의 집합
• $\Sigma$ : 입력받은 String
• $T$ : Tape Symbol의 집합
• $q$ : 초기 상태
• $F$ : AC를 받는 상태들의 집합
• $s$ : Transition Function

앞에서 DFA를 했기 때문에 위 용어들이 낯설지 않고 쉽게 알아볼 수 있다.

추가된건 $T$가 추가됐는데 이 때문에 DTM의 행동이 달라진다.

 

보통 $(q, a) \rightarrow (r,b,L|R|S)$로 나타낸다.

이 의미는 다음과 같다.

현재 상태가 $q$이고 현재 cell에 $a$라고 써 있으면 상태를 $r$로 바꾸고 cell에 $b$라고 쓴 뒤 $L$(왼쪽) | $R$(오른쪽) | $S$(제자리) 중 하나로 이동한다.

우리가 사용하는 컴퓨터에는 $(q, a) \rightarrow (r, b, L|R|S)$를 잔뜩 써 놓은 규칙에 따라 움직인다고 한다.

 

Non-Deterministic Turing Machine

DFA, NFA차이와 마찬가지도 DTM, NTM차이도 transition function에서 transition relation으로 변화한 형태이다.

DTM은 다음 상태로 가는 경로가 정해진 반면 NTM은 정해져있지 않고 모두 시뮬레이션 한다.

 

Simulation

상태가 이렇게 있다고 하면 DTM은 맨 위 경로로 가게 설계해야만 문제를 해결한다고 본다.

하지만 NTM은 위 모든 노드들을 방문하면서 한 가지 경우라도 AC를 받는다면 문제를 해결한 것으로 본다.

재미있는 것은 DTM과 NTM의 성능이 같다는 것이다. (속도 측면이 아니라 문제 해결 측면)

 

---

꽤 긴 시간 컴퓨테이션 이론을 알아봤는데 이를 통해 암호를 위한 배경지식을 쌓았다.

실제로 DFA, NFA를 알고 DTM, NTM을 보니 이해가 더 쉬웠던 것 같다.

 

다음 시간부터는 Complexity Theory로 들어가 필요한 배경지식을 더 쌓고 암호를 알아보러 갈 것이다.