튜링 계산가능한 함수는 회귀 함수이다

(Turing computable functions are recursive) 

 

계산가능성과 논리 : George S. Boolos   Richard C. Jeffrey 저, 김영정.최훈.강진호 옮김, 문예출판사 (393-5681), 1996 (원서 : Computability and Logic, 3rd ed, Cambridge Univ. Press, 1989), page 112~119

 

우리는 모든 회귀 함수가 주판 계산가능하고 (R ⊆ A) 모든 주판 계산가능한 함수는 튜링 계산가능하다 (A ⊆ T) 는 것을 보았다. 우리는 이제 모든 튜링 계산가능한 함수가 회귀 함수라는 것 (T ⊆ R) 을 보여주겠다. 그러면 포함관계

의 원이 닫혀지고 세 가지 계산가능성 개념이 동치라는 증명이 완성된다. 즉,

    R = A = T

이다.

그러면 6 장의 조건 (1) - (5) 을 만족하는 튜링 기계 M 이 계산하는 함수가 f 라고 가정하자. 우리는 f 가 회귀 함수라는 것을 보여야만 한다. 구체적으로 f 가 이항 함수라고 가정하자. 몇 항 함수가 되더라도 지금 하려고 하는 것과 비슷하게 할 수 있다.

가 임의의 자연수라고 가정하자. 의 계산을 시작할 때 M 의 테이프는 한 개의 빈 사각형으로 나누어진 1 들의 일련체 두 개 말고는 완전히 비어 있다. 왼쪽 일련체에는 1 이 개 있다. 오른쪽 일련체에는 1 이 개 있다. 처음에 M 은 왼쪽 일련체의 가장 왼쪽에 있는 1 을 읽고 있다. 그 기계는 멈출 때 개의 1 들을 가진 일련체 말고는 완전히 비어 있는 테이프에서 가장 왼쪽에 있는 1 을 읽고 있다. 그리고 계산과정 내내, 읽고 있는 사각형의 왼쪽에는 1 이 유한히 많이 있고, 오른쪽에도 1 이 유한히 많이 있으며, 읽고 있는 사각형에는 1 이 많아야 한 개 있다.

그러므로 계산을 하는 동안 언제나, 읽고 있는 사각형의 왼쪽에 1 이 있다면 그 사각형 왼쪽으로 가장 왼쪽에 있는 1 이 있고, 오른쪽의 경우에도 마찬가지로 말할 수 있다. 따라서 다음과 같이 이진법을 써서 자연수의 순서쌍을 통해 테이프 내용과 읽고 있는 사각형의 내용을 나타낼 수 있다.

읽고 있는 사각형의 왼쪽에 있는 테이프의 무한한 부분에는 이진법의 숫자 (이를테면 1011, 0, 1) 가 있고 군더더기인 0 들 (0 = B) 이 무한히 연속적으로 그 앞에 붙어 있다고 생각할 수 있다. 우리는 이 숫자를 왼쪽 숫자라고 부르고, 이진법으로 표기한 그 숫자가 가리키는 수는 왼쪽 수라고 부른다. 테이프의 나머지 부분은 읽고 있는 사각형과 그 사각형의 오른쪽 부분으로 이루어져 있는데, 거기에는 거꾸러 쓰여진 이진법 숫자가 있으며 마찬가지로 군더더기인 0 들이 연속적으로 붙어 있다고 생각할 수 있다. 우리는 테이프에 거꾸로 쓰여진 채로 나타난 이 숫자를 오른쪽 숫자라고 부르고, 그 숫자가 가리키는 수는 오른쪽 수라고 부른다. 따라서 읽고 있는 사각형에는 오른쪽 숫자의 '일의 자리' (one's place) 에 있는 0 이나 1 이 표시되어 있다. 우리는 테이프에서 생기는 변화가 언제나 두 숫자의 일의 자리 부근에서 생긴다는 것을 보장하기 위해 오른쪽 숫자가 거꾸로 쓰여졌다고 생각한다.

(보기 1)

이런 모양의 테이프가 있다 :

그러면 왼쪽 숫자는 11101 이고, 오른쪽 숫자는 10111 이고, 왼쪽 수는 29 이고, 오른쪽 수는 23 이다.

우리는 '0' 과 '1' 을 숫자의 이름으로도 또 숫자가 가리키는 수의 이름으로도 쓸 것이며, 그 때 발생하는 애매함은 문맥에 의존하여 해소하도록 할 것이다.

(보기 2)

테이프가 완전히 비어 있다. 그러면 왼쪽 숫자 = 오른쪽 숫자 = 0 이고 왼쪽 수 = 오른쪽 수 = 0 이다.

읽고 있는 사각형의 기호가 0 에서 1 로 [1 에서 0 으로] 바뀌면 오른쪽 수는 1 만큼 늘어나고 [줄어들고] 왼쪽 수는 변하지 않는다. M 이 왼쪽이나 오른쪽으로 사각형 하나 만큼 움직일 때 수에는 무슨 일이 일어날까?

l[r] 을 움직이기 전에 옛 왼쪽 [오른쪽] 수라고 하고, l'[r'] 은 새 왼쪽 [오른쪽] 수라고 하자. 우리는 l, r 의 값과 움직이는 방향에 따라 l', r' 이 어떻게 변하는지에 대해서, 그리고 움직임의 방향에 대해서 알고 싶다. 네 가지 경우를 생각해 보아야 하는데, 모두 거의 비슷하므로 M 이 왼쪽으로 움직이고 l 이 홀수인 경우만 자세히 생각해 보자.

