계산 가능 함수

계산 가능 함수(計算 可能 函數, Computable function)는 계산 가능성 이론의 주요 연구 대상이다. 비형식적으로는 함수가 모든 인수의 값에 대해 함수의 값을 계산하는 알고리즘이 있다면 계산 가능하다고 한다. 알고리즘 개념의 정확한 정의가 부족하기 때문에 계산 가능성에 대한 모든 형식적인 정의는 특정 계산 모델을 참조해야 한다.

많은 계산 모델이 제안되었는데 주요 모델로는 튜링 기계, 레지스터 머신, 람다 대수 및 일반 재귀 함수가 있다. 이 네 가지 모델은 본질적으로 매우 다르지만, 정확히 동일한 계산 가능 함수의 분류를 제시하며 지금까지 제안된 모든 계산 모델에 대해 해당 모델의 계산 가능 함수는 위 네 가지 계산 모델에서 계산 가능하다.

처치-튜링 논제는 상상할 수 있는 모든 계산 가능성 개념이 위에서 언급한 의미에서 계산 가능한 함수만을 계산할 수 있다는 증명할 수 없는 주장이다.

계산 가능 함수의 정확한 정의 이전에, 수학자는 종종 비형식적인 용어인 "효율적으로 계산 가능한"(effectively calculable)을 사용했다. 이 용어는 이후 계산 가능 함수와 동일하게 여겨지게 되었다. 이러한 함수의 효율적인 계산 가능성은 말 그대로 "효율적으로" 계산될 수 있음을 의미하지 않는다(즉, 합리적인 시간 내에 계산될 수 있음을 의미하지 않는다). 사실 일부 효율적으로 계산 가능한 함수에 대해서는 이를 계산하는 모든 알고리즘이 알고리즘의 실행 시간이 입력 길이에 따라 기하급수적으로 (심지어 초기하급수적으로) 증가한다는 점에서 매우 비효율적일 수 있음을 보여줄 수 있다. 실현 가능한 계산 가능성 및 계산 복잡도 이론 분야는 효율적으로 계산될 수 있는 함수를 연구한다.

블룸 공리는 계산 가능 함수 집합에 대한 추상적인 계산 복잡도 이론을 정의하는 데 사용될 수 있다. 계산 복잡도 이론에서 함수의 값을 계산하는 문제는 결과가 "예" 또는 "아니요"인 결정 문제와 달리 함수 문제로 알려져 있다.

정의

 전체 튜링 기계 문서를 참고하십시오.

함수의 계산 가능성은 비형식적인 개념이다. 이를 설명하는 한 가지 방법은 함수의 값이 유효한 절차를 통해 얻을 수 있다면 그 함수는 계산 가능하다고 말하는 것이다. 더 엄밀하게 말하면, 함수 ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$는 자연수의 튜플 ${\displaystyle \mathbf {x} }$를 주어졌을 때 값 ${\displaystyle f(\mathbf {x} )}$를 생성하는 유효한 절차가 있을 때만 계산 가능하다.^[1] 이 정의에 따라 이 문서의 나머지 부분에서는 계산 가능 함수가 유한 개의 자연수를 인수로 취하고 단일한 자연수인 값을 생성한다고 가정한다.

이 비형식적인 설명에 상응하는 여러 공식적인 수학적 정의가 존재한다. 계산 가능 함수의 분류는 다음을 포함한 여러 동등한 계산 모델에서 정의할 수 있다.

• 튜링 기계
• 일반 재귀 함수
• 람다 대수
• 포스트 기계 (포스트-튜링 기계 및 태그 시스템)
• 레지스터 머신

이러한 모델은 함수, 입력 및 출력에 대해 서로 다른 표현을 사용하지만 어떤 두 모델 사이에도 변환이 존재하며, 따라서 모든 모델은 본질적으로 동일한 함수 분류를 설명한다. 이는 형식적 계산 가능성이 자연스럽고 너무 좁지 않다는 견해를 낳는다.^[2] 이러한 함수ㄴ,ㄴ 비형식적인 용어인 "계산 가능"과 대조하여 "재귀적"이라고 불리기도 하는데,^[3] 이는 1934년 클레이니와 괴델 간의 논의에서 비롯된 구분이다.^[4]p.6

