계산 가능 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 계산 가능 함수의 특징
4. 예시
5. 처치-튜링 명제
6. 증명 가능성과 재귀적 정의
7. 계산 불가능 함수와 결정 불가능 문제
8. 계산 가능성 확장
- 8.1. 상대적 계산 가능성
- 8.2. 고차 재귀 이론과 하이퍼컴퓨팅
참조

1. 개요

계산 가능 함수는 유효한 절차를 통해 값을 얻을 수 있는 함수를 의미하며, 튜링 기계, μ-재귀 함수, 람다 대수 등 다양한 계산 모델로 정의될 수 있다. 이러한 모델들은 본질적으로 동일한 함수 클래스를 설명하며, 계산 가능 함수는 모든 입력에 대해 정의되는 전역 함수와 특정 입력에 대해서만 정의되는 부분 함수로 구분된다. 계산 가능 함수의 핵심 특징은 함수를 계산하는 방법을 알려주는 유한한 절차(알고리즘)가 존재한다는 것이며, 계산 불가능한 함수와 결정 불가능 문제도 존재한다. 처치-튜링 명제는 알고리즘적으로 계산 가능한 모든 함수가 튜링 머신으로 계산 가능하다는 주장을 담고 있으며, 계산 가능성 개념은 상대적 계산 가능성, 고차 재귀 이론, 하이퍼컴퓨팅 등으로 확장될 수 있다.

더 읽어볼만한 페이지

계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

계산 가능 함수
개요
정의	어떤 자연수를 입력받아 다른 자연수를 출력하는 함수 f에 대해, f를 계산하는 알고리즘 (즉, 컴퓨터 프로그램)이 존재하면 f는 계산 가능한 함수라고 한다.
특징	계산 가능 함수는 튜링 기계와 같은 계산 모델에서 계산될 수 있는 함수이다. 모든 함수가 계산 가능한 것은 아니다. 계산 불가능한 함수의 예로는 정지 문제를 푸는 함수가 있다.
형식적 정의
부분 함수	만약 함수가 모든 입력에 대해 정의될 필요가 없다면, 우리는 부분 계산 가능 함수에 대해 이야기한다.
계산 가능 함수	어떤 계산 가능 함수가 모든 입력 값에 대해 정의된다면, 우리는 그것을 전체 계산 가능 함수라고 부른다.
동치 명제	계산 가능 함수를 정의하는 방법은 많으며, 그들은 모두 동치인 명제를 생성한다. 함수 f: Nk → N은 계산 가능하다고 말할 수 있는 것은 다음 중 하나가 참인 경우이다.
튜링 기계	튜링 기계와 같은 계산 모델에 의해 계산 가능하다.
μ-재귀 함수	μ-재귀 함수이다. 즉, 상수 함수, 사상 함수, 후속 함수에서 시작하여 합성, 원시 재귀 및 최소화의 유한한 횟수를 사용하여 얻을 수 있다.
형식 체계	일부 형식 체계(예: 람다 대수)에서 해당 함수의 그래프를 나타내는 공식이 존재한다.
프로그래밍 언어	프로그래밍 언어(예: C 언어)에서 컴퓨터 프로그램에 의해 계산 가능하다.
예시
예시	모든 다항식 함수는 계산 가능하다. 지수 함수는 계산 가능하다. 함수의 근을 찾는 것은 일반적으로 계산 불가능하다.
계산 가능 수
정의	실수는 튜링 기계에 의해 근사될 수 있다면 계산 가능하다고 말한다.
예시	파이는 계산 가능한 수이다. 오일러 상수는 계산 가능한 수이다. 모든 대수적 수는 계산 가능하다.
활용
활용	계산 가능 함수는 계산 복잡도 이론, 알고리즘 정보 이론, 증명 이론과 같은 분야에서 중요한 역할을 한다.

2. 정의

'''계산 가능성'''은 어떤 문제를 알고리즘적으로 해결할 수 있는지, 즉 유한한 단계 안에 답을 구할 수 있는지를 다루는 계산 가능성 이론의 핵심 개념이다. 이 개념은 주로 집합이나 함수의 성질을 설명하는 데 사용된다.

