잇창명 개발 블로그

흥미 위주로 알아보는 μ-재귀 함수

• 수정 • 댓글 달기 TIL 계산이론 인터랙티브

ー모르는 단어다.

이번에는 갑자기 뜬금없는 주제에 안착했네요. 어쩌다가 이렇게 됐냐면...

이 글에서는 바로 위의 "또" 중 하나를 다룹니다. 참고로 위의 위키백과 글에서 언급한 튜링 완전한 계산 모형은 다음과 같습니다.

원래는 제가 잘 알고 있는 주제 위주로 블로그 글로 적었는데, 첫 문단에서 눈치채셨겠지만 제가 접한 지 얼마 안 되는 분야로 글을 쓰고 있기 때문에 주제에 대한 이해도가 비교적 낮을 수 있습니다. 재미있어 보이고 자주 다뤄지는 주제가 아닌 것 같아서 글로 남기고 있으니 틀린 곳을 발견하셨다면 댓글로 알려주세요.

원시 재귀 함수

μ-재귀 함수를 처음부터 전부 이해하려고 하면 체할 수 있으니 이것보다 더 작은 개념인 원시 재귀 함수부터 차근차근 살펴봅시다. 여기서 "재귀 함수"라는 단어는 프로그래밍에서의 재귀 함수와 다른 개념인 점에 유의해 주세요.

이 계산 모형에는 세 종류의 수학적 대상만이 존재합니다.

위에서 잠깐 살펴본 람다 대수와는 달리 함수의 인자로는 함수가 아니라 정수만 들어갈 수 있습니다. 여기서는 그 대신 기존의 함수끼리 연산하여 더 복잡한 함수를 만들어냅니다.

다음 방법으로 만든 함수만을 원시 재귀 함수라고 합니다. 별 말이 없으면 대문자는 함수, 소문자는 정수를 나타냅니다.

기본 함수 하나하나는 어렵지 않은데 연산자는 조금 헷갈리네요.

합성 연산자

두 가지 연산자 중 비교적 쉬운 것은 합성 연산자입니다. 학교에서 배운 \((H \circ G)(x) = H(G(x))\)를 기억하고 계실 텐데, 느닷없이 \(H\)를 \(m\)변수로, \(G\)를 \(k\)변수로 만들면 합성 연산자를 얻습니다. 단, \(H\)에 매개변수를 \(m\)개 전달해줘야 하니 \(H\)의 매개변수 자리에 들어가 있는 \(G\)도 함수 하나가 아닌 \(m\)개가 되어야 합니다.

기본 함수와 합성 연산자를 이용해 간단한 함수를 만들 수 있습니다.

솔직히 이런 함수만 만들어서 누구 코에 붙이나 싶네요.

원시 재귀 연산자

이 블로그가 개발 블로그인 걸 생각하면 설명을 냅다 코드로 해도 괜찮지 않을까 싶습니다. 원시 재귀 연산자를 의사코드로 표현하면 다음과 같습니다.

def rho(G, H)(y, ...args):
	result = G(...args)
	for i in [0, y):
		result = H(i, result, ...args)
	return result

\(G\)는 일종의 "베이스 케이스"고, 한 번 반복할 때마다 \(H\)에 반복 횟수, 이전 반복의 결과, 나머지 매개변수를 인자로 넘겨서 다음 결과를 계산합니다. 엄밀성 다 던져놓고 더 대충 설명하자면 \(\rho(G, H)(x) = H^x \circ G\)인 편입니다.

덧셈 함수 만들기

이쯤에서 다음 수 함수의 존재를 기억해봅시다. 함수를 주어진 인자만큼 재귀시킬 수 있고 그 함수 자리에 다음 수 함수를 넣는다면... 덧셈 함수를 만들 수 있습니다!

\[Add(x, y) = S^x(y)\]

그런데 원시 재귀 연산자를 사용하려면 함수 2개가 필요합니다. \(H\) 자리의 얼개는 잡아 두었고 \(G\)는 항등함수를 쓰면 될 것 같습니다.

\[Add(x, y) = (S^x \circ P^1_1)(y)\]

...그런데 \(G\)가 일변수이니 \(H\)는 3변수여야 합니다. 위의 합성 연산자 예시에서 확인했듯이 함수를 적당히 변형할 수 있습니다. 당장 필요한 건 지금까지 반복한 결과(즉, 2번째 인자)이므로...

\[H(i, z, y) = S(z) = (S \circ P^3_2)(i, z, y)\]

종합하면 덧셈 함수는 다음과 같이 정의할 수 있습니다.