예를 들어, 계산 가능 함수를 μ-재귀 함수로 형식화할 수 있는데, 이는 유한 튜플의 자연수를 취하고 단일 자연수를 반환하는 부분 정의 함수이다(위와 동일하게). 이는 상수, 계승, 사영 함수를 포함하고 함수의 합성, 원시 재귀 함수 및 μ 연산자에 대해 닫힌 부분 함수의 가장 작은 클래스이다.

동등하게, 계산 가능 함수는 튜링 기계나 레지스터 머신과 같은 이상화된 계산 에이전트에 의해 계산될 수 있는 함수로 형식화될 수 있다. 형식적으로 말하면, 부분 정의 함수 ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$는 다음과 같은 속성을 가진 컴퓨터 프로그램이 있을 때만 계산할 수 있다.

1. ${\displaystyle f(\mathbf {x} )}$가 정의되어 있다면, 프로그램은 입력 ${\displaystyle \mathbf {x} }$에 대해 컴퓨터 메모리에 ${\displaystyle f(\mathbf {x} )}$ 값이 저장된 채 종료된다.
2. ${\displaystyle f(\mathbf {x} )}$가 정의되어 있지 않다면, 프로그램은 입력 ${\displaystyle \mathbf {x} }$에 대해 절대로 종료되지 않는다.

계산 가능 함수의 특징

 이 부분의 본문은 알고리즘입니다.

계산 가능 함수의 기본 특징은 함수를 계산하는 방법을 알려주는 유한 절차(알고리즘)가 있어야 한다는 것이다. 위에 나열된 계산 모델은 절차가 무엇이고 어떻게 사용되는지에 대해 서로 다른 해석을 제공하지만 이러한 해석은 많은 속성을 공유한다. 이러한 모델이 동등한 계산 가능 함수 분류를 제공한다는 사실은 각 모델이 다른 모델의 절차를 읽고 모방할 수 있다는 사실에서 비롯된다. 이는 컴파일러가 한 컴퓨터 언어의 명령을 읽고 다른 언어로 명령을 내보낼 수 있는 것과 매우 유사하다.

엔더턴 [1977]은 계산 가능 함수를 계산하기 위한 절차의 다음과 같은 특징을 제시한다. 유사한 특징은 튜링 [1936], 로저스 [1967] 등이 제시했다.

• "절차에 대한 정확한 지시(즉, 프로그램)는 유한한 길이를 가져야 한다." 따라서 모든 계산 가능 함수는 함수가 어떻게 계산될지 완전히 설명하는 유한한 프로그램을 가져야 한다. 단순히 지시를 따르는 것만으로 함수를 계산할 수 있다. 추측이나 특별한 통찰력은 필요하지 않다.
• "절차가 f의 정의역에 있는 k-튜플 x를 받으면, 유한한 수의 이산적인 단계 후에 절차는 종료되어 f(x)를 생성해야 한다." 직관적으로 절차는 단계별로 진행되며, 계산의 각 단계에서 무엇을 해야 할지에 대한 특정한 규칙이 있다. 함수의 값이 반환되기 전에 유한한 수의 단계만 수행될 수 있다.
• "절차가 f의 정의역에 없는 k-튜플 x를 받으면, 절차는 영원히 계속되거나, 어느 시점에서 막힐 수 있다(즉, 지시 중 하나가 실행될 수 없다). 그러나 f(x)에 대한 값을 생성하는 척해서는 안 된다." 따라서 f(x)에 대한 값이 발견되면, 그것은 올바른 값이어야 한다. 계산 에이전트가 올바른 결과와 잘못된 결과를 구별할 필요는 없다. 절차는 결과를 생성할 때만 올바른 것으로 정의되기 때문이다.

엔더턴은 계산 가능 함수를 위한 절차의 3가지 요구사항에 대한 몇 가지 추가 설명을 열거한다.