l 이 홀수이므로 옛 왼쪽 숫자는 1 로 끝난다. r = 0 이면, 새 오른쪽 숫자는 1 이고 r' = 1 = 2r + 1 이다. 그리고 만약 r > 0 이면, 새 오른쪽 숫자는 옛 숫자의 일의 자리 끝에 1 을 덧붙여 만든다. 여기서도 r' = 2r + 1 이다. l' 의 경우에 만약 l = 1 이면, 옛 왼쪽 숫자는 단지 1 이고, 새 왼쪽 숫자는 0 이며, l' = 0 = (l - 1) / 2 이다. 그리고 l 이 1 보다 큰 임의의 홀수라면, 새 왼쪽 숫자는 옛 왼쪽 숫자의 일의 자리에 있는 1 을 지움으로써 (따라서 숫자를 줄임으로써) 만들 수 있다. 이 새 숫자는 (l - 1) / 2 를 가리키며, 역시 l' = (l - 1) / 2 이다. 요약해 보자. 만약 M 이 왼쪽으로 움직이고 l 이 홀수이면, l' = (l - 1) / 2 이고 r' = 2r + 1 이다.

(보기 1 의 계속)

M 이 왼쪽으로 움직인다고 가정하자. 그러면 새 왼쪽 숫자는 1110 이고 l' = 14 = (29 - 1) / 2 이며, 새 오른쪽 숫자는 101111 이고 r' = 47 = 2ㆍ23 + 1 이다.

비슷하게 논증을 해보면

    만약 M 이 왼쪽으로 움직이고 l 이 짝수이면, l' = l / 2 이고 r' = 2r 이다.
    만약 M 이 오른쪽으로 움직이고 r 이 홀수이면, l' = 2l + 1 이고 r' = (r - 1) / 2 이다.
    만약 M 이 오른쪽으로 움직이고 r 이 짝수이면, l' = 2l 이고 r' = r / 2 이다.

는 것을 알 수 있다.

M 이 계산을 시작할 때 왼쪽 수와 오른쪽 수는 얼마인가? 그 때 테이프는 읽고 있는 사각형 왼쪽으로는 완전히 비어 있고, 그래서 왼쪽 숫자는 0 이며 왼쪽 수는 0 이다. 오른쪽 숫자는 다음과 같다.

이진 표기법으로 된 m 개의 연속적인 1 은 을 가리킨다. 0 이 n 개만큼 뒤에 나오는 m 개의 연속적인 1 은 을 가리킨다. m 개의 1 다음에 0 이 하나 나오고 그 다음에 1 들이 p 개 따라 나오는 1 들의 일련체는 을 가리킨다. 그러므로 M 이 의 계산을 시작할 때 오른쪽 수는 (  1) + (  1) 이다. (  1) + (  1) 이라고 하자. 그러면 s 는 기초적 회귀 함수이다.

또한 M 이 멈출 때 왼쪽 수와 오른쪽 수는 얼마인가? M 은 멈출 때, + 1 개의 일련체를 제외하고는 빈 칸인 테이프에서 가장 왼쪽에 있는 1 을 읽고 있다. 왼쪽 수는 그대로 0 이고, 오른쪽 수는 인데, 이것은 이진 표기법으로 된 + 1 개의 연속적인 1 들이 가리키는 수이다.

lo(x) 는 인 가장 큰 라고 하자. 19 에 의해, lo 는 기초적 회귀 함수이다. (실제로 만약 이면 d(x, y) = 0 이고, 그렇지 않으면 1 이라고 한다면, lo(x) = Mxx[d](x) 이다.) 이다. 그러므로 이다. 따라서 M 이 t 에서 의 계산을 멈추고 또 t 에서 r 이 오른쪽 수이면, 라는 결론이 따라나온다.