어떤 집합이 '''계산 가능'''하다는 것은 그 집합의 원소인지 아닌지를 유효한 절차를 통해 항상 결정할 수 있다는 의미이다. 즉, 집합 $A$ 에 대해, 어떤 값 $n$ 이 $A$ 에 속하면 1을, 속하지 않으면 0을 반환하는 계산 가능한 함수 $f$ 가 존재한다. 이러한 집합을 '''재귀적 집합'''(recursive set) 또는 '''결정 가능한 집합'''(decidable set)이라고도 부른다.

한편, 어떤 집합의 원소인 경우에만 유한한 시간 안에 그렇다는 것을 확인할 수 있는 경우(즉, 원소가 아닐 때는 확인 절차가 끝나지 않을 수도 있음), 그 집합을 '''계산 가능하게 열거 가능한 집합'''(computably enumerable set) 또는 '''귀납적으로 셀 수 있는 집합'''(recursively enumerable set), '''준결정 가능 집합'''(semidecidable set)이라고 한다. 이는 어떤 값이 집합에 속하는 것과 특정 부분 계산 가능 함수의 값이 정의되는 것이 동치인 경우이다.

함수의 경우, 입력값이 주어졌을 때 그 결과값을 유한한 단계 안에 계산할 수 있는 유효 절차가 존재하면 '''계산 가능한 함수'''라고 한다.^[1] 계산 가능 함수는 입력값에 따라 결과값이 정의되지 않을 수도 있는 '''부분 계산 가능 함수'''(Partial computable function)와 모든 입력값에 대해 결과값이 정의되는 '''전역 계산 가능 함수'''(Total computable function)로 나뉜다.

"계산 가능", "재귀적", "결정 가능"과 같은 용어들은 문맥에 따라 유사한 개념을 나타내는 데 사용되며,^[3] 이는 클레이니(Kleene)와 괴델(Gödel)의 논의에서 비롯된 구분이다.^[4]^p.6 계산 가능성 이론에서는 튜링 기계, μ-재귀 함수, 람다 대수 등 다양한 계산 모델을 통해 이러한 개념들을 수학적으로 엄밀하게 정의하며, 이 모델들은 본질적으로 동일한 계산 능력(동일한 함수 클래스)을 가진다는 것이 밝혀졌다.^[2]

2. 1. 계산 가능한 함수

함수의 계산 가능성은 비공식적으로 어떤 함수 값을 구하는 유효 절차가 존재할 때 그 함수가 계산 가능하다고 설명할 수 있다. 더 정확히 말하면, 함수

f:\mathbb N^k\rightarrow\mathbb N

는 어떤 자연수 튜플

\mathbf x

가 주어졌을 때

f(\mathbf x)

값을 계산하는 유효한 절차가 존재할 경우에만 계산 가능하다.^[1] 이 정의에 따라, 계산 가능한 함수는 유한한 개수의 자연수를 입력받아 하나의 자연수 값을 결과로 내놓는다고 가정한다.

이러한 비공식적 개념에 대응하는 여러 공식적인 수학적 정의가 있으며, 계산 가능한 함수의 종류는 다음과 같은 서로 동등한 계산 모델들을 통해 정의될 수 있다.

튜링 기계
μ-재귀 함수
람다 대수
포스트 기계 (포스트-튜링 기계 및 태그 기계)
레지스터 기계
콤비네이터 논리

이 모델들은 함수의 표현, 입력, 출력을 다루는 방식은 다르지만, 모델 간 변환이 가능하기 때문에 본질적으로 동일한 종류의 함수들을 설명한다. 이는 공식적인 계산 가능성 개념이 자연스러우며 지나치게 한정적이지 않다는 근거가 된다.^[2] 이러한 함수들은 때때로 "계산 가능(computable)"이라는 비공식적 용어와 구분하기 위해 "재귀적(recursive)"이라고도 불리는데,^[3] 이는 1934년 클레이니(Kleene)와 괴델(Gödel)의 논의에서 비롯된 구분이다.^[4]^p.6

예를 들어, 계산 가능한 함수는 μ-재귀 함수로 정의될 수 있다. 이는 유한한 튜플의 자연수를 입력받아 단일 자연수를 반환하는 부분 함수이다. μ-재귀 함수는 상수 함수, 다음수 함수(successor function), 사영 함수(projection function)를 기본으로 포함하며, 합성, 원시 재귀, μ 연산자 연산에 대해 닫혀 있는 가장 작은 부분 함수 클래스이다.

비슷하게, 계산 가능한 함수는 튜링 기계나 레지스터 기계와 같은 이상적인 계산 장치로 계산될 수 있는 함수로도 정의할 수 있다. 공식적으로, 부분 함수