1. 이 절차는 이론적으로 임의로 큰 인수에 대해서도 작동해야 한다. 예를 들어, 인수가 지구의 원자 수보다 작다고 가정하지 않는다.
2. 이 절차는 출력을 생성하기 위해 유한한 단계 후에는 멈춰야 하지만, 멈추기 전까지 임의로 많은 단계를 거칠 수 있다. 시간 제한은 가정되지 않는다.
3. 이 절차는 성공적인 계산 중에 유한한 양의 저장 공간만 사용할 수 있지만, 사용되는 공간의 양에는 제한이 없다. 절차가 추가 저장 공간을 요청할 때마다 해당 절차에 추가 저장 공간을 제공할 수 있다고 가정한다.

요약하자면, 이 관점에 따르면 함수는 다음 경우에 계산 가능하다.

1. 인풋에서 입력을 받았을 때, 제한 없는 저장 공간에 의존할 수 있지만 유한한 수의 정확하고 모호하지 않은 지침으로 구성된 절차(프로그램, 알고리즘)를 따라 해당 출력을 제공할 수 있다.
2. 유한한 단계 내에 해당 출력을 반환한다(중지한다).
3. 인풋에 없는 입력을 받으면, 결코 중지하지 않거나 멈춘다.

계산 복잡도 이론 분야는 성공적인 계산에 허용되는 시간 및 공간에 미리 정해진 제약이 있는 함수를 연구한다.

계산 가능한 집합 및 관계

자연수의 집합 A는 계산 가능(동의어: 재귀적, 결정 가능)이라고 불린다. 이는 모든 자연수 n에 대해, n이 A에 속하면 f(n) = 1이고 n이 A에 속하지 않으면 f(n) = 0인 계산 가능하고 전체적인 함수 f가 존재할 때이다.

자연수의 집합은 계산 가능하게 열거 가능(동의어: 재귀 열거 가능, 준결정 가능)이라고 불린다. 이는 각 숫자 n에 대해, n이 집합에 속하는 필요충분조건으로 f(n)이 정의되는 계산 가능 함수 f가 존재할 때이다. 따라서 집합은 어떤 계산 가능 함수의 정의역인 경우에만 계산 가능하게 열거 가능하다. "열거 가능"이라는 용어는 자연수의 비어 있지 않은 부분집합 B에 대해 다음이 동등하기 때문에 사용된다.

• B는 계산 가능 함수의 정의역이다.
• B는 전체 계산 가능 함수의 치역이다. 만약 B가 무한하다면, 함수는 단사 함수로 가정할 수 있다.

만약 집합 B가 함수 f의 치역이라면, 함수는 B의 열거로 볼 수 있다. 왜냐하면 목록 f(0), f(1), ...은 B의 모든 원소를 포함할 것이기 때문이다.

자연수에 대한 각 유한 관계는 해당 유한 자연수열 집합과 식별될 수 있으므로, 계산 가능 관계 및 계산 가능하게 열거 가능 관계의 개념은 집합에 대한 유사한 개념으로부터 정의될 수 있다.

형식 언어

 이 부분의 본문은 형식 언어입니다.

컴퓨터 과학의 계산 가능성 이론에서는 형식 언어를 고려하는 것이 일반적이다. 알파벳은 임의의 집합이다. 알파벳에 대한 단어는 알파벳에서 가져온 기호들의 유한한 시퀀스이다. 단어에는 동일한 기호가 여러 번 사용될 수 있다. 예를 들어, 이진 문자열은 알파벳 Σ = {0, 1}에 대한 정확한 단어이다. 언어는 고정된 알파벳에 대한 모든 단어들의 집합의 부분집합이다. 예를 들어, 정확히 3개의 1을 포함하는 모든 이진 문자열의 집합은 이진 알파벳에 대한 언어이다.