우리는 이제 M 의 흐름 도식이나 기계 도표를 두 개의 기초적 회귀 함수 a 와 q 로 나타내는 일을 할 것이다. 우리는 기계의 상태 등을 자연수 1 등으로, 기호 B, 1 을 자연수 0, 1 로, 동작 B, 1, L, R 을 자연수 0, 1, 2, 3 으로 해석한다. 만약 M 이 상태 에서 0 을 읽으면서 동작 j(= 0, 1, 2, 3) 를 수행하고 상태 로 간다면, 우리는 a(i, 0) = j 과 q(i, 0) = k 라고 놓는다. 만약 M 이 상태 에서 1 을 읽으면서 동작 j 를 수행하고 상태 로 간다면, 우리는 a(i, 1) = j 과 q(i, 1) = k 라고 놓는다. 이 규정에 해당하지 않는 모든 자연수 x, y 의 순서쌍에 대해서 우리는 a(x, y) = y 와 q(x, y) = 0 이라고 놓는다. 그렇다면 멈춘다는 것은 가상의 상태 0 으로 가는 것이다. M 의 기계 도표에는 사중체들이 유한한 수만큼만 있으므로, a 와 q 가 경우별로 정의가능한, 기초적 회귀 함수라는 것은 분명하다.

(보기 3)

다음수 함수를 계산하는 기계의 도식인 그림 1 을 생각해 보자.

 

그림 1  함수 s 를 계산하기

    

    

f 가 회귀 함수라는 것을 보여주기 위해서, 우리는 자연수들의 순서 삼중체를 단 한 개의 자연수로 코드화하는 장치와, 삼중체를 코드화한 단 한 개의 삼중체의 첫번째, 두번째, 세번째 구성요소를 찾아낼 수 있는 장치가 필요하다. 이런 장치들이 필요한 까닭은 계산의 t + 1 단계에서 왼쪽 수가 얼마인가 하는 것이, t 에서 왼쪽 수가 얼마였는가라는 것 뿐만 아니라 t 에서 오른쪽 수가 얼마였는가라는 것과 t 에서 M 의 상태가 무엇이었는가에도 달려 있기 때문이다. 이 점은 t 에서 오른쪽 수와 M 의 상태의 경우에도 마찬가지이다. 그러나 우리가 일단 삼중체를 단 한 개의 수로 코드화하면, 우리는 t + 1 의 왼쪽 수, t + 1 의 상태, t + 1 의 오른쪽 수로 이루어진 삼중체 l', c', r' 이 t 의 왼쪽 수, t 의 상태, t 의 오른쪽 수로 이루어진 삼중체 l, c, r 에 (기초적 회귀적으로) 의존한다는 것을 보일 수 있을 것이다.

그러므로 우리는 tpl(x, y, z) = 라고 정의한다. tpl 은 기초적 회귀 함수이다. 만약 tpl(x, y, z) = tpl(a, b, c) 라면 x = a, y = b, z = c 이다. 우리는 앞으로 'tpl(x, y, z)' 대신에 '<x, y, z>' 라고 쓰겠다.

lft(w) 는 가 w 를 (나머지 없이) 나누는 가장 큰 x ≤ w 라고 하고, ctr(w) 는 이 w 를 나누는 가장 큰 x ≤ w 라고 하고, rgt(w) 는 이 w 를 나누는 가장 큰 x ≤ w 라고 하자. 7.19 에 의해서 lft, ctr, rgt 는 기초적 회귀 함수이다. 함수 lft, ctr, rgt 은 w = <x, y, z> 이면 lft(w) = x, ctr(w) = y, rgt(w) = z 라는 뜻에서 tpl 의 역이다.

우리는 이제 다음과 같은 성질을 가진 3 항의 기초적 회귀 함수 g 를 정의하겠다. 만약 t 가 M 이 를 계산할 때 멈추는 단계보다 더 나중의 단계가 아니라면, 에서 왼쪽 수, t 에서 M 의 상태, t 에서 오른쪽 수 > 이다. M 은 계산을 시작할 때 상태 1 에 있으므로,

    

라고 할 수 있다.

e(x) 는 만약 x 가 짝수이면 0 이고 홀수이면 1 이라고 하자. 함수 e 는 물론 기초적 회귀 함수이다. 수가 짝수인 경우 그리고 오직 그 경우에만 이진 표기법으로 된 일의 자리에 0 이 있다. 그러므로 r 이 t 에서 오른쪽 수인 경우, 만약 t 에서 읽은 사각형의 기호가 0(=B) 이면 e(r) = 0 이고, 이 기호가 1 이면 e(r) = 1 이다.

