튜링 머신
유튜브 주니온 TV 아무거나 연구소의 <TMItalk. 튜링 머신의 이해> 영상을 보고 내용을 정리했다.
www.youtube.com/watch?v=BOr1waCdv3U&feature=youtu.be
튜링 머신의 이해
다비트 힐베르트
- 20세기 가장 위대한 수학자로 손꼽히는 1인
- 힐베르트 문제 : 20세기에 풀어야 할 23개의 문제 제시
- 힐베르트의 꿈 : 정의와 공리를 입력하면 모든 수학적 명제를 도출해줄 수 있는 만능기계가 있으면 좋지 않을까?
(공리(axiom) : 논리학이나 수학 등의 이론체계에서 가장 기초적인 근거가 되는 명제)
쿠르트 괴델
- 힐베르트의 꿈을 박살낸 수학자
- 불완전성 정리(Incompleteness Threorem) : 페아노 공리계를 포함한 모든 무모순적 공리계는 참인 일부 명제를 증명할 수 없다. -> 기계적인 방식으로 모든 수학적 명제를 도출할 수 없다.
앨런 튜링
- 수학만으로 컴퓨터를 만든 컴퓨터과학의 아버지
- 내가 설계한 튜링 머신은 모든 계산을 할 수 있는 보편적 만능기계인데, 그 기계로도 정지 문제는 풀 수 없다.
-> 모든 수학적 명제를 도출하는 기계를 만들었는데, 그 기계가 풀 수 없는 문제가 있다.
-> 괴델의 불완전성 정리를 뒷받침하는 근거로, 힐베르트의 꿈이 이루어질 수 없다고 주장
(정지 문제 – 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로
그램이 계산을 끝내고 멈출지 아니면 계속 계산할지 판정하는 문제
튜링 머신
- 실존하는 기계가 아닌 수학적 도구(가상의 도구)
- 테이프, 헤드, 상태 기록기, 행동표가 존재
- 용어 정리
- 테이프 : 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어
날 수 있다.
- 헤드 : 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다.
- 기호 집합 : 테이프에 읽고 쓸 수 있는 기호들의 집합
- 상태 집합 : 튜링 머신이 가질 수 있는 상태들의 집합
- 상태 기록기 : 현재 튜링 머신의 상태를 기록하고 있는 장치
- 개시상태 : 상태 기록기가 초기화된 상태
- 종료상태 : 수행이 종료된 상태
- 행동표(명령 테이블) : 특정 상태에서 특정 기호를 읽었을 때 해야할 행동을 지시한다.
튜링 머신 예시
기호 집합 X = {0, 1}
상태 집합 S = {s0, s1, H}, s0 : 초기 상태, H : 종료 상태
|
No. |
현재 상태 |
읽은 기호 |
쓸 기호 |
헤드 이동 |
상태 이동 |
|
1 |
s0 |
0 |
1 |
R |
s1 |
|
2 |
s0 |
1 |
1 |
L |
s1 |
|
3 |
s1 |
0 |
1 |
L |
s0 |
|
4 |
s1 |
1 |
1 |
R |
H |
행동표의 각 행은 간단하게 (헤드의 상태, 적혀있는 숫자, 쓸 숫자, 다음에 움직일 방향, 다음 상태)로 나타낼 수 있다.
ex) No 1 -> (s0, 0, 1, R, s1)
작업 예시
초기 상태
행동 1. 현재 상태 s0, 읽은 기호 0 -> No.1 참조, 다음 상태 s1, 쓸 기호 1, 헤드 오른쪽 이동
행동 2. 현재 상태 s1, 읽은 기호 0 -> No.3 참조, 다음 상태 s0, 쓸 기호 1, 헤드 왼쪽 이동
행동 3. 현재 상태 s0, 읽은 기호 1 -> No.2 참조, 다음 상태 s1, 쓸 기호 1, 헤드 왼쪽 이동
행동 4. 현재 상태 s1, 읽은 기호 0 -> No.3 참조, 다음 상태 s0, 쓸 기호 1, 헤드 왼쪽 이동
단계 5. 현재 상태 s0, 읽은 기호 0 -> No.1 참조, 다음 상태 s1, 쓸 기호 1, 헤드 오른쪽 이동
단계 6. 현재 상태 s1, 읽은 기호 1 -> No.4 참조, 다음 상태 H, 쓸 기호 1, 헤드 오른쪽 이동
현재 상태가 H로 변했으므로 튜링 머신의 동작이 끝난다.
이 튜링머신이 하는 일은? -> 아무것도 기록되어 있지 않은 메모리에 15를 기록한다(어셈블리보다 더 원시적인 방법). 이 방법이 15를 기록하기 위한 가장 효율적인 튜링 머신이다(2개의 상태만으로 기록).
-> 유한 상태 오토마타(Finite state Automata)
튜링 머신의 응용법
- 이론적으로 계산 가능한 모든 것을 할 수 있음(현대 컴퓨터로 불가능한 계산도 가능).
- Computability and Computational Theory
- 컴퓨터는 메모리가 유한하지만 튜링 머신의 테이프 길이는 무한하다고 가정하므로, 튜링 머신이 컴퓨터보다 할 수 있는 일이 더 많다.
클로드 섀넌 : 정보의 최소 단위는 비트, 모든 정보는 0과 1로 표현 가능
튜링머신은 0을 1로, 그리고 1을 0으로 바꿀 수 있다. -> 이 조합으로 and, or, not 연산 표현 가능 -> 사칙연산이 가능 -> 모든 연산이 가능
앨런 튜링
- 튜링 머신은 모든 정보를 처리할 수 있다.
유니버셜 튜링 머신
- 앨런 튜링이 만든 개념
- 임의의 튜링 머신 M의 명령 테이블을 보고 그것을 따라하는 따라쟁이 튜링 머신 UTM을 만들 수 있다.
-> 1을 4개 사용하는 튜링 머신이 있다면(위의 예제), 그것을 따라하는 따라쟁이 튜링 머신(UTM)을 만들 수 있다.
- 어떤 튜링 머신에 대해 UTM이 존재하면, 그 튜링 머신이 존재하는지, 무한히 동작 하는지를 알 수 있다.
튜링 머신에서 헤드는 컴퓨터의 CPU로, 테이프는 컴퓨터의 메모리로 치환이 가능하다. 각각의 튜링 머신은 컴퓨터의 응용프로그램으로, 유니버셜 튜링 머신은 컴퓨터의 운영체제로 치환 가능하다(운영체제(유니버셜 튜링 머신)가 각각의 응용프로그램(튜링 머신)을 실행시켜준다).