형식 언어의 핵심 속성은 주어진 단어가 언어에 속하는지 여부를 결정하는 데 필요한 난이도이다. 계산 가능 함수가 언어의 임의의 단어를 입력으로 취할 수 있도록 하는 어떠한 코딩 체계가 개발되어야 하는데, 이는 일반적으로 일상적인 것으로 간주된다. 언어는 계산 가능(동의어: 재귀적, 결정 가능)이라고 불린다. 이는 알파벳에 대한 각 단어 w에 대해, 단어가 언어에 속하면 f(w) = 1이고 단어가 언어에 속하지 않으면 f(w) = 0인 계산 가능 함수 f가 존재할 때이다. 따라서 언어는 임의의 단어가 언어에 속하는지 여부를 올바르게 판단할 수 있는 절차가 있을 때만 계산 가능하다.

언어는 계산 가능하게 열거 가능(동의어: 재귀 열거 가능, 준결정 가능)이라고 불린다. 이는 단어 w가 언어에 속하는 경우에만 f(w)가 정의되는 계산 가능 함수 f가 존재할 때이다. "열거 가능"이라는 용어는 자연수의 계산 가능하게 열거 가능한 집합과 동일한 어원을 가진다.

예시

다음 함수는 계산 가능하다.

• 정의역이 유한한 모든 함수. 예를 들어, 자연수의 모든 유한한 순열.
• 모든 상수 함수 f : N^k → N, f(n₁,...n_k) := n.
• 덧셈 함수 f : N² → N, f(n₁,n₂) := n₁ + n₂
• 두 수의 최대 공약수
• 두 수의 베주 계수
• 어떤 수의 가장 작은 소인수

f와 g가 계산 가능하면 다음도 계산 가능하다. 예를 들어 f + g, f * g, f가 단항연산이면 ${\displaystyle \color {Blue}f\circ g}$, max(f,g), min(f,g), 아그 맥스y ≤ f(x)} 및 더 많은 조합이 있다.

다음 예시는 함수가 계산 가능하더라도 어떤 알고리즘이 그것을 계산하는지 알려져 있지 않을 수 있음을 보여준다.

• π의 십진 확장 안에 n개의 연속된 5가 있으면 f(n) = 1이고, 그렇지 않으면 f(n) = 0인 함수 f는 계산 가능하다. (함수 f는 계산 가능한 상수 1 함수이거나, 또는 n < k일 때 f(n) = 1이고 n ≥ k일 때 f(n) = 0인 k가 존재한다. 이러한 모든 함수는 계산 가능하다. π의 십진 확장 안에 임의로 긴 5의 연속열이 있는지 알려져 있지 않으므로, 이 함수들 중 어떤 것이 f인지 알 수 없다. 그럼에도 불구하고, 함수 f는 계산 가능해야 한다는 것을 알고 있다.)
• 계산 불가능한 자연수열(예: 바쁜 비버 함수 Σ)의 각 유한 구간은 계산 가능하다. 예를 들어 각 자연수 n에 대해, 유한한 순열 Σ(0), Σ(1), Σ(2), ..., Σ(n)을 계산하는 알고리즘이 존재한다. 이는 전체 Σ-순열, 즉 모든 n에 대한 Σ(n)을 계산하는 알고리즘이 없다는 사실과 대조된다. 따라서, "0, 1, 4, 6, 13을 출력"하는 것은 Σ(0), Σ(1), Σ(2), Σ(3), Σ(4)를 계산하는 사소한 알고리즘이다. 유사하게, 주어진 n 값에 대해, 그러한 사소한 알고리즘이 존재한다(비록 그것이 결코 알려지거나 누구에게도 생성되지 않을지라도) Σ(0), Σ(1), Σ(2), ..., Σ(n)을 계산하기 위해.

처치-튜링 논제

 이 부분의 본문은 처치-튜링 논제입니다.

처치-튜링 논제는 위에서 나열된 세 가지 속성을 가진 절차로부터 계산 가능한 모든 함수가 계산 가능 함수라고 주장한다. 이 세 가지 속성이 공식적으로 명시되지 않았기 때문에, 처치-튜링 논제는 증명될 수 없다. 다음 사실들은 종종 이 논제의 증거로 간주된다.

