0. 컴퓨터란 무엇인가?
현대 컴퓨터의 수학적 구조 제안의 시초는 앨런 튜링의 튜링 기계이다. 최초의 컴퓨터로 알려진 콜로서스보다 앞서 제시된 개념이다.
튜링 기계의 개략적인 아이디어는, "무한히 긴 테이프 위에 일렬로 칸이 나누어 져 있고, 각 칸에는 어떤 기호가 기록되어 있다. 헤드라고 하는 각 칸을 지시하는 지시자가 있어 칸을 옮겨 다니면서 정해진 명령에 따라 각 칸에 기록되어 있는 칸을 변경한다."의 간단한 구조를 제시한다. 이때, 헤드는 한 번에 한 칸만 이동할 수 있다.
그럼, 수학적으로 튜링 기계를 모델링해보자. 무한히 긴 테이프 위에 칸이 나누어 져 있다는 것은, 수직선에 대응할 수 있을 것이다. 헤드의 이동 조건인 한 차례에 한 칸만 이동할 수 있다는 점에서, 적어도 각 칸은 countable한 개수를 가져야 함을 알 수 있고, 헤드의 각 칸은 자연수에 대응시킬 수 있을 것 같다.
헤드는 그 각 칸 중 하나를 가리키므로 어떤 변수 H라 두고, 그 값이 각 칸 중 하나인 동적인 변수로 생각하는 것은 적당해 보인다.
여기까지 요약하면, 어떤 자연수와 bijection인 문자열 S와, 그 문자의 위치를 담고 있는 변수 h를 순서쌍으로 엮은 (S,h)를 튜링 기계라고 하는 것은 "일단은" 큰 문제는 없어보인다.
그리고, 상당히 공학적으로 의미있는 아이디어를 곁들이면 조금 더 간단한 구성을 얻을 수 있다.
"튜링 기계는 종료되어야 한다."
무한히 작동하기만 하는 튜링 기계는 공학적으로 큰 의미를 갖기 힘들어보인다. 예컨대 응답하는 데 걸리는 시간이 무한대인 서버는 클라이언트에게 어떤 의미이겠는가!
이때, 종료되는 시간 동안 헤드가 움직인 칸 수를 j라 한다면, j보다 큰 변위만큼 헤드는 테이프를 벗어날 수 없다. 즉, 공학적으로는 "어떤 명령을 모두 수행하는 데 필요한 테이프 길이 이상의 테이프 길이를 가진다면 그 테이프는 무한대의 테이프를 가진 것과 다름없"고, 수학적으로는 "종료되는 시간까지 도달할 수 없는 테이프에 기록된 문자는, 그 문자가 어떤 문자이던 간에 튜링 기계의 작동에 영향을 끼치지 않는다"고 할 수 있다. 즉, 이런 칸에 기록된 문자는 임의의 우리가 원하는 문자로 생각해도 관계 없다.
한편, 문자의 종류 개수도 종료되어야 하는 튜링 기계에게는 무한할 필요가 없는데, 튜링 기계가 작동한 명령 개수 i에 대해 i보다 많은 문자의 개수는 필요하지 않다. 여기서 한 가지 아이디어를 더 이용해서, 각 문자를 자연수라고 생각할 수 있다. 그러면 그 자연수의 나열은 하나의 자연수를 이룰 것이다. 왜냐하면 종료되어야 하는 튜링 기계는 무한하지 않은 길이의 테이프로도 공학적으로 충분하기 때문이다. 심지어 자연수의 자릿수를 일치시키고 빈 자릿수를 0으로 채우면, k자리의 자연수를 각 기호에 매핑했다면 테이프를 가리키는 자연수를 k자리마다 끊는 것으로 원래의 튜링 기계와 완전히 동치임을 쉽게 보일 수 있다.
조금 더 나아가면, 2진 자연수로도 충분히 이를 실행할 수 있다는 것을 보일 수 있고, 테이프에 필요한 문자의 종류는 0과 1의 두 가지로 충분하다.
위의 종료가능한 튜링 기계의 무한한 테이프 위 도달불가능한 칸을 모두 0으로 채우면 유한의 어떤 자연수로 테이프의 상태를 표현할 수 있다.
테이프는 어떤 적당한 자연수에 대응시킬 수 있었으므로, 테이프의 상태를 나타내는 자연수 T와 헤드의 위치를 담고 있는 변수 H를 순서쌍으로 묶을 수 있고, 순서쌍 (T,H)를 메모리라고 한다. 그리고, 실제 컴퓨터에서, 공학적으로, 그리고 이 글 이후로 하술할 내용에서, 테이프의 각 칸은 슬롯, 헤드는 포인터라는 이름을 갖고 있다. 이를 이용해 튜링 기계를 천천히 정의해보자.
1. 기계와 쿼리
기계란, 메모리와 메모리를 작동시키는 쿼리의 조합을 의미한다. 쿼리란, 기계가 할 수 있는 일을 의미하고, 메모리에 기록된 문자가 바뀌거나, 헤드의 위치가 바뀔 수 있다.
쿼리가 작동한다는 것은 쿼리가 의미하는 기계가 할 수 있는 일을 하는 것을 의미한다. 아래의 예를 통해 살펴보자.
다음 8개의 쿼리를 수행할 수 있는 튜링 기계를 생각하자. 이 튜링 기계의 테이프 위의 각 칸은 8비트 부호없는 정수이다.
> : 헤드를 1칸 이동시킨다. (오버플로우 포함)
< : 헤드를 -1칸 이동시킨다. (언더플로우 포함)
+ : 헤드가 위치한 칸의 값을 1만큼 변화시킨다. (오버플로우 포함)
- : 헤드가 위치한 칸의 값을 -1만큼 변화시킨다. (언더플로우 포함)
. : 헤드가 위치한 칸의 값을 출력한다.
, : 헤드가 위치한 칸에 입력된 값을 할당한다.
[ : 헤드가 가리키는 값이 0이면 짝이 되는 ] 쿼리를 실행한다.
] : 헤드가 가리키는 값이 0이 아니면 짝이 되는 [ 쿼리를 실행한다.
출력, 입력, 쿼리의 나열 등은 후술하겠으나, 일단 공학적으로 받아들이고 시작하자. 이 튜링 기계는 BrainFuck이라는 기계이다. 메모리는 1바이트 슬롯 32768개로 이루어져 있다.
BrainFuck의 동작을 통해 기계를 이해해보자. 8칸의 메모리만을 사용하는 쿼리를 다루자.
이 기계의 상태는 9개의 요소를 가지는 순서쌍으로 이해할 것이다. 앞의 8개의 자연수는 각 슬롯에 기록된 정수, 마지막 자연수는 헤드의 위치이다. 슬롯에 기록된 정수의 이진 표현을 연속해서 쓴 하나의 정수로 이해할 수도 있지만, 그리고 그런 방식을 통해 적절한 순서쌍으로 메모리의 상태를 나타냈지만, 각 슬롯에 기록된 내용을 이해하기 위해 각 슬롯을 분리해서 작성한다.
초기 상태는 (0,0,0,0,0,0,0,0,0)이고, 각 슬롯의 번호는 0에서 7까지의 정수라고 하자.
쿼리 1. >>
(0,0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0,1), (0,0,0,0,0,0,0,0,2) 순서대로 메모리의 상태가 변한다.
쿼리 2. <<
(0,0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0,7), (0,0,0,0,0,0,0,0,6) 순서대로 메모리의 상태가 변한다.
쿼리 3. +>+>>+
(0,0,0,0,0,0,0,0,0), (1,0,0,0,0,0,0,0,0), (1,0,0,0,0,0,0,0,1), (1,1,0,0,0,0,0,0,1), (1,1,0,0,0,0,0,0,2), (1,1,0,0,0,0,0,0,3), (1,1,0,1,0,0,0,0,3) 순서대로 메모리의 상태가 변한다.
쿼리 4. ++.-.-.
(0,0,0,0,0,0,0,0,0), (1,0,0,0,0,0,0,0,0), (2,0,0,0,0,0,0,0,0)로 변하고 2를 출력한다.
(1,0,0,0,0,0,0,0,0)로 변하고 1을 출력한다.
(0,0,0,0,0,0,0,0,0)로 변하고 0을 출력한다.
쿼리 5. ,.
(0,0,0,0,0,0,0,0,0)에서 입력받는다. (입력값이 7이라 가정하자.)
(7,0,0,0,0,0,0,0,0)로 변하고 7을 출력한다.
쿼리 6. ++[>+<-]
(0,0,0,0,0,0,0,0,0), (1,0,0,0,0,0,0,0,0), (2,0,0,0,0,0,0,0,0),로 변한 뒤 [ 쿼리는 슬롯 0의 값이 0이 아니므로 (2이므로) 지나간다.
(2,0,0,0,0,0,0,0,1), (2,1,0,0,0,0,0,0,1), (2,1,0,0,0,0,0,0,0), (1,1,0,0,0,0,0,0,0)로 변한 뒤 ] 쿼리는 슬롯의 값이 0이 아니므로 짝이 되는 [ 쿼리로 돌아간다.
(1,1,0,0,0,0,0,0,1), (1,2,0,0,0,0,0,0,1), (1,2,0,0,0,0,0,0,0), (0,2,0,0,0,0,0,0,0)로 변한 뒤 ] 쿼리는 슬롯의 값이 0이 아니지 않으므로 (0이므로) 지나간다.
쿼리 4와 쿼리 5에서 본 것 처럼 기계는 입력받을 수 있고, 출력할 수 있다. 이때 입력 버퍼와 출력 버퍼라는 개념을 도입하자. 버퍼란, 입력값 또는 출력값 등을 입력받기 이전에 저장해 두는 메모리이다. 튜링 기계를 생각할 때 가장 먼저 생각한 메모리와 동일한 메모리와 포인터를 생각하자. 입력 버퍼는 다음과 같은 쿼리만을 수행한다.
"입력 버퍼의 포인터가 가리키는 값을 메인 메모리에 전달하고 포인터를 +1만큼 변화시킨다."
출력 버퍼는 다음과 같은 쿼리만을 수행한다
"출력 버퍼의 포인터가 가리키는 슬롯을 메인 메모리로부터 전달받은 값으로 변화시키고 포인터를 +1만큼 변화시킨다."
한편, 쿼리 6에서 본 것 처럼, 쿼리는 한 번 수행하고 소멸되는 정보가 아니다. 입력 버퍼나 출력 버퍼는 메인 메모리의 입장에서 쿼리를 수행하고 나면 그 내용이 무엇이었든 관계없지만, 쿼리 자체는 기억하고 있을 필요가 있다. 실제 구조나 구현은 메모리 구조를 배우게 되면 알 수 있지만, 여기서는 쿼리 버퍼를 마련하는 것으로 생각하자.
즉, BrainFuck 기계를 동작하는 데는 네 개의 메모리와 네 개의 헤더가 필요하다. 그러나, 수학자들에 의해 여러 개의 메모리를 가지는 튜링 기계와 하나의 메모리를 가지는 튜링 기계는 튜링 동치임이 증명되어 있다. 즉, 입출력과 쿼리 버퍼는 원래 메모리가 튜링 기계라면 원래 메모리와 하나의 메모리인 것으로 생각해도, 별개의 메모리인 것으로 생각해도, 심지어 추상적이라고 생각해도 문제없다.
2. 쿼리와 시간
앞서 살펴본 여러 쿼리를 묶어 하나의 수행 단위로 만들어 놓은 것을 프로그램이라고 한다.
앞서 살펴본 프로그램들은 순서가 있었다. 당연히 ++>+.와 +>++.은 다른 BrainFuck 프로그램이다. 순서대로 쿼리가 실행될 때 어떤 중간 과정에서의 메모리 상태가 다르기 때문이다. 두 BrainFuck 프로그램을 살펴보자.
+>+>+<<과 >>+<+<+는 모두 시작 메모리 상태와 끝 메모리 상태, 쿼리의 종류와 개수가 같다. 그러나 두 프로그램은 서로 다르고, 이를 구분할 필요가 있다. 프로그램은 단순히 시작과 끝 메모리 상태(입출력 버퍼를 포함하여)를 매핑하는 함수로는 불충분하다. 즉, 중간 과정이 있어야 한다. 프로그램은 시작 메모리 상태가 주어지면 중간 모든 메모리 상태가 결정된다. (이를 결정적 튜링 기계라고 한다.) 즉, 프로그램은 시작 메모리 상태를 인자로 하여 중간 모든 메모리 상태를 결정하는 인자로 이해할 수 있다.
모든 메모리 상태의 나열은 순서가 있고, 이산적이고, 가산이다. 즉, 메모리 상태의 나열은 수열로 생각할 수 있는데, 수열은 자연수를 정의역으로 하는 함수로 이해할 수 있으므로, 적당한 자연수 t에 대해 어떤 프로그램에 대한 메모리 상태를 함수로 나타낼 수 있다.
초기 메모리 상태 M0, 프로그램 P가 주어졌을 때 t번째 메모리 상태를 나타내는 함수 M은 M(P, M0, t)로 쓸 수 있고, 이때 t를 프로그램의 시간이라고 한다.
예를 들어, 앞선 BrainFuck의 튜링 기계를 예로 들자. (4개의 1바이트 슬롯을 가진 메모리와 포인터를 순서쌍으로 표현한다.)
M(>>++>+>, (0,0,0,0,0), 3)은 (0,0,0,0,0)을 시작으로 >>++>+>의 쿼리열을 거치는 시간 3의 메모리 상태를 나타낸다.
M(>>++>+>, (0,0,0,0,0), 3) = M(>++>+>, (0,0,0,0,1), 2) = M(++>+>, (0,0,0,0,2), 1) = M(+>+>, (0,0,2,0,2), 0) = (0,0,2,0,2)와 같은 식으로 표현할 수 있다.
3. 기계의 상태
기계는 상태를 가진다. 모든 프로그램은 종료 쿼리로 끝나야 한다. 종료 쿼리는 생략되기도 하고, 종료 쿼리가 정의되지 않은 기계는 프로그램 끝을 종료 쿼리로 가져야 한다. 물론 종료 쿼리가 프로그램 중간에 있을 수 있지만, 그 쿼리를 수행하지 않고 이후 쿼리를 수행하도록 하는 다른 쿼리가 있지 않다면 그 이후에 나오는 쿼리는 실행되지 않는다.
기계의 상태는 실행상태와 종료상태가 있다. 현재 상태를 나타내는 함수 S에 대해, 프로그램 P, 초기 메모리 상태 M0, 시간 t가 주어질 때 S(P, M0, t)는 초기 메모리 상태 M0에 프로그램 P를 통과하는 시간 t의 상태를 의미한다. 실행상태인 경우를 [RUN]로, 종료 상태인 경우를 [END]로 표현하기로 하자. 편의상 프로그램의 첫 쿼리를 시작쿼리라고 하고, 종료 쿼리는 q로, 시작쿼리를 p로 표현하자. 이때 상태함수 S는 다음과 같이 정의된다.
ㄱ. S(qP, M0, 0)=[END]
ㄴ. S(pP, M0, 0)=[RUN]
ㄷ. if S(P, M0, 0)=[END] then S(P, M0, k)=[END] on {0<=k}
공학적으로 해석하면 종료 쿼리를 만나기 전까지는 [RUN]상태이다가 종료 쿼리를 만난 이후의 시간에는 [END]상태가 된다는 것이다.
어떤 기계가 종료가능하다는 것은 S(P, M0, t)=[END]인 t가 존재한다는 것을 의미한다.
4. goto 쿼리와 튜링 완전한 언어
튜링 기계는, 쿼리의 조합이 튜링 완전한 기계를 의미한다.
기계언어란, 메모리 위에서 작동하는 쿼리의 집합이다. 즉, 기계언어 L에 대해 L의 어떤 조합 C(L)도 메모리함수 M과 상태함수 S가 잘 정의되는 것을 의미한다.
goto 쿼리란, 쿼리 버퍼 포인터의 값을 조건에 따라 직접 변경하는 쿼리를 의미한다. 오해해서는 안되는 것은 goto 쿼리 또한 쿼리이고, 메인 메모리 위에서 작동하는 다른 쿼리와 등위이다. 쿼리 버퍼에서 작동하는 쿼리가 아니다. 쿼리 버퍼는 오직 메인 메모리가 작동할 쿼리를 전달하고 쿼리 포인터를 증가시키는 것 뿐이다. 쿼리 버퍼를 메인 메모리와 동일한 메모리에 사용하는 것으로 쿼리 버퍼 포인터의 위치를 기록하는 슬롯의 값을 변경시키는 쿼리라고 할 수 있다. goto 쿼리의 핵심은 조건에 따라 다음 쿼리가 달라진다는 것이다. goto 쿼리의 존재때문에 프로그램 자체를 함수로 정의하지 않고 메모리 함수 M, 상태함수 S 등을 정의해 함수처럼 보이도록 설정하는 것이다.
어떤 기계언어가 튜링 완전하다는 것은, goto쿼리를 포함하고, 메모리 상태 (T,H)를 (T', H')로 변경하는 프로그램 P를 메모리 상태에 관계 없이 조합할 수 있음을 의미한다. 즉, M(C(L), (T,H), t)=(T',H')인 조합 C, 시간 t가 존재하게 하는 기계 언어 L은 튜링 완전하다. 간접적으로 위 조건을 만족하는 경우도 포함한다. 튜링 완전한 언어와 튜링 동치인 기계 언어도 튜링 완전하다.
두 언어가 튜링 동치라는 것은, 한 언어가 다른 언어를 모방할 수 있을 때 튜링 동치라고 한다. 어떤 쿼리를 이 쿼리를 포함하지 않는 다른 쿼리들의 조합으로 표현할 수 있다면 이를 쿼리를 모방한다고 한다. 어떤 언어의 모든 쿼리를 모방할 수 있다면, 이를 언어를 모방한다고 한다.
느슨하게 튜링 완전한 언어는 사용할 수 있는 메모리가 유한한 경우를 의미한다. 느슨하게 튜링 완전한 경우는 포인터를 저장할 공간이 유한하거나 총 메모리가 유한한 경우 발생한다. 물리학적으로 구현가능한 컴퓨터는 완전히 튜링 완전하지 않은데, 메모리가 무한하지 않기 때문이다.
BrainFuck은 느슨하게 튜링 완전한 언어이다. 즉, BrainFuck과 튜링 동치인 기계 언어는 모두 튜링 완전하다.
흔히들 HTML은 프로그래밍 언어가 아니라고 하는데, 그 이유가 튜링 완전하지 않기 때문이다.
튜링 완전한 언어에는 람다 대수, 절차적 언어 등이 있다.
5. 마무리
상당히 분량이 길어졌는데, 중간에 대거 수정이 있어서 단어 설정 등이 어색할 수 있습니다. 지적 바랍니다.
쿼리라는 개념 자체가 함수와는 어느 정도 다른 느낌도 있고, 명확하고 정확하게 수학적으로 정의하기도 힘들어 보이고, 정의한 것을 본 적도 없고 해서 다소 엄밀하지 않은 정의가 상당수 있습니다. 또, 중고등학교, 공대, 자연대 등에서 흔히 다루는 수학과 상당히 이질적인 수학을 다루게 되서 수학적이지 못하다고 느끼는 사람이 상당수 있을 것으로 생각됩니다. 하지만 이런 수학이 공학적이라기보다 수학적이어야 한다고 생각하기 때문에 이렇게 작성해봅니다. 어색한 정의, 반례 등 지적 바랍니다.
