유튜브 주니온 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로, 테이프는 컴퓨터의 메모리로 치환이 가능하다. 각각의 튜링 머신은 컴퓨터의 응용프로그램으로, 유니버셜 튜링 머신은 컴퓨터의 운영체제로 치환 가능하다(운영체제(유니버셜 튜링 머신)가 각각의 응용프로그램(튜링 머신)을 실행시켜준다).
'Computer Science' 카테고리의 다른 글
| MVC 패턴 (0) | 2021.01.16 |
|---|---|
| 정지 문제 (Halting problem) (0) | 2021.01.14 |