우리는 이제 g 의 정의를 완성할 수 있다. 앞으로 우리는 '', '', '' 를 줄여서 각각 'l', 'c', 'r' 이라고 쓰겠다. 우리는 또 'q(c, e(r))', 곧 ', ' 를 줄여서 'q' 라고 쓰겠다.

라고 하자. (우리는 / 를 기초적 회귀적으로 정의한 것이라고 생각한다. 즉, x/y 는 만약 몫이 되는 자연수가 있다면 x 를 y 로 나눈 몫이고, 그런 자연수가 없다면 (이를테면) 0 으로 정의한다.)

tpl, lft, ctr, rgt, s, q, e, a, , +, ㆍ, / 가 모두 기초적 회귀 함수이므로, g 도 역시 기초적 회귀 함수이다.

g 의 정의에서 두번째 구절은 이렇게 해석할 수 있다. 즉, 만약 M 이 1 을 읽으면서 상태 c 에 있고 그 기계 도표는 읽고 있는 사각형에 0 을 쓰라고 말하고 있다면, 왼쪽 수는 여전히 똑같고, M 의 다음 상태는 그 도표가 기술한 대로이고, 오른쪽 수는 1 만큼 줄어든다. 다른 구절들도 비슷하게 해석할 수 있다.

우리의 정의는 만약 t 가 M 이 멈추는 단계라면 M 은 t + 1 에서 처음으로 상태 0 으로 간다는 것을 보장해 준다. 그러므로 모든 y ≤ t 에 대해서 이다. 그리고 l, c, r 이 각각 t 에서 왼쪽 수, t 에서 M 의 상태, t 에서 오른쪽 수라면, a(c, e(r)) = e(r) (= 0, 1) 이고 q(c, e(r)) = 0 이며, 따라서 이고 이다. 그러므로 M 이 를 계산할 때 t 에서 멈출 경우 그리고 오직 그 경우에만 t 는 인 가장 작은 y 이다. 이라고 하자. h 는 기초적 회귀 함수이고, M 이 를 계산할 때 t 에서 멈출 경우 그리고 오직 그 경우에만 이다. Mn[h] 는 회귀함수이다. (그것이 기초적 회귀 함수라고 결론짓는 것은 일반적으로 불가능하다.) 그리고 M 이 t 에서 멈추고 r 이 t 에서 오른쪽 수라면, 이다. 그러므로 모든 , 에 대해서

    

이다. 따라서 f 는 회귀 함수이다. 이로써 포함관계의 원은 닫혀졌다.

그런데 우리는 다음을 또한 증명한 셈이다.

(회귀 함수에 대한 클리니 표준 형식 (Kleene normal form) 정리)

기본 함수에서 합성, 기초적 회귀, 최소화를 통해 회귀 함수를 얻을 때, 최소화 연산은 한 번 이상 쓸 필요가 없다.

우리가 '회귀적' 이라는 용어를 쓴 것은 어느 정도 비표준적이었다. 우리가 회귀 함수라고 불러 왔던 것은 보통 부분 회귀함수라고 부르는 것이고, 표준적으로 '회귀적' 이라고 부르는 함수들은 전체 함수인 부분 회귀 함수들, 다시 말해서 (적절한 n 에 대하여) 모든 자연수들의 n 중체에 산출값을 부여하는 함수들이다. 우리는 전체가 아닌 부분 회귀 함수는 더 이상 다루지 않을 것이므로, 앞으로 표준적 표현을 채택하겠다. 즉, 이제부터 회귀 함수는 언제나 전체 함수이다.

연습문제 (존 버지스 (John Burgess))

튜링기계 M 이 에 대한 표준적 위치에서 출발하여 y 에 대한 표준적 위치에서 멈출 꼭 그 경우에 모든 에 대하여 이 정의되며 그 값이 y 와 같을 경우 그리고 오직 그 경우에만 M 이 넓은 의미에서 n 항 함수 f 를 계산한다고 하자. (모든 기계는, 심지어 어떤 투입값들에 대해서는 비표준적 위치에서 멈추는 기계조차도, 넓은 의미에서 n 항 함수를 계산한다.) 어떤 기계가 어떤 함수를 넓은 의미에서 계산할 경우 그리고 오직 그 경우에만 그 함수는 부분 회귀 함수임을 보여라. [힌트 : M 은 왼쪽 수가 0 이고 오른쪽 수가 양수이면서 동시에 2 의 거듭제곱보다 작을 경우 그리고 오직 그 경우에만 ㅍ 표준적 위치에서 멈춘다.