f:\mathbb N^k\rightarrow\mathbb N

는 다음 속성을 만족하는 컴퓨터 프로그램이 존재할 경우에만 계산 가능하다고 본다.

# 만약

f(\mathbf x)

가 정의된다면, 프로그램은 입력

\mathbf x

에 대해 실행되어 컴퓨터 메모리에 저장된 값

f(\mathbf x)

를 결과로 내고 종료한다.

# 만약

f(\mathbf x)

가 정의되지 않는다면, 프로그램은 입력

\mathbf x

에 대해 실행될 때 절대 종료하지 않는다.

계산 가능 함수는 기본적으로 자연수에 대한 부분 함수이다. 즉, 모든 가능한 입력 값에 대해 함수 값이 정의되지 않을 수도 있다. 계산 가능 함수

f

는 정해진 개수의 자연수를 인수로 받으며, 이 개수는 함수마다 다르다. 부분 함수이므로 모든 입력 조합에 대해 정의되어 있는 것은 아니다. 계산 가능 함수는 출력으로 하나의 자연수를 반환한다(이 출력을 짝 함수를 사용하여 자연수 목록으로 변환할 수도 있다). 어떤 부분 함수

f

가 인수

x_1,\ldots,x_k

에 대해 정의되어 있다는 것을

f(x_1,\ldots,x_k) \downarrow

로 표기하고, 정의된 값이

y

라는 것을

f(x_1,\ldots,x_k) \downarrow = y

로 표기한다. 이러한 함수를 '''부분 재귀 함수'''(Partial recursive function)라고도 부른다. 재귀 이론에서는 함수의 정의역을 해당 함수가 정의된 모든 입력 값들의 집합으로 정의한다.

모든 인수에 대해 정의된 함수를 전역 함수라고 부른다. 계산 가능 함수 중 전역 함수인 것을 '''전역 계산 가능 함수'''(Total computable function) 또는 '''전역 재귀 함수'''(Total recursive function)라고 부른다.

2. 2. 계산 가능한 집합

'''계산 가능한 집합'''(computable set)은 어떤 원소가 그 집합에 속하는지 여부를 알고리즘적으로, 즉 유한한 단계 안에 판단할 수 있는 집합을 말한다.^[1] 즉, 자연수의 부분집합 ''A''에 대해, 어떤 계산 가능한 함수 ''f''가 존재하여 다음 조건을 만족하면 집합 ''A''는 계산 가능하다고 한다:^[2]^[3]

만약 ''n''이 집합 ''A''의 원소이면, ''f''(''n'') = 1이다.
만약 ''n''이 집합 ''A''의 원소가 아니면, ''f''(''n'') = 0이다.

이때 함수 ''f''를 집합 ''A''의 특성 함수라고 부른다. 따라서 계산 가능한 집합은 그 특성 함수가 계산 가능한 함수인 집합과 같다. 계산 가능한 집합은 '''재귀적 집합'''(recursive set) 또는 '''결정 가능한 집합'''(decidable set)이라고도 불린다.^[3]^[4]

한편, 자연수의 부분집합 ''B''가 어떤 부분 계산 가능 함수 ''g''의 정의역과 일치할 때, 즉 ''n''이 ''B''의 원소인 것과 ''g''(''n'')이 정의되는 것이 필요충분조건일 때, 이 집합 ''B''를 '''계산 가능 열거 가능 집합'''(computably enumerable set, C.E. set)이라고 한다.^[5] 이 집합은 '''재귀적 열거 가능 집합'''(recursively enumerable set, R.E. set) 또는 '''준결정 가능 집합'''(semidecidable set)이라고도 불린다.

'열거 가능'(enumerable)이라는 이름은 다음과 같은 동치 관계에서 유래한다. 공집합이 아닌 자연수의 부분집합 ''B''에 대해 다음 두 조건은 서로 동치이다:

''B''는 어떤 계산 가능 함수의 정의역이다.
''B''는 어떤 전역 계산 가능 함수의 치역이다. (만약 ''B''가 무한 집합이라면, 이 함수는 단사 함수가 되도록 만들 수 있다.)

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

관계의 개념으로 확장하여, 자연수에 대한 유한 관계는 자연수의 유한한 순서쌍들의 집합으로 볼 수 있으므로, '''계산 가능 관계'''(computable relation)와 '''계산 가능 열거 가능 관계'''(computably enumerable relation) 역시 위에서 설명한 집합의 개념을 통해 유사하게 정의할 수 있다.

