계산 가능한 수

수학에서 계산 가능한 숫자는 유한 종단 알고리즘에 의해 원하는 정밀도 내에서 계산될 수 있는 실제 숫자다. 그것들은 또한 재귀수, 유효수^[1] 또는 계산 가능한 실재 또는 재귀 실재로도 알려져 있다.^{[citation needed]}

알고리즘의 공식 표현으로 μ-recursive 함수, 튜링 머신 또는 λ-미적분을 사용하여 등가 정의를 제공할 수 있다. 계산 가능한 숫자들은 실제 폐쇄된 영역을 형성하며, 모든 것은 아니지만 많은 수학적인 목적을 위해 실제 숫자 대신에 사용될 수 있다.

튜링 머신을 사용한 비공식 정의 예

다음에서 마빈 민스키는 1936년 앨런 튜링에 의해 정의된 것과 유사한 방식으로 계산될 숫자를 정의한다.^[2] 즉, 0과 1 사이의 "소수 분수로 해석되는 자릿수 순서"로 정의한다.^[3]

계산 가능한 숫자 [is]는 초기 테이프에서 n번째 숫자로 끝나는 튜링 기계가 있는 숫자 [is]이다.

정의에서 핵심 개념은 (1) 일부 n이 시작 시 지정된다는 것, (2) n에 대한 계산은 제한된 수의 스텝만 수행하며, 그 후에는 기계가 원하는 출력을 생성하고 종료된다는 것이다.

(2)의 대체 형태 - 기계는 연속적으로 테이프에 있는 모든 n자리 수를 인쇄하고 n번째 숫자를 인쇄한 후 멈춤 - 민스키의 관찰을 강조한다: (3) 튜링 기계를 사용함으로써 - 기계 테이블의 형태로 - 유한한 정의 - - 십진수의 잠재적으로 무한 문자열인 것을 정의하기 위해 사용되고 있다.

그러나 이것은 단지 주어진 정확성 내에서만 결과를 정확하도록 요구하는 현대적인 정의는 아니다. 위의 비공식적 정의는 테이블메이커의 딜레마라고 불리는 반올림 문제에 따르는 반면 현대적 정의는 그렇지 않다.

형식 정의

계산 가능한 함수 $f{\displaystyle }$: N${\displaystyle }$→ ${\displaystyle Z\mathbb{}}$ ${\$에 의해$$ 추정될 수 있는 실제 숫자 a는 다음과 같은 정수 f(n)를 산출할 수 있다.

${\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}$

이와 동등한 두 가지 유사한 정의가 있다.

• 계산 가능한 함수가 있으며, 계산 가능한 함수는 양의 합리적 오류 $바인딩{\displaystyle }$ { ${\displaystyle \varepsilon$ $\}$에 ${\displaystyle \mathrm{따라}}$ r -$$ . {\$displaystyle r-a \leq \varepsilon .}$과 같은 합리적인 숫자 r을 생성한다.
• 합리적인 숫자 $q{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$가 각 i에 대해 -+ < - i $displaystyle q_{i+1}$ $<2^{-i}\}}}$과(와)$$같은 {\$displaystystyle$ a$$$}$에 수렴하는 계산 가능한 시퀀스가 있다.

계산 가능한 디데킨드 컷을 통한 계산 가능한 숫자의 또 다른 동등한 정의가 있다. A computable Dedekind cut is a computable function ${\displaystyle D\;}$ which when provided with a rational number ${\displaystyle r}$ as input returns ${\displaystyle D(r)=\mathrm {true} \;}$ or ${\displaystyle D(r)=\mathrm {false} \;}$, satisfying the following conditions:

${\displaystyle \exists rD(r)=\mathrm {true} \;}$

${\displaystyle \exists rD(r)=\mathrm {false} \;}$

${\displaystyle(D(r)=\mathrm {true})\wedge(D(s)=\mathrm {false})\Rightarrow r<s\;}$

${\displaystyle D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true}.\;}$

