함수, 조건식, 재귀적 정의 등 수학적 함수와 관련된 기본 개념을 설명하는 글입니다. 조건식과 재귀적 함수 정의에 특별히 중점을 두고 있습니다.
우리는 일반적인 함수에 관한 여러 수학적 아이디어와 표기법이 필요하다. 대부분의 아이디어는 잘 알려져 있지만, 조건식이라는 개념은 새로운 것으로 보인다2. 조건식을 사용하면 함수를 새롭고 편리한 방식으로 재귀적으로 정의할 수 있게 된다.
부분 함수란 정의역의 일부분에서만 정의되는 함수이다. 함수가 계산에 의해 정의될 때, 어떤 인자 값들에 대해서는 계산이 끝나지 않을 수 있으므로 부분 함수가 자연스럽게 나타난다. 하지만, 몇몇 기본 함수들도 부분 함수로 정의될 것이다.
명제식이란 가능한 값이 참(T)과 거짓(F)인 식이다. 독자는 명제 논리적 결합자인 그리고(
), 또는(
), 아니면(
)에 익숙하다고 가정한다. 전형적인 명제식의 예는 다음과 같다:
프레디킷은 진리값 T와 F로 이루어진 함수의 범위를 갖는 함수이다.
진리값이 다른 종류의 값에 어떻게 의존하는지 수학에서는 프레디킷으로 표현한다. 진리값이 다른 진리값에 의존하는 것은 논리적 결합자로 표현된다. 그러나 다른 종류의 값이 진리값에 의존하는 의존성을 기호로 명확히 표현할 만한 표기법은 충분치 않으며, 보통 영어 단어와 구문이 사용된다. 예를 들어, 함수 |x|는 보통 말로 정의된다. 조건식은 명제값에 따라 값이 달라지는 양의존성을 표현하는 장치이다. 조건식의 형식은 다음과 같다:
여기서 p들은 명제식이고, e들은 어떤 종류의 식이든 될 수 있다. 이는 “만약 p₁이면 e₁, 그렇지 않고 p₂이면 e₂, ..., 그렇지 않고 pₙ이면 eₙ” 또는 “p₁이 e₁을, ..., pₙ이 eₙ을 내놓는다”로 읽을 수 있다.3
조건식 (p₁ → e₁, ..., pₙ → eₙ)의 값이 정의되는지의 규칙을 다음과 같이 둔다. p들을 왼쪽에서 오른쪽으로 살펴본다. 만약 T값(참)을 갖는 p가 undefined값을 갖는 p보다 먼저 등장하면, 그 조건식의 값은 그에 대응되는 e(값이 정의되어 있다면)가 된다. undefined인 p를 먼저 만나거나, 모든 p가 F(거짓)이거나, T인 p에 대응되는 e값이 undefined이면, 조건식의 값은 undefined이다.
예를 들면:
조건식의 가장 단순한 응용 중 하나는 다음과 같은 정의에 있다:
조건식을 이용하면, 순환참조 없이 정의될 함수식 안에 그 함수 자체를 등장시키는 방식으로 함수를 정의할 수 있다.
예를 들어:
이 식으로 0!을 계산하면 1이 되고, 의미 없는 0·(0-1)! 같은 식은 발생하지 않는다. 2!의 계산은 다음과 같이 진행된다:
2! = (2 = 0 → 1, T → 2 · (2 - 1)!) = 2 · (1 = 0 → 1, T → 1·(1-1)!) = 2 · 1 · (0 = 0 → 1, T → 0·(0-1)!) = 2 · 1 · 1 = 2
다른 재귀 함수 정의의 예로 최대공약수(유클리드 알고리즘)가 있다:
뉴턴 방식으로 근사 제곱근을 구하는 알고리즘은 다음과 같이 정의된다:
여러 함수의 동시 재귀적 정의도 가능하며, 필요하다면 이런 정의를 쓸 것이다.
재귀 정의에 따라 수행되는 계산이 반드시 끝나리라는 보장은 없다. 예를 들어 n!의 경우 n이 음수가 아닌 정수일 때에만 성공적으로 계산될 것이다. 계산이 끝나지 않으면, 그 인자에 대한 함수값은 정의되지 않은 것으로 본다.
명제 논리의 결합자들도 조건식으로 정의할 수 있다. 예를 들어:
오른쪽 식들의 진리표가 올바른지 쉽게 확인할 수 있다. 만약 p나 q가 undefined일 수 있음을 고려하면, ∧와 ∨는 교환법칙이 성립하지 않게 된다. 예를 들어, p가 F이고 q가 undefined라면, p ∧ q는 F이지만, q ∧ p는 undefined이다. 우리의 목적에서는 이 비가환성이 오히려 바람직하다. p ∧ q를 계산할 땐 먼저 p를 계산하고, p가 F이면 q는 계산하지 않는다. 만약 p 계산이 끝나지 않으면, q 계산은 아예 시도되지 않는다. 여기서부터는 이러한 의미로 명제 논리 결합자를 사용한다.
수학(수리논리학 외의)을 통틀어, "함수"라는 용어는 흔히 정확하게 사용되지 않으며, y² + x와 같은 형식(form)에도 적용된다. 우리는 나중에 함수식을 대상으로 계산을 하려 하므로, 함수와 형식을 구분하고, 그 구분을 명확히 해 줄 표기법이 필요하다. 이 구분과 표기법(약간의 변형 포함)은 Church[3]에 의해 제시되었다.
f를 정수 두 변수의 함수로 나타내는 표현이 있다고 하자. 이 경우 f(3, 4)와 같이 쓸 수 있어야 하고 값이 결정되어야 한다. 그러나 y² + x는 이 조건을 충족하지 못한다. y² + x(3, 4)는 표준 표기법이 아니며, 그 값을 13으로 볼지 19로 볼지 불확실하다. Church는 y² + x와 같은 표현을 “형식(form)”이라 부른다. 만약 형식의 변수들과 함수의 인자 순서를 대응시킬 수 있다면, 이를 함수로 변환할 수 있다. 이때 필요한 것이 Church의 λ-표기법이다.
E를 x₁,...,xₙ에 대한 형식이라 하자. 그렇다면 λ((x₁, ..., xₙ), E)는 n변수 함수가 되고, 인자를 x₁,...,xₙ 순서대로 E에 대입해서 식의 값을 산출한다. 예를 들어,
λ((x, y), y² + x)는 두 변수 함수이고, λ((x, y), y² + x)(3, 4) = 19이다.
λ-표기식의 변수는 적분의 변수처럼 가변(dummay) 혹은 바인딩(bound)되어 있다. 즉, 바운드 변수 이름을 일관되게 바꾸면 함수식의 값은 변경되지 않는다. 따라서 λ((x, y), y² + x), λ((u, v), v² + u), λ((y, x), x² + y)는 모두 같은 함수를 뜻한다.
λ로 바운드된 변수와 바인딩되지 않은(자유, free) 변수를 동시에 포함할 수도 있으며, 이는 파라미터(매개 변수)로써 함수를 정의하는 것으로 볼 수 있다.
형식과 함수를 구분해 표기하면, 함수의 인자를 함수 자체로 사용할 때에도 모호함이 없어진다. (예시는 생략하나, 후속 논의에서 함수의 인자로 함수를 사용하는 예를 다룬다.)
λ-표기식 등에서 바운드된 변수들이 동일한 기호로 충돌(collision)할 경우에는 조합자(combinator) 기반 표기가 사용된다. 하지만 이런 표기는 실용적 관점에서 읽기 어렵고 길어진다.
λ-표기법만으로 재귀적으로 정의되는 함수를 이름지을 수는 없다. 예를 들어, λ로 sqrt의 정의를 바꿔보면:
λ로 바꾸면:
그러나 오른쪽 식에서 sqrt의 참조가 무엇을 의미하는지 불분명해진다.
그래서 재귀함수의 식을 쓸 수 있도록, 표기법을 추가한다:
label(a, E)는 식 E를 의미하되, E 내에서 a가 참조될 때마다 E 전체를 가리킨다.
예를 들어:
label(sqrt, λ((a, x, ε), (|x² - a| < ε → x, T → sqrt(a, ½(x + a/x), ε))))
이 표기를 통해 sqrt함수를 명쾌하게 표현할 수 있다.
label(a, E)의 a도 바운드된 변수(λ의 변수와 다름)이므로, 체계적으로 이름을 바꿔도 의미가 변하지 않는다.
존 매카시(John McCarthy), 2006-08-13