2. 3. 계산 가능하게 열거 가능한 집합 (귀납적 가산 집합, 준결정 가능 집합)

자연수의 집합

A

가 '''계산 가능하게 열거 가능'''(또는 '''귀납적으로 셀 수 있는 집합''', '''재귀적 열거 가능 집합''', '''준결정 가능 집합''', '''계산 가산 집합''')하다는 것은, 어떤 계산 가능 함수

f

가 존재하여, 자연수

n

에 대해

n

이 집합

A

에 속할 때, 그리고 오직 그때만

f(n)

이 정의될(즉, 계산이 유한 시간 내에 멈출) 경우를 말한다.^[1]^[2] 이는 어떤 값이 집합에 속하는 경우 그 사실을 유한한 단계 내에 확인할 수 있지만, 속하지 않는 경우에는 계산이 영원히 끝나지 않을 수도 있음을 의미한다.

따라서 어떤 집합이 계산 가능하게 열거 가능하다는 것은 그 집합이 어떤 계산 가능 함수의 정의역이라는 것과 동치이다.^[1]^[2]

'열거 가능'(enumerable)이라는 용어는 자연수의 공집합이 아닌 부분 집합

B

에 대해 다음 두 조건이 동치이기 때문에 사용된다:^[1]^[2]

$B$ 는 계산 가능한 함수의 정의역이다.
$B$ 는 전역 계산 가능 함수의 치역이다. 만약 $B$ 가 무한 집합이라면, 이 함수는 단사 함수라고 가정할 수 있다.

집합

B

가 함수

f

의 치역일 경우, 함수

f

는

B

의 열거로 볼 수 있다. 왜냐하면 목록

f(0), f(1), f(2), ...

이

B

의 모든 원소를 포함하기 때문이다.^[1]^[2]

자연수에 대한 각 유한 관계는 자연수의 유한 순서열(sequence)에 해당하는 집합으로 볼 수 있으므로, '''계산 가능하게 열거 가능한 관계'''(computably enumerable relation)의 개념도 집합에서와 유사하게 정의할 수 있다.^[1]^[2]

2. 4. 계산 가능 관계와 형식 언어

자연수에 대한 유한 관계는 자연수의 유한 수열(sequence)에 해당하는 집합으로 볼 수 있다. 이를 바탕으로, 자연수 집합에 대한 계산 가능성 개념을 확장하여 '''계산 가능 관계'''와 '''계산 가능 열거 가능 관계'''를 정의할 수 있다.^[1]^[2]

컴퓨터 과학의 계산 가능성 이론에서는 형식 언어를 다루는 것이 일반적이다.^[1]^[2]

'''알파벳'''은 임의의 기호(symbol) 집합이다.
알파벳 위의 '''단어'''(word)는 알파벳에 속한 기호들을 유한 개 나열한 것이다. 같은 기호가 여러 번 사용될 수 있다. 예를 들어, 이진 문자열은 알파벳 {0, 1} 위의 단어들이다.
'''언어'''(language)는 특정 알파벳으로 만들 수 있는 모든 단어들의 집합의 부분 집합이다. 예를 들어, 정확히 3개의 '1'을 포함하는 모든 이진 문자열의 모임은 이진 알파벳 위의 언어이다.^[1]^[2]

형식 언어의 중요한 속성 중 하나는 주어진 단어가 특정 언어에 속하는지 여부를 판별하는 문제의 난이도이다. 어떤 언어가 '''계산 가능'''(computable, 동의어: '''재귀적''', '''결정 가능''')하다는 것은, 그 언어의 알파벳으로 만들어진 모든 단어 ''w''에 대해 다음을 만족하는 계산 가능한 함수 ''f''가 존재한다는 의미이다:^[1]^[2]

단어 ''w''가 언어에 속하면 ''f''(''w'') = 1이다.
단어 ''w''가 언어에 속하지 않으면 ''f''(''w'') = 0이다.

따라서 어떤 언어가 계산 가능하다는 것은, 임의의 단어가 그 언어에 속하는지 여부를 항상 정확하게 결정할 수 있는 절차(알고리즘)가 존재한다는 뜻이다.^[1]^[2]