예는 3의 큐브 루트를 정의하는 D 프로그램에 의해 주어진다. > ${\$을(를) 가정하면 다음과 같이 정의된다.

${\displaystyle p^{3}<3q^{3}\오른쪽 화살표 D(p/q)=\mathrm {true} \;}$

${\displaystyle p^{3}>3q^{3}\오른쪽 화살표 D(p/q)=\mathrm {false}.\;}$

실제 숫자는 그것에 해당하는 계산 가능한 Dedekind 컷 D가 있는 경우에만 계산할 수 있다. 함수 D는 각 계산 가능한 숫자에 대해 고유하다(물론 두 개의 다른 프로그램이 동일한 기능을 제공할 수도 있다).

복잡한 숫자는 그것의 실제와 가상의 부분이 계산될 수 있다면 계산 가능하다고 불린다.

특성.

계산적으로 열거할 수 없음

각 튜링 시스템 정의에 괴델 번호를 할당하면 계산 가능한 숫자에 해당하는 자연 숫자의 부분 집합$$ S ${\displaystyle S}$이(가) 생성되고 계산 가능한 숫자에 대한$$ $S{\displaystyle }$ ${\displaystyle S}$의 추출을 식별한다. 계산 가능한 숫자들이 하위 카운트 가능하다는 것을 보여주는 튜링 기계는 셀 수 없이 많다. 그러나 이러한 괴델 숫자의 $S$ ${\displaystyle S}$ 집합은 계산적으로 열거할 수 없다(결과적으로 $S{\displaystyle }$ ${\displaystyle S}$의 하위 집합은$$ 그것과 관련하여 정의된 S {\displaystyle S}의 하위 집합도 아니다). 계산 가능한 실물을 생산하는 튜링 기계에 해당하는 괴델 숫자가 어떤 것인지 판단할 알고리즘이 없기 때문이다. 계산 가능한 실물을 생산하기 위해 튜링 기계는 총 함수를 계산해야 하지만, 해당 결정 문제는 튜링 도 0′에 있다. 따라서 자연수에서 계산 가능한 실제에 이르는 계산적 함수는 없고, 칸토어의 대각선 인수는 헤아릴 수 없을 정도로 많은 것을 증명하기 위해 건설적으로 사용될 수 없다.

실수의 집합은 계산할 수 없는 반면, 계산 가능한 숫자의 집합은 분류적으로 계산할 수 있고, 따라서 거의 모든 실수의 집합은 계산할 수 없다. 여기서, 계산 가능한 $숫자{\displaystyle }$ x${\displaystyle }$, ${\displaystyle x}$에 대해 웰$$ 순서 원리는 s$${\$displaystyle$S}에 x$${\$displaystyle$x$\}$에 해당하는 최소 요소가 있음을 제공하며, 따라서 지도가 편향된 최소 요소로 구성된 하위 집합이 존재한다. 이 편향의 역행은 계산 가능한 숫자의 자연수에 주입하는 것으로, 계산 가능한 숫자임을 증명한다. 그러나, 다시 말하지만, 계산 가능한 실물이 스스로 정렬되어 있음에도 불구하고, 이 부분집합은 계산할 수 없다.

필드로서의 속성

계산 가능한 숫자에 대한 산술 연산 자체는 실제 숫자 a와 b를 계산할 수 있을 때마다 다음과 같은 실제 숫자도 계산할 수 있다는 점에서 계산 가능하다: b가 0이 아닌 경우 a + b, a - b, ab, a/b. 이러한 작업은 실제로 균일하게 계산할 수 있다. 예를 들어, 입력(A,${\displaystyle }$, {, ${,$ \$displaystyle \epsilon$에서 출력 r을 생성하는 튜링 시스템이 있다. 여기서 A는 튜링 시스템의 설명이고, B는 튜링 시스템의 설명 b, $r$은$$r {\$displaystyle \epsilon }$근사시오$$.a+b의 n

계산 가능한 실수가 한 분야를 형성한다는 사실은 1954년 헨리 고든 라이스에 의해 처음 증명되었다.^[4]

그러나 계산 가능한 실물은 계산 가능한 필드를 형성하지 않는다. 계산 가능한 필드의 정의는 효과적인 평등을 요구하기 때문이다.

주문의 비컴퓨터성

계산 가능한 숫자의 순서 관계는 계산할 수 없다. A를 Turing 시스템에 대한 설명으로, $숫자{\displaystyle }$ a ${\displaystyle a$에 가깝다. 그러면 입력 A에서 보다큰 경우 "YES"를 출력하고 ${\displaystyle \le }$ ${\displaystyle 0.}$ ${\displaystyle a\leq$ 0$.}$인 경우 "NO"를 출력하는 튜링 시스템이 없으므로 A에서 설명하는 시스템이 계속해서 0을 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$ 근사치로$$ 출력한다고 가정해 보십시오$$. 기계가 a를 양성으로 강제하는 근사치를 절대 출력하지 않을 것이라고 결정하기 전에 얼마나 기다려야 하는지는 명확하지 않다. 따라서 기계는 출력을 생성하기 위해 결국 숫자가 0과 같을 것이라는 것을 추측해야 할 것이다; 그 순서는 나중에 0과 다를 수 있다. 이 아이디어는 기계가 총 함수를 계산하는 경우 일부 시퀀스에서 기계가 부정확하다는 것을 보여주는 데 사용될 수 있다. 계산 가능한 실물이 데데킨드 컷으로 표현될 때 비슷한 문제가 발생한다. 평등 관계에 대한 동일한 보유: 평등 시험은 계산할 수 없다.

전체 순서 관계는 계산할 수 없지만, 불평등 숫자 쌍으로 제한한다. 즉, 입력 2개의 튜링 머신 A와 B에 근사치인 숫자 a와 b(여기서 ≠ b)를 취하여< ${\displaystyle$ a $<b}$ 또는 > $. {\displaysty$ a>$b$를 출력하는 프로그램이 있다$.$$}}$ < - a/ , ${\displaystyle \varepsilon$< $b-a /2},$ 따라서 점점 작아지는 (0에 근접함$)$을 취함으로써 <b ${\displaysty a <b}$ 또는 > ${\displaysty a>b$를 결정할 수 있다.$}$

기타 속성

계산 가능한 실수는 분석에 사용된 실수의 모든 속성을 공유하지는 않는다. 예를 들어, 계산 가능한 실제 숫자의 계산 가능한 증가 순서의 최소 상한은 계산 가능한 실제 숫자가 될 필요가 없다.^[5] 이 성질을 가진 수열은 스피커 수열로 알려져 있는데, 첫 번째 건설은 1949년 에른스트 스피커 때문이다.^[6] 이와 같은 백반샘플이 존재함에도 불구하고 계산 가능한 숫자 분야에서 미적분 부분과 실제 분석이 개발될 수 있어 계산 가능한 분석의 연구로 이어질 수 있다.

계산 가능한 모든 숫자는 산술적으로 정의할 수 있지만, 그 반대의 경우도 아니다. 산술적으로 정의할 수 있고 계산이 불가능한 실수에는 다음을 포함하여 많은 수가 있다.

• 선택한 인코딩 방식에 따라 중지 문제(또는 기타 확인되지 않은 문제)의 해결책을 인코딩하는 숫자.
• 차이틴의 상수인 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$은$($는) 정지 문제와 동등한 튜링(Turing)의 실수의 일종이다.

이 두 예 모두 실제로 정의가 가능하고, 각 범용 튜링 기계에 대해 한 개씩 계산이 불가능한 무한대의 숫자 집합을 정의한다. 실제 숫자는 그것이 나타내는 자연수 집합(이진수로 작성되고 특성 함수로 볼 때)을 계산할 수 있는 경우에만 계산된다.

계산 가능한 실수의 집합(모든 계산 가능한, 끝이 없는 계산 가능한 실수의 촘촘한 부분 집합)은 이성적인 숫자의 집합에 대해 순서가 이형적이다.

숫자 문자열 및 캔터 및 바이어 공간

튜링의 원래 논문은 다음과 같이 계산 가능한 숫자를 정의했다.

실제 숫자는 어떤 알고리즘이나 튜링 기계에 의해 자릿수 순서가 생성될 수 있다면 계산할 수 있다. 알고리즘은 정수 n${\displaystyle \mathrm{n}}$ 1 ${\displaystyle n\geq$ 1$}$을(를) 입력으로$$ 사용하고, 실수의 소수 $확장{\displaystyle }$ 중 n ${\displaystyle n}$ -번째 숫자를$$ 출력한다.

(a의 소수점 확장이란 소수점 뒤에 오는 숫자만을 가리킨다.)

Turing은 이 정의가 위에 $제시$된 $\$ {\$displaystyle \epsilon}$ - closimation$$ 정의와 동일하다는 것을 알고 있었다. 다음과 같다 주장:숫자를Turing 의미에서 계산할 수 있는 것도ϵ{\displaystyle \epsilon}의미에서:n을 계산할 수 있는, 로그 10⁡(1/ϵ){\displaystyle n>, \log_{10}(1/\epsilon)}, 그 후 소수 전개의를 제공한ϵ{\displaystyle \epsilon}a의 첫번째와 숫자 진행을pproxa의 모사 반대로 계산 가능한$$ 실제 숫자 a $pick{\displaystyle }$ ${\displaystyle \epsilon$ }을$($를) 선택하고 소수점 이후 n번째 자리까지 점차 정밀한 근사를 생성한다. 이는 항상 a와 동일한 소수점 확장을 생성하지만, 9의 무한 시퀀스로 부적절하게 종료될 수 있으며, 이 경우 유한(따라서 계산 가능한) 적절한 소수점 확장을 가져야 한다.

실수의 특정한 위상적 특성이 관련되지 않는 한$,{\displaystyle }$ [${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]}$에 있는 실수 대신에 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\$}}}(총 0.1 값 함수)의 요소를 다루는 것이 더 편리한 경우가 많다$.$ $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\$come$}$의 멤버는 bi와 구별할 수 있다$$.nary decimal expansions but since the decimal expansions ${\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }$ and ${\displaystyle .d_{1}d_{2}\ldots d_{n}10}$ denote the same real number the interval ${\displaystyle [0,1]}$ can only be bijectively (and home$2\Omega {\displaystyle {\mathrm{}}^{}}$ {\$displaystyle 2^{\omega }}$의 ${\displaystyle {부분}^{}}$ 집합으로 식별된 부분 집합 위상 아래 생략)이 모두 1로 끝나지 않는다$$$.$

