- Alan Mathison Turing by wekipedia, Creative Commons Attribution-ShareAlike 3.0 Unported License-
튜링 머신
나온 배경
튜링 머신은 앨런 튜링이란 수학자가 괴델의 불완전성 원리를 증명하기 위해 고안된 장치였다.
즉, 어떤 기계가 있는데, 그 기계는 아주 뛰어나서 그 어떤 기계적인 연산도 처리할 수 있다. 그래서 이 기계로 괴델의 불완전성 원리를 증명하고자 했던 것이 튜링의 원래 의도이자 튜링 머신이 나오게 된 배경이다.
원리
튜링 머신은 인간을 본따서 만든 것이다. 즉, 튜링이 인간이 생각하고 연산하는 과정을 잘 관찰한 뒤에 이를 따라할 수 있도록 튜링 머신의 설계도를 구상한 것이다. 그래서 튜링 머신의 신뢰성은 인간의 연산 행위에 대한 신뢰성에 의존적이라고도 할 수 있다.
인간은 '관찰->연산->기록'과 같은 순서로 연산을 한다. 예를 들어, 곱셈을 한다면 먼저 주어진 식을 읽은 다음에, 머릿속에서 곱셈을 하여서 이 결과를 종이에 적는다. 근데 여기서 매우 중요한 현상을 관찰할 수 있다. 인간은 1과 2를 관찰했지만 2 또는 3이란 다른 결과를 작성할 때가 있다. 즉, 덧셈 연산을 할려고 1과 2를 봤다면, 결과로 3을 적는다. 곱셈 연산을 할려고 1과 2를 봤다면, 결과로 2를 적는다. 즉, 연산이란 행위에는 어떤 상태가 존재한다는 것이다. 그래서 튜링은 이런 것을 모두 고려하여 인간의 연산 행위를 다음과 같이 5개의 요소로 나누었다.
- 상태 확인
- 기호 읽기
- 기호 처리
- 위치 옮기기 또는 멈추기
- 상태 변경
위의 과정을 통해서 덧셈 또는 곱셈과 같은 연산이 가능하다. 뿐만 아니라 모든 연산을 저 행위로 묘사할 수 있다. 최소한 인간이 할 수 있는 연산은 따라할 수 있다. 왜냐면 이 요소들의 기원이 인간이기 때문이다. 그리하여 튜링 머신이란 위의 5가지 요소를 기반으로 명령을 처리하는 기계라고 짤막하게 요약할 수 있다. 이를 위해 튜링 기계는 5 가지 부품으로 구성되어 있다.
- 기호 입력 공간
- 기호
- 입력 공간의 읽기 및 쓰기 장치
- 기계의 상태
- 기계의 명령 규칙표
구체적인 예시와 설명은 아래의 링크를 통해 파악하라.
https://url.kr/p8ly31
보편 튜링 머신
n진법을 이용하여 튜링 머신을 '수'로 표현하기 - 괴델 수 대응
우리는 앞서 튜링 머신에 대해서 살펴봤다. 튜링 머신에는 어떤 수가 입력된다. 그리고 튜링 머신은 이 수를 처리한다. 즉, 당연하게도 튜링 머신이 다루는 데이터는 수라는 것이다.
그런데 튜링 머신이 다루는 데이터뿐만 아니라 튜링 머신 그 자체도 수로 표현할 수 있다. 이는 괴델 수 대응을 이용하면 가능하다.
괴델 수 대응이란 괴델이란 수학자의 이름이 주는 두려움과는 다르게 매우 간단하다. 예를 들어, '먹어'라는 명령을 수로 표현해보자. 이때, 각각의 모음과 자음에 미리 어떤 숫자가 대응되도록 약속했다고 하자. 그렇다면 그 약속대로 '먹어'라는 명령어는 아래와 같이 대응시킬 수 있다.
ㅁ : 0
ㅓ : 4
ㄱ : 2
ㅇ : 9
ㅓ : 6
그렇다면 "먹어"는 04296이란 수로 표현할 수 있다. 이런 식의 대응을 괴델 수 대응이라고 생각하면 된다. 즉, "괴델 수 대응이란 임의의 단어, 문장, 정보 등을 하나의 수로 일대일 대응시키는 방법을 말한다."[1]
이때, 어떤 튜링 기계가 n개의 부호를 가지고 명령어를 작성한다고 해보자. 그렇다면 이것은 n진법으로 수를 표현해버리면 그만이다. 그렇기 때문에 명령어를 기록하는 부호가 몇 개이든지 상관 없이 명령을 수로 표현할 수 있다.
다른 튜링 머신을 따라하기 - 현대 컴퓨터(Stored-program Computer)
위처럼 어떤 튜링 머신의 명령을 수로 표현할 수 있다면, 그 튜링 머신을 구성하는 모든 명령들을 수로 구성할 수 있다. 그렇게 된다면, 튜링 머신 그 자체를 수로 표현했다고 볼 수 있다. 그런데 아까 뭐라고 했던가? 튜링 머신의 입력 데이터도 수이다. 그래서 수로서 A라는 튜링 머신을 B라는 튜링 머신에 입력할 수 있다. 그렇게 된다면, B라는 튜링 머신은 A라는 튜링 머신의 명령어를 읽고 A라는 튜링 머신을 따라할 수 있게 된다. 이것을 확장하여 생각한다면, "현대 컴퓨터는 보편 튜링 기계의 이념을 구현한 ‘프로그램 내장형 컴퓨터’(Stored-program Computer)인 것이다."[2]
인공지능
튜링은 튜링 머신을 인간을 본따서 만들었다고 하였다. 그런데 인간은 생각을 할 수 있는 동물이다. 이런 맥락에서 기계 또한 지능을 가질 수 있는지에 대한 질문이 나온다. 튜링은 가능하다고 보았다.
튜링 완전성(turing completeness)
튜링 완전(turing completeness)이란 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 의미이다. 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다.
제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다.
(위키백과,"튜링 완전")
고찰
내가 튜링 머신에 관심 갖게 된 이유는 어느 책에서 읽었던 질문 때문이다. 그 책에선 왜 컴퓨터가 범용성을 갖는지 물어보았다. 그래서 나는 컴퓨터의 기원을 좇았다. 그렇게 해서 튜링 머신을 다시 만났다. 결국에 결론은 인간을 본따 만든 것이 튜링 머신이며, 튜링 머신은 컴퓨터의 근본 설계도이다. 그렇다면 컴퓨터의 범용성은 인간의 범용성에 의존한다고 볼 수 있다. 그래서 결론은 인간이 범용적이기 때문에 컴퓨터도 범용적이라고 할 수 있는 것이다. 그렇다면 "인간이 왜 범용적인가?"라고 물을 수 있다. 그러나 이 질문은 지금은 해결할 수 없는 아주 어려운 질문이라고 할 수 있다.
참고 문서
[1] : 박정일 (2012). [앨런 튜링 탄생 100주년] 앨런 튜링과 현대 컴퓨터의 기원. 지식의 지평(13),236
[2] : 박정일 (2012). [앨런 튜링 탄생 100주년] 앨런 튜링과 현대 컴퓨터의 기원. 지식의 지평(13),239
[3] : 이광근, 컴퓨터과학이 여는 세계(인사이트,2015), 2.1 보편만능 기계의 탄생
[4] : https://ko.wikipedia.org/wiki/%ED%8A%9C%EB%A7%81_%EC%99%84%EC%A0%84
[5] : https://www.scienceall.com/%ED%98%84%EB%8C%80-%EC%BB%B4%ED%93%A8%ED%84%B0%EC%9D%98-%EB%AA%A8%EB%8D%B8-%ED%8A%9C%EB%A7%81%EA%B8%B0%EA%B3%84turing-machine%EC%9D%98-%EA%B3%A0%EC%95%88/