어떤 언어가 '''계산 가능하게 열거 가능'''(computably enumerable, 동의어: '''재귀적으로 열거 가능''', '''반결정 가능''')하다는 것은, 단어 ''w''가 그 언어에 속할 경우에만 계산 가능 함수 ''f''(''w'')가 정의되는(즉, 계산이 멈추고 결과를 내는) 함수 ''f''가 존재한다는 의미이다. 이 용어는 자연수의 계산 가능하게 열거 가능한 집합과 같은 맥락에서 사용된다.^[1]^[2]

3. 계산 가능 함수의 특징

계산 가능 함수의 기본적인 특징은 함수를 계산하는 방법을 알려주는 유한한 절차(알고리즘)가 반드시 존재해야 한다는 점이다. 다양한 계산 모델들이 이러한 절차를 다르게 표현하지만, 공통된 속성을 공유한다. 이는 마치 컴파일러가 한 언어로 작성된 명령을 다른 언어의 명령으로 변환하는 것과 유사하게, 각 모델이 다른 모델의 절차를 모방할 수 있기 때문이다.

엔더튼 [1977]은 계산 가능한 함수의 절차가 가져야 할 특징을 다음과 같이 제시했다. 유사한 특징은 튜링 [1936], 로저스(Rogers) [1967] 등 여러 학자에 의해서도 제시되었다.^[1]

명확하고 유한한 명령어: 절차를 위한 명확한 명령어(즉, 프로그램)가 유한한 길이로 존재해야 한다. 따라서 모든 계산 가능 함수는 그 함수를 계산하는 방법을 완전히 설명하는 유한한 프로그램을 가진다. 이 명령어들을 따르면 누구나 추측이나 특별한 지식 없이 함수를 계산할 수 있다.
정의역 내 입력 처리: 함수의 정의역에 속하는 입력값(예: ''k''-튜플 '''x''')이 주어지면, 절차는 유한한 횟수의 개별 단계를 거친 후 반드시 종료되어야 하며, 올바른 함수값('''f'''('''x'''))을 결과로 내놓아야 한다. 절차는 단계별로 진행되며, 각 단계에서 수행할 작업은 명확한 규칙에 따라 정해진다.
정의역 외 입력 처리: 함수의 정의역에 속하지 않는 입력값('''x''')이 주어지면, 절차는 영원히 계속 실행되거나(멈추지 않음), 특정 지점에서 멈출 수 있다(예: 더 이상 실행할 명령어가 없음). 하지만 어떤 경우에도 절대로 해당 입력값('''x''')에 대한 함수값을 결과로 내놓는 척해서는 안 된다. 즉, 절차가 어떤 값을 결과로 내놓았다면, 그 값은 반드시 올바른 값이어야 한다.

엔더튼은 이러한 기본적인 특징 외에도 다음과 같은 부가적인 설명을 덧붙였다.

임의 크기 인수 처리: 절차는 이론적으로 임의로 큰 입력값에 대해서도 작동해야 한다. 입력값의 크기가 특정 수(예: 지구상의 원자 수)보다 작아야 한다는 식의 제약은 없다.
시간 제한 없음: 절차는 결과를 내놓기까지 유한한 단계만 거치면 되지만, 그 단계 수가 아무리 많아도 상관없다. 실행 시간에 대한 제한은 가정하지 않는다.
무제한 저장 공간: 절차가 계산을 수행하는 동안 유한한 양의 저장 공간만을 사용하지만, 필요한 저장 공간의 총량에는 제한이 없다. 즉, 절차가 추가적인 저장 공간을 요구하면 언제든지 제공될 수 있다고 가정한다.

요약하자면, 어떤 함수가 계산 가능하다는 것은 그 함수의 정의역에 속하는 입력이 주어졌을 때, 무제한의 저장 공간을 활용하여 유한하고 명확한 명령어로 구성된 절차(알고리즘)를 따라 유한한 단계 안에 해당 출력을 정확히 계산하고 멈추는 절차가 존재한다는 의미이다. 만약 정의역에 속하지 않는 입력이 주어진다면, 절차는 영원히 멈추지 않거나, 멈추더라도 결과를 내놓지 않아야 한다.

계산 복잡도 이론 분야에서는 계산 가능한 함수 중에서도 특히 계산에 필요한 시간이나 사용하는 저장 공간에 일정한 제약(경계)이 있는 함수들을 주로 연구한다.

4. 예시

다음 함수들은 계산 가능한 함수의 예시이다.

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