\[Add = \rho(P^1_1, S \circ P^3_2)\]

뭐가 덕지덕지 많이 붙었네요. 여기서 핵심은 \(\rho\)로 첫 인자만큼 재귀시키고 \(S\)로 다음 수를 구한다는 점입니다. 실제로 덧셈을 수행하는지 아무 정수를 넣어서 확인해 보겠습니다.

\[\begin{align} Add(2, 7) &= \rho(P^1_1, S \circ P^3_2)(2, 7) \\ &= (S \circ P^3_2)(1, \rho(P^1_1, S \circ P^3_2)(1, 7), 7) \\ &= S(P^3_2(1, \rho(P^1_1, S \circ P^3_2)(1, 7), 7)) \\ &= S(\rho(P^1_1, S \circ P^3_2)(1, 7)) \\ &= S((S \circ P^3_2)(0, \rho(P^1_1, S \circ P^3_2)(0, 7), 7)) \\ &= S(S(P^3_2((0, \rho(P^1_1, S \circ P^3_2)(0, 7), 7)))) \\ &= S(S(\rho(P^1_1, S \circ P^3_2)(0, 7))) \\ &= S(S(P^1_1(7))) \\ &= S(S(7)) \\ &= S(8) \\ &= 9 \end{align}\]

계산 과정은 복잡하지만 원하는 값이 나왔네요! 이외에도 함수를 차근차근 조합해서 다음과 같은 것들을 만들 수 있습니다. 수식은 영문 위키백과에서 가져왔습니다.

함숫값으로 정수 하나만 가질 수 있다면 그렇지 않은 수학적 대상은 어떻게 표현할까 싶은데, 괴델 수 같은 걸 써서 나타낼 수 있다고 합니다. 예를 들어 피보나치 수열은 괴델 베타 함수 같은 걸로 두 수를 하나로 묶는 함수와 그걸 풀어내는 함수를 만들고 나서 \(\rho\)를 적당히 써서 만들 수 있습니다. 무섭네요.

한계점

세 가지 기본 함수와 두 가지 연산자로 생각보다 많은 것을 만들 수 있었지만, 원시 재귀 함수에는 H(3, H(2, H(1, H(0, G())))) 같은 제한된 형태의 재귀 이외에 무제한 재귀가 불가능하다는 한계가 있습니다. 동일한 함수로 재귀를 시키려면 \(\circ\) 연산자로 수동으로 함수를 중첩하거나, \(\rho\) 연산자로 인자의 값만큼만 재귀할 수밖에 없습니다. 식의 길이가 유한하고 유한 번밖에 재귀할 수 없으니 모든 식을 유한 단계 안에 계산할 수 있습니다.

일반적인 튜링 기계가 특정한 입력을 받았을 때 결국 멈출지 아닐지 판정하는 알고리즘은 존재하지 않음이 알려져 있습니다(정지 문제로 유명합니다). 람다 대수 등 다른 계산 모형에서는 "표현식이 주어졌을 때 (유한 단계 안에) 값을 구할 수 있는지 판정하는 알고리즘"으로 바꿔서 생각할 수 있습니다. 원시 재귀 함수는 항상 값을 구할 수 있기 때문에 튜링 완전하지는 않겠네요.

실제로 전역적 재귀 함수인데2 원시 재귀 함수가 아닌 것 중 유명한 예시가 아커만 함수이고, 여러 버전이 있는데 가장 자주 쓰이는 정의는 이렇습니다.

슥 보고 그대로 C 코드로 옮길 수 있을 것처럼 생겼죠? 이런 함수들도 재귀 함수의 맥락에서 계산할 수 있도록 연산자를 하나 더 정의해 봅시다.

μ-재귀 함수

오래 기다리셨습니다! 이제 진짜로 μ-재귀 함수가 뭔지 알아볼 차례입니다.

원시 재귀 함수의 정의에 아래 연산자만 하나 더 추가한 것을 μ-재귀 함수라고 합니다.

이 함수도 냅다 코드로 옮겨 보겠습니다.

def mu(G)(...args):
	for i in [0, ∞):
		if G(i, ...args) == 0:
			return i

이번에는 정말 원하는 만큼 재귀를 돌릴 수 있겠네요! 이렇게 최소화 연산자를 추가한 μ-재귀 함수는 튜링 완전함이 알려져 있습니다.

그런데 정의를 보고 "\(G\)에서 절대로 0이 안 나온다면 어떻게 될지"가 신경쓰이는 분들이 계실 것 같습니다. 결론부터 말씀드리자면, 이런 경우에는 함숫값이 없습니다!!! 🥳🥳🥳

