계산 가능한 수

3. 형식적 정의

실수 ''a''가 계산 가능한 함수 $f:\backslash mathbb\{N\}\backslash to\backslash mathbb\{Z\}$에 의해 다음 조건을 만족하면 '''계산 가능'''하다고 한다. 임의의 양의 정수 ''n''에 대해, 다음을 만족하는 정수 ''f''(''n'')을 생성한다.

:$\{f(n)-1\backslash over\; n\}\; \backslash leq\; a\; \backslash leq\; \{f(n)+1\backslash over\; n\}.$

복소수는 실수부와 허수부가 모두 계산 가능하면 계산 가능하다고 한다.

3. 1. 동치 정의

• 임의의 양의 오차 한계 $\backslash varepsilon$가 주어지면 $|r\; -\; a|\; \backslash leq\; \backslash varepsilon$를 만족하는 유리수 ''r''을 생성하는 계산 가능한 함수가 존재한다.
• 각 ''i''에 대해 를 만족하고 $a$로 수렴하는 계산 가능한 유리수열 $q\_i$가 존재한다.

4. 성질

튜링 머신 정의에 괴델 수를 할당하면 계산 가능한 수에 해당하는 자연수 부분 집합 $S$가 생성되고, $S$에서 계산 가능한 수로의 전사가 식별된다. 튜링 머신은 셀 수 있을 만큼만 존재하므로, 계산 가능한 수는 가산 이하임을 알 수 있다. 그러나 괴델 수의 집합 $S$는 계산 가능 열거 가능하지 않은데, 이는 어떤 괴델 수가 계산 가능한 실수를 생성하는 튜링 머신에 해당하는지 결정하는 알고리즘이 없기 때문이다. 계산 가능한 실수를 생성하려면 튜링 머신이 전체 함수를 계산해야 하지만, 해당 결정 문제는 튜링 차수 '''0′′'''에 있다. 따라서 자연수에서 계산 가능한 실수를 나타내는 머신 집합 $S$로의 전사 계산 가능 함수는 없으며, 칸토어의 대각선 논법으로는 계산 가능한 실수가 무수히 많음을 구성적으로 증명할 수 없다.

실수 집합은 비가산 집합이지만, 계산 가능한 수 집합은 가산 집합이므로 거의 모든 실수는 계산 가능하지 않다. 주어진 계산 가능한 수 $x$에 대해, 정렬 원리에 따라 $x$에 해당하는 $S$의 최소 원소가 존재하며, 따라서 맵이 전단사 함수인 최소 원소로 구성된 부분 집합이 존재한다. 이 전단사 함수의 역함수는 계산 가능한 수에 대한 자연수로의 단사 함수이며, 이는 계산 가능한 수가 가산 집합임을 증명한다. 그러나 계산 가능한 실수가 자체적으로 정렬되어 있음에도 이 부분 집합은 계산 가능하지 않다.

4. 1. 체(Field)로서의 성질

4. 2. 정렬의 계산 불가능성

4. 3. 기타 성질

• 정지 문제(또는 다른 결정 불가능 문제)의 해를 선택된 인코딩 방식에 따라 인코딩하는 모든 수.
• 차이틴 상수 $\backslash Omega$는 정지 문제와 튜링 차수가 같은 종류의 실수이다.

5. 숫자열과 칸토어 공간 및 베르 공간

앨런 튜링의 원래 정의는 계산 가능한 수를 십진법 전개로 정의했지만, 이는 현대적인 정의와 동등하다. 실수의 위상적 속성이 중요하지 않은 경우, [0, 1] 구간의 실수 대신 2^ω^영어 (이진 함수 공간) 또는 ω^ω^영어 (자연수 함수 공간)의 원소를 다루는 것이 편리할 수 있다.

2^ω^영어의 원소는 이진 십진법 전개와 동일시될 수 있지만, 십진법 전개 .d_1d_2… d_n0111…^영어와 .d_1d_2… d_n10^영어은 동일한 실수를 나타내므로, 간격 [0, 1]은 모든 1로 끝나지 않는 2^ω^영어의 부분 집합과 전단사적으로 동일시될 수 있다.

계산 가능성 이론가들은 종종 2^ω^영어의 구성원을 실수라고 부르며, 2^ω^영어는 완전 불연결이지만, Π^0_1^영어 클래스 또는 무작위성에 대한 질문의 경우 2^ω^영어에서 작업하는 것이 더 쉽다. ω^ω^영어의 원소도 때때로 실수라고 불리며, ω^ω^영어는 국소 콤팩트조차 아니다.

6. 실수 대신 사용

계산 가능한 수는 대수적 수뿐만 아니라, ''e'', ''π'' 및 많은 다른 초월수를 포함하여 실제로 나타나는 대부분의 실수를 포함한다. 계산 가능한 실수는 우리가 계산하거나 근사할 수 있는 실수를 모두 포함하지만, 모든 실수가 계산 가능하다는 가정은 실수에 대해 실질적으로 다른 결론으로 이어진다. 모든 실수 집합을 없애고 모든 수학에 계산 가능한 수를 사용할 수 있는지에 대한 질문이 제기되며, 이 아이디어는 구성주의 관점에서 매력적이며, 러시아 구성 수학 학파에서 추구해 왔다.^[5]

계산 가능한 수에 대한 해석학을 개발하는 데는 주의가 필요하다. 예를 들어, 고전적인 수열의 정의를 사용하면, 계산 가능한 수의 집합은 유계 수열의 상한을 취하는 기본 연산에 대해 닫혀 있지 않다(예를 들어, 슈페커 수열 참고). 이러한 어려움은 계산 가능한 수렴 계수를 갖는 수열만 고려함으로써 해결된다. 결과적인 수학 이론은 계산 가능 해석학이라고 불린다.

7. 정확한 산술 구현

실수를 근사값으로 계산하는 프로그램을 나타내는 컴퓨터 패키지는 1985년 이전에 "정확한 산술"이라는 이름으로 제안되었다.^[6] 현대적인 예로는 CoRN 라이브러리(Coq)^[7], RealLib 패키지(C++)^[8] 등이 있다. 이와 관련된 작업은 iRRAM^영어 패키지와 같이 충분한 정밀도의 유리수 또는 부동 소수점 숫자로 실수 RAM 프로그램을 실행하는 것을 기반으로 한다.^[8]

참조

_[1] 서적 Computable analysis https://eudml.org/do[...] Institute of Mathematics of the Polish Academy of Sciences
_[2] 논문 Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators
_[3] 논문 The present theory of Turing machine computability
_[4] 서적 Classical Recursion Theory North-Holland
_[5] 논문 The constructive mathematics of A. A. Markov
_[6] 서적 Proceedings of the 1986 ACM conference on LISP and functional programming - LFP '86 1986-08-08
_[7] 서적 Theorem Proving in Higher Order Logics 2008
_[8] 서적 Computability and Complexity in Analysis Springer 2001
_[9] 논문 Exact real arithmetic: a case study in higher order programming http://fricas-wiki.m[...] 1986-08-08
_[10] 논문 Certified Exact Transcendental Real Number Computation in Coq https://arxiv.org/pd[...] 2008
_[11] 논문 A Survey of Exact Arithmetic Implementations https://link.springe[...] Springer 2001