만약 ''f''와 ''g''가 계산 가능하다면, 이들의 합(''f'' + ''g''), 곱(''f'' * ''g''), 함수 합성(f ○ g, 단 ''f''가 단항 함수일 경우), 최댓값(max(''f'', ''g'')), 최솟값(min(''f'', ''g'')), arg max {''y'' | ''y'' ≤ ''f''(''x'')} (특정 조건을 만족하는 가장 큰 입력값을 찾는 연산) 등 다양한 조합으로 만들어진 함수 역시 계산 가능하다.

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

π의 소수점 이하 전개에서 ''n''개의 '5'가 연속으로 나타나면 ''f''(''n'') = 1, 그렇지 않으면 ''f''(''n'') = 0으로 정의되는 함수 ''f''는 계산 가능하다. 이 함수 ''f''는 상수 함수 1이거나, 혹은 어떤 자연수 ''k''가 존재하여 ''n'' < ''k''일 때는 ''f''(''n'') = 1이고 ''n'' ≥ ''k''일 때는 ''f''(''n'') = 0인 형태의 함수 중 하나이다. 이러한 형태의 함수는 모두 계산 가능하다. 현재 π의 소수 전개에 임의로 긴 '5'의 연속이 존재하는지는 알려져 있지 않으므로, 위 두 가지 경우 중 실제로 어떤 함수가 ''f''인지는 알 수 없다. 하지만 어느 경우든 함수 ''f''는 계산 가능함이 보장된다.

비지 비버 함수 Σ와 같이 계산 불가능한 자연수 수열이라도, 그 수열의 유한한 부분(segment)은 계산 가능하다. 예를 들어, 임의의 자연수 ''n''에 대해, Σ(0), Σ(1), Σ(2), ..., Σ(''n'')까지의 유한한 항들을 계산하는 알고리즘은 존재한다. 이는 모든 ''n''에 대해 Σ(''n'') 값을 계산하여 수열 전체를 생성하는 알고리즘이 존재하지 않는다는 사실과 대조된다. 따라서 "0, 1, 4, 6, 13을 출력하라"는 Σ(0), Σ(1), Σ(2), Σ(3), Σ(4)를 계산하는 자명한 알고리즘이다. 마찬가지로, 어떤 주어진 ''n'' 값에 대해서도 Σ(0)부터 Σ(''n'')까지를 계산하는 알고리즘은 (비록 그 알고리즘이 실제로 발견되거나 알려지지 않았을 수 있더라도) 존재한다.

5. 처치-튜링 명제

'''처치-튜링 명제'''는 특정 속성들을 가진 절차로 계산할 수 있는 모든 함수는 계산 가능 함수라고 주장하는 명제이다. 이 속성들은 형식적으로 명확하게 정의하기 어렵기 때문에 처치-튜링 명제 자체를 수학적으로 증명할 수는 없다.

하지만 다음의 사실들이 이 명제를 뒷받침하는 근거로 여겨진다.

지금까지 알려진 여러 계산 모델들은 서로 동등한 계산 능력을 가지며, 모두 동일한 함수들을 '계산 가능'하다고 정의한다. (물론 이들보다 계산 능력이 약한 모델도 존재한다.)
일반적으로 유효 계산 가능하다고 여겨지는 계산 방법들보다 더 강력한 계산 모델은 아직까지 제안된 적이 없다.

처치-튜링 명제는 어떤 함수가 계산 가능하다는 것을 증명할 때, 특정 계산 모델(예: 튜링 기계) 위에서 작동하는 구체적인 절차를 일일이 작성하는 번거로움을 덜어주는 데 사용되기도 한다. 즉, 함수를 계산하는 절차(알고리즘)를 명확하게 설명하는 것만으로도, 처치-튜링 명제에 근거하여 해당 함수가 계산 가능하다고 인정하는 것이다. 이는 알려진 계산 모델들의 능력이 본질적으로 동일하다는 믿음 때문이다.

6. 증명 가능성과 재귀적 정의

어떤 함수나 집합이 계산 가능한지 여부뿐만 아니라, 특정 증명 시스템, 예를 들어 일계 페아노 산술 내에서 이것이 증명될 수 있는지 여부도 중요한 문제이다. 계산 가능하다고 증명될 수 있는 함수를 증명 가능 전체 함수라고 부른다.