네, 진짜로 함숫값이 없습니다. 일반적으로 \(G\)에서 0이 안 나올지 확인하는 방법은 직접 대입해보는 방법밖에는 없기 때문에 0부터 무한대까지 다 대입해봐야 하고, μ-재귀 함수에는 이렇게 생기는 무한루프를 감지하거나 빠져나올 메커니즘이 없습니다. \(\mu\) 연산자를 도입했더니 정지 문제도 같이 따라왔네요.

이런 식으로 함숫값이 없는("정의되지 않는다"고도 합니다) 경우가 있는 함수를 "부분 함수"(partial function)라고 합니다. 가장 간단한 예를 들자면 \(\mu(C^1_1)() = \mathrm{undefined}\)가 있고 이외에도 여러 가지 상황에서 함숫값이 정의되지 않을 수 있습니다.

위키백과에서 \(\mu\) 연산자를 사용한 예시로는 정수 제곱근(실수 제곱근에서 소숫점 아래를 버린 것)이 있습니다. 원시 재귀 함수가 아닌 예시는 아쉽게도 없네요.

\[Isqrt = \mu(Not \circ Gt \circ (Mul \circ (S \circ P^2_1, S \circ P^2_1), P^2_2))\]

제가 스스로 예시를 만들어보고 싶은데(특히 아커만 함수) 제가 \(\mu\) 연산자를 어떻게 다뤄야 할지를 몰라서 못 해보고 있습니다. 그대신 위키백과에서 본 신기한 정리를 인용해야겠네요. 솔직히 이러면 위키백과 번역글이 되는 것 같긴 한데...

클레이니 표준형 정리

1 이상의 모든 정수 \(k\)에 대해 다음을 만족시키는 일변수 원시 재귀 함수 \(U_k(y)\)와 \((k + 2)\)변수 원시 재귀 함수 \(T_k(y, e, x_1, \cdots, x_k)\)가 존재한다고 합니다.

...저도 읽으면서 헷갈렸으니 너무 걱정하지는 말아주세요. 이 정리의 의의는 모든 μ-재귀 함수는 \(\mu\)를 한 번만 써서 표현할 수 있다는 것입니다.

여기서 위의 함수 \(T_k(x, e, x_1, \cdots, x_k)\)를 클레이니 T 명제라고 하는데, 괴델 수 \(e\)로 표현되는 튜링 기계3의 초기 상태가 \((x_1, \cdots, x_k)\)일 때, 그 튜링 기계가 괴델 수 \(x\)로 표현되는 과정을 거쳐 정지하는지 판정하는 함수라는 것 같습니다. \(U_k(x)\)는 과정 \(x\)에서 최종 값만 뽑아내는 함수입니다. 저는 "원시 재귀 함수로는 튜링 기계를 통째로 시뮬레이션하는 건 곤란하지만 단계가 맞는지 검산하는 것은 가능하다는 접근이구나"로 이해했습니다. 계산 이론에서 중요한 역할을 하는 정리인 것 같은데 이제서야 처음 들은 느낌이라서 찜찜하네요.

직접 써 보자!

흥미 위주로 쓰기 시작한 글을 위키백과 번역글로 놔두기는 아까우니 아래에 μ-재귀 함수 인터프리터를 만들어 두겠습니다. 문법은 다음과 같습니다.

프로그램은 0개 이상의 함수 매크로 정의, 1개의 본문 함수, 0개 이상의 인자로 이루어집니다.

파서는 Peggy를 이용해 생성했습니다. 오류 메시지가 영어로 나오거나 일부 상황에서 알아보기 어려운 메시지가 나오는 점 양해 부탁드립니다.

그런데 글을 이렇게 끝내기 굉장히 찜찜하네요. 뭐 더 쓸 만한 거 없나? 개인 의견 쓰기는 부담스러운데

  1. 보통 3종류의 콤비네이터 \(S\), \(K\), \(I\)를 사용하지만, \(I\)는 \(S\)와 \(K\)로 나타낼 수 있습니다. 이외에 \(B\), \(C\), \(Y\) 등을 추가로 도입하는 경우도 있습니다. ↩

  2. 모든 인자의 조합에 대해 함숫값을 가지는 함수를 "전역적"(total)이라고 합니다. 그렇지 않은 함수는 "부분 함수"(partial function)라고 하며, 이 글의 더 밑에서 살펴보겠습니다. ↩

  3. 모든 μ-재귀 함수는 대응하는 튜링 기계가 있고, 그 역도 성립한다고 합니다. ↩

흥미 위주로 알아보는 μ-재귀 함수