• 많은 동등한 계산 모델이 알려져 있으며, 이들은 모두 계산 가능 함수의 동일한 정의(또는 어떤 경우에는 더 약한 버전)를 제공한다.
• 일반적으로 효율적으로 계산 가능하다고 여겨지는 더 강력한 계산 모델은 제안된 적이 없다.

처치-튜링 논제는 때때로 특정 함수가 계산 가능함을 입증하기 위해 계산 절차에 대한 구체적인 설명을 제공하는 증명에서 사용된다. 이는 논제의 이러한 모든 사용이 어떤 계산 모델에서 함수에 대한 형식적인 절차를 작성하는 지루한 과정을 통해 제거될 수 있다고 믿어지기 때문에 허용된다.

증명 가능성

함수 (또는 유사하게 집합)가 계산 가능한지 여부뿐만 아니라 특정 증명 시스템(일반적으로 1차 페아노 산술)에서 이를 증명할 수 있는지 여부에 관심이 있을 수 있다. 계산 가능성이 증명될 수 있는 함수를 증명 가능 전체 함수라고 한다.

증명 가능 전체 함수의 집합은 재귀 열거 가능하다. 이는 그들의 계산 가능성을 증명하는 모든 해당 증명을 열거함으로써 모든 증명 가능 전체 함수를 열거할 수 있다. 이는 증명 시스템의 모든 증명을 열거하고 관련 없는 증명을 무시함으로써 수행할 수 있다.

재귀적으로 정의된 함수와의 관계

재귀적 정의로 정의된 함수에서 각 값은 동일한 함수 또는 다른 함수의 이전에 정의된 값(단순히 상수일 수 있음)의 고정된 1차 공식으로 정의된다. 이들의 부분집합이 원시 재귀 함수이다. 또 다른 예로는 재귀적으로 정의되었지만 원시 재귀적이지 않은 아커만 함수가 있다.^[5]

이러한 유형의 정의가 순환성이나 무한 회귀를 피하려면, 정의 내에서 동일한 함수에 대한 재귀적 호출이 함수의 정의역에 있는 어떤 잘 정렬된 부분 순서에 대해 더 작은 인수에 대한 것이어야 한다. 예를 들어, 아커만 함수 ${\displaystyle A}$의 정의에서 ${\displaystyle A(x,y)}$가 ${\displaystyle A(p,q)}$를 참조할 때마다 ${\displaystyle (p,q)<(x,y)}$는 자연수 쌍의 사전식 순서와 관련된다. 이 경우와 원시 재귀 함수의 경우, 잘 정렬은 명확하지만, 일부 "참조-대상" 관계는 잘 정렬됨을 증명하기가 쉽지 않다. 잘 정렬된 방식으로 재귀적으로 정의된 모든 함수는 계산 가능하다. 각 값은 함수에 대한 재귀적 호출 트리를 확장하여 계산할 수 있으며, 이 확장은 유한한 수의 호출 후에 종료되어야 한다. 그렇지 않으면 쾨니그 보조정리는 무한히 감소하는 호출 시퀀스로 이어져 잘 정렬됨의 가정을 위반하기 때문이다.

증명 가능 전체 함수가 아닌 전체 함수

건전한 증명 시스템에서 모든 증명 가능 전체 함수는 실제로 전체 함수이지만, 그 역은 참이 아니다. 충분히 강력하고 건전한 모든 1차 증명 체계(페아노 산술 포함)에서는 (다른 증명 체계에서) 증명 시스템에서 전체 함수임을 증명할 수 없는 전체 함수의 존재를 증명할 수 있다.

전체 계산 가능 함수가 이를 생성하는 튜링 기계를 통해 열거된다면, 위에서 언급된 증명 가능 전체 함수의 열거를 사용하여 위에서 사용된 것과 유사한 대각화 논증에 의해 (증명 시스템이 건전하다면) 위 진술이 증명될 수 있다. 관련 증명을 열거하는 튜링 기계를 사용하고, 모든 입력 n에 대해 f_n(n)을 호출한다(여기서 f_n은 이 열거에 의한 n번째 함수이다). 이는 n번째 증명에 따라 해당 함수를 계산하는 튜링 기계를 호출함으로써 이루어진다. 이러한 튜링 기계는 증명 시스템이 건전하다면 중단이 보장된다.