이 십진 확장 속성은 십진 확장 측면에서 정의된 계산 가능한 실제 숫자와 $approx{\displaystyle }$ ${\displaystyle \epsilon }$ 근사$$ 의미에 정의된 숫자를 효과적으로 식별할 수 없음을 의미한다는 점에 유의하십시오. 허스트는 계산 가능한 숫자 a에 대해 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$ 근사를$$ 생성하고 Turing의 정의에 따라 의 숫자를 열거하는 Turing 시스템을 출력하는 Turing 시스템의 설명을 입력으로 사용하는 알고리즘이 없음을 보여 주었다.^[7] 마찬가지로 계산 가능한 실물의 산술 연산은 십진수를 추가할 때와 같이 십진수 표시에 효과적이지 않다는 것을 의미하며, 한 자릿수를 생성하기 위해서는 임의로 오른쪽을 멀리 보아야 현재 위치에 운반이 있는지 판단할 수 있다. 이러한 균일성의 결여는 계산 가능한 숫자의 현대적 정의가 소수점 확대보다는 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$ 근사치를$$ 사용하는 한 가지 이유다.

그러나 계산적 또는 측정적 이론적 관점에서 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\$ 2$^{\omega }$과${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]}$은 본질적으로 동일하며$$, 계산성 이론가들은 종종 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\$의 구성원을 실재로서$$ 언급한다. $[{\displaystyle }$ ${\displaystyle 0}$,${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]}$ ${\displaystyle {}_{}^{}}$ ${\$ ${\$ 클래스나$$ 임의성에 대한 문의는 ${\displaystyle {2\Omega }^{}}${\$displaystyle$ 2$^{\m }}$에서 작업하는 것이 훨씬 덜 지저분하다$.$

${\$의 원소도 리얼이라고 부르기도$$ 하며, 완전히 분리되어 있는 것 외에$$ $R{\displaystyle \mathbb{}}${\$displaystyle \mathb{R}}$${\displaystyle {\Omega }^{}}$ {\$displaysty \omega ^{\omega }}}}}$의 동형 이미지를 포함하고 있음에도 불구하고 로컬로 압축되어 있지 않다. 이것은 계산 속성의 진정한 차이를 이끈다. For instance the ${\displaystyle x\in \mathbb {R} }$ satisfying ${\displaystyle \forall (n\in \omega )\phi (x,n)}$ with ${\displaystyle \phi (x,n)}$ quantifier free must be computable while the unique ${\displaystyle x\in \omega ^{\omega }}$ satisfying a universal formula는 고산술 계층 구조에서 임의로 높을 수 있다.