증명 가능 전체 함수의 집합은 재귀적 가산 집합이다. 계산 가능성을 증명하는 모든 증명을 열거함으로써 모든 증명 가능 전체 함수를 열거할 수 있다. 이는 증명 시스템의 모든 증명을 나열하고 관련 없는 증명은 제외하는 방식으로 이루어진다.

재귀적 정의로 정의된 함수에서는 각 값이 이전에 정의된 다른 값(같은 함수 또는 상수일 수 있음)들의 고정된 1차 공식을 통해 정의된다. 원시 재귀 함수는 이러한 함수의 한 부분 집합이다. 또 다른 예시로는 아커만 함수가 있는데, 이 함수는 재귀적으로 정의되지만 원시 재귀 함수는 아니다.^[5]

이러한 재귀적 정의가 순환이나 무한 반복에 빠지지 않으려면, 정의 내에서 같은 함수를 다시 호출할 때 함수의 정의역(domain)에서 어떤 정렬 순서에 따라 더 작은 인수를 사용해야 한다. 예를 들어, 아커만 함수 ''A''의 경우, ''A''(''x'', ''y'')를 정의할 때 ''A''(''p'', ''q'')를 참조한다면, (''p'', ''q'')는 자연수 쌍에 대한 사전식 순서에서 (''x'', ''y'')보다 작아야 한다((''p'', ''q'') < (''x'', ''y'')). 아커만 함수나 원시 재귀 함수의 경우 정렬 순서는 명확하지만, 어떤 경우에는 참조 관계가 정렬 순서임을 증명하기 어려울 수 있다. 정렬된 방식으로 재귀적으로 정의된 모든 함수는 계산 가능하다. 각 값은 함수 호출 트리를 확장하여 계산할 수 있으며, 이 확장은 유한한 횟수 안에 끝나야 한다. 만약 그렇지 않다면, 쾨니그의 보조정리에 따라 무한히 감소하는 호출 순서가 존재하게 되어 정렬 순서라는 가정에 위배되기 때문이다.

무모순인 증명 체계에서는 증명 가능한 모든 전역 함수는 실제로 전역 함수이지만, 그 역은 항상 성립하지 않는다. 즉, 충분히 강력하고 무모순적인 모든 일차 논리 증명 체계(페아노 산술 포함)에서는, 해당 증명 체계 내에서 전역 함수임을 증명할 수 없는 전역 함수가 존재한다는 사실을 (다른 증명 체계에서) 증명할 수 있다.

만약 전역 계산 가능 함수들을 생성하는 튜링 기계를 통해 열거한다면, 증명 체계가 무모순적일 경우 위에서 설명한 증명 가능한 전역 함수의 열거와 유사한 대각선 논법을 사용하여 이 사실을 보일 수 있다. 관련 증명을 열거하는 튜링 기계를 사용하여, 모든 입력 ''n''에 대해 ''f''_''n''(''n'')을 호출한다 (여기서 ''f''_''n''은 이 열거 방식에 따른 ''n''번째 함수이다). 이는 ''n''번째 증명에 따라 함수를 계산하는 튜링 기계를 호출하여 수행된다. 이러한 튜링 기계는 증명 체계가 무모순적이라면 반드시 정지함이 보장된다.

7. 계산 불가능 함수와 결정 불가능 문제

모든 계산 가능 함수는 이를 계산하는 방법에 대한 명확하고 모호하지 않은 지침을 제공하는 유한한 절차를 가진다. 이 절차는 계산 모델에서 사용되는 유한한 알파벳(예: 비트 문자열 Σ = {0, 1})으로 부호화될 수 있으므로, 계산 가능한 함수는 가산 개수만큼 존재한다.

그러나 실수는 비가산적이므로 대부분의 실수는 계산 불가능하다. (계산 가능한 수 참조) 마찬가지로, 자연수에 대한 유한 함수의 집합은 비가산적이므로 대부분은 계산 불가능하다. 이러한 계산 불가능한 함수의 구체적인 예로는 비지 비버 함수, 콜모고로프 복잡성, 또는 Chaitin의 상수와 같이 계산 불가능한 수의 자릿수를 출력하는 모든 함수가 있다.