계산 불가능한 함수와 풀 수 없는 문제

 이 부분의 본문은 비결정 문제 목록입니다.

모든 계산 가능 함수는 그것을 계산하는 방법에 대한 명확하고 모호하지 않은 지침을 제공하는 유한한 절차를 가지고 있다. 더욱이, 이 절차는 계산 모델이 사용하는 유한한 알파벳으로 인코딩되어야 하므로, 계산 가능 함수는 가산 개수만 존재한다. 예를 들어, 함수는 비트 문자열(알파벳 Σ = {0, 1})을 사용하여 인코딩될 수 있다.

실수는 비가산 집합이므로 대부분의 실수는 계산 가능하지 않다. 계산 가능한 수를 참조하라. 자연수에 대한 유한 함수의 집합은 비가산 집합이므로 대부분은 계산 가능하지 않다. 이러한 함수의 구체적인 예로는 바쁜 비버, 콜모고로프 복잡도 또는 차이틴 상수와 같은 계산 불가능한 숫자의 자릿수를 출력하는 모든 함수가 있다.

마찬가지로, 자연수의 대부분의 부분집합은 계산 가능하지 않다. 정지 문제는 그렇게 구성된 첫 번째 집합이다. 다비트 힐베르트가 제안한 결정 문제는 어떤 수학적 진술(자연수로 코딩됨)이 참인지를 결정하는 유효한 절차가 있는지 물었다. 튜링과 처치는 1930년대에 독립적으로 이 자연수 집합이 계산 가능하지 않음을 보였다. 처치-튜링 논제에 따르면, 이러한 계산을 수행할 수 있는 유효한 절차(알고리즘을 가진)는 존재하지 않는다.

계산 가능성의 확장

상대적 계산 가능성

함수의 계산 가능성 개념은 임의의 자연수 집합 A에 대해 상대화될 수 있다. 함수 f는 A에 대한 오라클에 대한 접근을 허용하는 수정 사항과 함께 계산 가능 함수의 정의를 만족할 때 A에 대해 계산 가능(동등하게 A-계산 가능 또는 A에 상대적으로 계산 가능)으로 정의된다. 계산 가능 함수의 개념과 마찬가지로, 상대적 계산 가능성은 여러 다른 계산 모델에서 동등한 정의로 주어질 수 있다. 이는 일반적으로 주어진 정수가 A의 구성원인지 묻는 추가 기본 연산을 사용하여 계산 모델을 보완함으로써 이루어진다. 또한 g를 그 그래프와 동일시함으로써 f가 'g에 대해 계산 가능'하다고 말할 수도 있다.

고층 재귀 이론

초산술적 계층 이론은 공집합의 튜링 점프를 가산 순서수 번 반복하여 계산할 수 있는 집합들을 연구한다. 이는 2차 산술 언어의 보편적 및 존재적 공식 모두에 의해 정의된 집합과 일부 하이퍼 계산 모델과 동등하다. 훨씬 더 일반적인 재귀 이론들이 연구되어 왔는데, 예를 들어 어떤 집합이든 E-재귀 함수의 인수로 사용될 수 있는 E-재귀 이론이 있다.

하이퍼 계산

처치-튜링 논제는 계산 가능한 함수에 모든 알고리즘을 가진 함수가 포함된다고 명시하고 있지만, 알고리즘이 가져야 할 요구 사항을 완화하는 더 넓은 함수를 고려하는 것이 가능하다. 하이퍼 계산 분야는 일반적인 튜링 계산을 넘어서는 계산 모델을 연구한다.

같이 보기

• 계산 가능한 수
• 유효 방법
• 계산 이론
• 재귀 이론
• 튜링 차수
• 산술적 위계
• 하이퍼 계산
• 초재귀 알고리즘
• 반계산 가능 함수