진짜 대신 사용

계산 가능한 숫자들은 e, π, 그리고 많은 다른 초월적인 숫자들뿐만 아니라 모든 실제 대수 숫자를 포함하여 실제에 나타나는 구체적인 실수를 포함한다. 계산 가능한 실체들이 우리가 계산하거나 근사할 수 있는 실체들을 소진하지만, 모든 실체들이 계산 가능하다는 가정은 실수에 대해 실질적으로 다른 결론을 이끌어낸다. 자연스레 모든 실물을 처분하고 모든 수학에 계산 가능한 숫자를 사용하는 것이 가능한가 하는 의문이 생긴다. 이 생각은 구성주의적 관점에서 호소하고 있으며, 에렛 비숍과 프레드 리치먼이 러시아식 건설 수학 학교라고 부르는 것에 의해 추구되어 왔다.^{[citation needed]}

계산 가능한 숫자에 대한 분석을 실제로 개발하기 위해서는 주의를 기울여야 한다. 예를 들어, 어떤 사람이 수열의 고전적 정의를 사용하는 경우, 한정된 수열의 우월성을 취하는 기본 연산 하에서 계산 가능한 숫자 세트가 닫히지 않는다(예를 들어, Specker 수열을 고려한다, 위의 단원을 참조한다). 이 어려움은 계산 가능한 수렴 계수가 있는 시퀀스만 고려함으로써 해결된다. 그 결과로 나온 수학 이론을 계산 가능한 분석이라고 한다.

실행

계산 가능한 실제 숫자로 작동하는 몇몇 컴퓨터 패키지가 있는데, 이는 실제 숫자를 프로그램 계산 근사치로 나타낸다. RealLib 패키지가 한 예다.^[8]

참고 항목

• 생성 가능한 수
• 정의 가능한 수
• 반투명함수
• 트랜스컴퓨팅 문제

메모들

참조

추가 읽기