정의
계산 가능한 수(Computable number)란, 자연수 인덱스에 따라 그 수의 유한한 자리수(또는 소수점 이하 자리수)를 효과적인 알고리즘, 즉 튜링 기계나 다른 형태의 결정 가능한 절차에 의해 구할 수 있는 실수 또는 복소수를 말한다. 보다 구체적으로, 실수 $x$가 계산 가능하다는 것은 다음과 같은 튜링 기계 $M$가 존재함을 의미한다.
- 입력으로 자연수 $n$을 받으면, $M$은 $x$의 소수점 이하 $n$번째 자리수를 정확히 출력한다.
- $M$은 언제나 정지(halts)한다.
이 정의는 1936년에 앨런 튜링이 제시한 튜링 가산성(Turing‑computable) 개념을 실수에 적용한 형태이다.
역사·어원
‘계산 가능한’은 한국어 동사 ‘계산하다(計算하다)’에 형용사형 전성 어미 ‘‑ㄹ 수 있다’를 붙인 형태이며, 영어 표현 ‘computable’을 직역·의역한 용어이다. 컴퓨터 과학과 수리 논리학 분야에서 20세기 중반부터 사용되었으며, 특히 튜링의 논문 On Computable Numbers, with an Application to the Entscheidungsproblem (1936)에서 제시된 ‘computable numbers’가 한국어 학술 번역에서 ‘계산 가능한 수’로 번역되었다.
관련 개념
| 개념 | 설명 |
|---|---|
| 튜링 기계 | 이론적 계산 모델; 계산 가능한 수의 정의에 사용됨. |
| 재귀 가능한(real recursive) 함수 | 튜링 기계로 구현 가능한 함수; 계산 가능한 수의 자리수 함수를 나타냄. |
| 알고리즘 | 명시된 절차에 따라 단계별로 수행되는 작업; 계산 가능한 수는 알고리즘에 의해 자리수를 구할 수 있음. |
| 비계산 가능한 수 | 어떤 알고리즘으로도 모든 자리수를 산출할 수 없는 수(예: 챈스키의 대각선 논법에 의해 존재가 증명됨). |
주요 성질
-
가산성
계산 가능한 실수의 집합은 가산 집합이다. 이는 모든 튜링 기계가 가산 개수이므로, 각 기계에 대응되는 실수도 가산 개수임을 의미한다. 따라서 실수 전체(비가산)와 비교해 ‘대다수의 실수는 계산 불가능’하다는 결과가 도출된다. -
폐쇄성
두 계산 가능한 실수의 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈(0 제외))은 역시 계산 가능하다. 또한, 유리함수·초월함수·삼각함수 등 대부분의 표준 수학적 연산에 대해서도 계산 가능성이 유지된다. -
표현 방법
- 프로그래밍: 특정 실수를 근사하는 알고리즘을 구현함으로써 계산 가능성을 증명한다.
- 수열: 수열 ${a_n}$이 점근적으로 $x$에 수렴하고, 각 $a_n$을 효과적으로 구할 수 있으면 $x$는 계산 가능하다.
학술적 활용
- 컴퓨터 과학: 계산 가능성 이론, 복잡도 이론, 형식 언어와 자동 이론 등에서 기본 전제로 다루어진다.
- 수학: 실해석, 측도론에서 비가산 실수와의 대비를 통해 “실제 계산 가능한 수”와 “이론적 존재수”를 구분한다.
- 철학: 수학적 대상의 존재론적 논의에서 ‘계산 가능한’이라는 기준은 ‘구성주의’와 ‘플라톤주의’ 사이의 논쟁에 활용된다.
참고문헌(대표)
- Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42), 230–265.
- Cutland, N. J. (1980). Computability: An Introduction to Recursive Function Theory. Cambridge University Press. (한국어 번역판: 재귀 가능성 이론 입문)
- Soare, R. I. (2016). Turing Computability: Theory and Applications. Springer.
요약
계산 가능한 수는 알고리즘에 의해 그 자리수를 유한 시간 내에 산출할 수 있는 실수(또는 복소수)이며, 튜링 기계와 재귀 함수 이론을 기반으로 정의된다. 이 개념은 현대 컴퓨터 과학·수리 논리학의 핵심 요소로, 가산성, 폐쇄성 등의 수학적 특성을 가진다.