자연수의 부분 집합 역시 대부분 계산 불가능하다. 정지 문제는 이러한 계산 불가능한 집합 중 처음으로 구성된 예이다. 다비트 힐베르트가 제안한 결정 문제(Entscheidungsproblem)는 어떤 수학적 명제(자연수로 부호화됨)가 참인지 거짓인지를 결정하는 실효적인 절차가 존재하는지에 대한 질문이었다. 1930년대에 튜링과 처치는 이 문제가 결정 불가능하다는 것, 즉 해당 자연수의 집합이 계산 불가능하다는 것을 독립적으로 보여주었다. 처치-튜링 명제에 따르면, 이러한 계산을 수행할 수 있는 실효적인 절차(알고리즘)는 존재하지 않는다.

8. 계산 가능성 확장

함수의 계산 가능성 개념은 자연수의 특정 집합 ''A''나 함수 ''f''의 정보를 즉시 활용할 수 있는 오라클 기계를 가정하여 확장될 수 있다. 이러한 확장된 튜링 기계 모델을 사용하여 계산 가능한 함수는 주어진 집합 ''A''나 함수 ''f''에 상대화된 것으로 보며, 각각 '''A-계산 가능''' 또는 '''f-계산 가능'''이라고 부른다.

또한, 처치-튜링 명제가 제시하는 일반적인 알고리즘의 개념을 넘어서는 더 넓은 범위의 계산 가능성 모델들도 연구되고 있다. 예를 들어, 하이퍼컴퓨팅 분야에서는 무한한 계산 단계를 허용하는 모델을 연구하며, '''E-재귀 이론'''과 같이 임의의 집합을 입력으로 사용하는 일반화된 재귀 이론도 존재한다.

8. 1. 상대적 계산 가능성

함수의 계산 가능성 개념은 임의의 집합 ''A'' 또는 자연수에서 자연수로의 함수 ''f''에 대해 상대화될 수 있다. 이는 특정 집합 ''A''나 함수 ''f''의 정보를 마치 오라클처럼 즉시 접근하여 활용할 수 있도록 확장된 튜링 기계(오라클 기계)를 가정하는 것이다.

어떤 함수가 집합 ''A''를 오라클로 사용하여 계산될 수 있을 때, 이를 '''A에서 계산 가능'''하다고 하며, '''A-계산 가능''' 또는 '''A에 상대적으로 계산 가능'''이라고도 부른다. 마찬가지로, 함수 ''f''를 오라클로 사용하여 계산 가능한 함수는 '''f-계산 가능'''이라고 한다. 이러한 개념은 튜링 환원과 밀접하게 연관된다.

상대적 계산 가능성은 기본적인 계산 가능성 개념처럼 다양한 계산 모델에서 동등하게 정의될 수 있다. 일반적으로 이는 '주어진 자연수가 집합 ''A''에 속하는가?'와 같은 질문에 답하는 기본 연산을 계산 모델에 추가하는 방식으로 구현된다. 또한, 함수 ''f''가 다른 함수 ''g''의 정보를 이용하여 계산될 수 있다면 '''g에서 계산 가능'''하다고 말할 수도 있다.

8. 2. 고차 재귀 이론과 하이퍼컴퓨팅

초산술 이론은 공집합의 튜링 점프를 계산 가능한 순서수만큼 반복하여 계산할 수 있는 집합들을 연구한다. 이는 2차 산술 언어에서 보편적 및 존재적 양화사를 모두 사용하여 정의된 집합과 동일하며, 초계산의 일부 모델과도 관련이 있다.

더 일반화된 재귀 이론으로 '''E-재귀 이론'''이 연구되었는데, 이는 E-재귀 함수의 인수로 임의의 집합을 사용할 수 있도록 허용한다.

처치-튜링 명제는 알고리즘을 가진 모든 함수가 계산 가능 함수에 포함된다고 명시하지만, 알고리즘이 갖춰야 할 요건을 완화하여 더 넓은 종류의 함수를 고려하는 것이 가능하다. 하이퍼컴퓨팅 분야는 이러한 관점에서 일반적인 튜링 기계의 계산 능력을 넘어서는 계산 모델들을 연구한다. 예를 들어, 답을 얻기 위해 무한한 단계를 실행할 수 있는 계산 가능성 표기법 등이 연구 대상이다.

참조

_[1] 서적 A Mathematical Introduction to Logic Elsevier 2002
_[2] 서적 A Mathematical Introduction to Logic Elsevier 2002
_[3] 서적 Computable Structures and the Hyperarithmetical Hierarchy Studies in Logic and the Foundation of Mathematics 2000
_[4] 간행물 Computability and Recursion http://www.people.cs[...] 1995
_[5] 논문 Konstruktion nichtrekursiver Funktionen

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com