계산 가능한 분석

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2021년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수학과 컴퓨터 과학에서 계산 가능한 분석은 계산가능성 이론의 관점에서 수학적 분석을 연구하는 학문이다. 그것은 계산 가능한 방법으로 수행될 수 있는 실제 분석과 기능 분석의 부분과 관련이 있다. 그 분야는 건설적 분석과 수치적 분석과 밀접한 관련이 있다.

주목할 만한 결과는 (리만 적분이라는 의미에서) 통합이 계산 가능하다는 것이다. 이것은 필수불가결한 것이 무한한 금액이기 때문에 놀라운 것으로 여겨질 수도 있다. 이 결과는${\displaystyle \mathbb{}}$[ ${\displaystyle 0\mathrm{},}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle \mathb {[} 0,$1$$]}부터$$R {\$displaystyle \mathb${R$}}$까지 계산 가능한 함수가 모두 균일하게 연속성이라는$$ 사실로 설명될 수 있지만, 주목할 만한 점은 명시적으로 주어지지 않고 항상 계산될 수 있다는 점이다. 이와 유사하게 놀라운 사실은 복잡한 기능의 분화도 계산이 가능한 반면, 실제 기능에 대해서는 동일한 결과가 거짓이라는 것이다.

위와 같은 동기부여 결과는 비숍의 건설적 분석과는 상충되지 않는다. 그 대신 건설적 논리에서 상대방을 제공하는 것이 브루워에 의해 개발된 보다 강력한 형태의 건설적 분석이다.

기본 구성

계산 가능한 분석을 하는 데 인기 있는 모델은 튜링 머신이다. 수학적 구조의 테이프 구성과 해석은 다음과 같이 설명된다.

Type 2 튜링 머신

Type 2 튜링 기계(Type 2 Turing Machine)는 다음과 같은 3개의 테이프가 있는 튜링 기계다. 읽기 전용인 입력 테이프, 쓰기 및 읽기 전용인 작동 테이프, 특히 "애플리케이션 전용"인 출력 테이프.

실수

이 맥락에서, 실수는 임의의 무한한 기호의 시퀀스로 표현된다. 예를 들어 이러한 시퀀스는 실제 숫자의 숫자를 나타낼 수 있다. 그러한 시퀀스는 계산할 필요가 없다. 반면에, 이러한 순서에 따라 작용하는 프로그램들은 합리적인 의미에서 계산될 필요가 있다.

계산 가능한 함수

계산 가능한 기능은 타입 2 튜링 기계의 프로그램으로 표현된다. 입력에 관계 없이 출력 테이프에 기호를 몇 개라도 쓰는 데 유한한 시간이 걸리는 경우 프로그램은 총량(부분함수와는 반대로 총함수라는 의미에서)으로 간주된다. 그 프로그램들은 영원히 실행되어 점점 더 많은 숫자의 결과물을 만들어 낸다.

이름

무한 집합과 관련된 계산가능성에 대한 결과는 종종 이름들을 포함하는데, 이름들은 그러한 집합과 하위 집합의 재귀적 표현 사이의 지도들이다.

토론

유형 1 대 유형 2 계산성의 문제

제1종 연산성은 기계에 대한 입력을 임의의 실수 대신에 계산 가능한 숫자로 제한하는 계산 가능한 분석의 순진한 형태다.

두 모델의 차이는 계산 가능한 숫자에 대해 (총체라는 의미에서) 잘 동작하는 함수가 임의의 실수에 대해 반드시 잘 동작하는 것은 아니라는 사실에 있다. 예를 들어, 총계인 계산 가능한 실제 숫자에 대해 연속적이고 계산 가능한 함수가 있지만, 이 함수는 닫힌 간격을 무한 개방 간격에 매핑한다. 이러한 함수는 극한값 정리를 위반할 수 있기 때문에, 이러한 함수를 부분적인 것으로 만들지 않고서는 분명히 임의의 실제 숫자로 확장할 수 없다. 그러한 종류의 행동은 병리학적으로 간주될 수 있기 때문에, 한 기능이 계산 가능한 것만이 아니라 모든 실제 숫자에 걸쳐 총체적인 경우에만 총체적인 것으로 간주되어야 한다고 주장하는 것은 당연하다.

실현 가능성

튜링 머신을 사용하는 것이 불만족스러운 경우(낮은 수준과 다소 임의적이라는 이유로), 계산 가능한 분석을 건설적인 분석으로 줄일 수 있는 실현가능성 토포스가 있다. 이 건설적인 분석은 Brouwer 학교에서 유효한 모든 것을 포함하며, Bishop 학교만이 아니다.

기본결과

계산 가능한 모든 실제 함수는 연속적이다(Weihrauch 2000, 페이지 6).

실수의 산술 연산은 계산할 수 있다.

평등 관계는 해독할 수 없지만, 불평등한 실수에 대한 보다 큰 술어는 해독할 수 있다.

균일한 표준 연산자도 계산할 수 있다. 이는 리만 통합의 계산 가능성을 시사한다.

Riemann 적분은 계산 가능한 연산자: 즉, 계산 가능한 함수의 적분을 수치적으로 평가하는 알고리즘이 있다.

실제 가치 함수에 대한 분화 연산자는 계산할 수 없지만, 복잡한 함수에 대한 분화 연산자는 계산할 수 있다. 후자의 결과는 Cauchy의 통합 공식과 통합의 계산 가능성에서 나타난다. 이전의 부정적인 결과는 분화(실제 가치 함수의 과대)가 불연속적이라는 사실에서 비롯된다. 이는 실제 분석과 복잡한 분석 사이의 괴리뿐만 아니라, 실제 숫자에 대한 수치적 분화의 난이도를 보여주고 있는데, 이는 복잡한 숫자로 함수를 확장하거나 상징적인 방법을 사용하여 우회되는 경우가 많다.

계산 가능한 숫자라고 불리는 실제 숫자의 하위 집합이 있는데, 위의 결과에 의해 실제 폐쇄된 필드라고 한다.

일반 위상과 연산성 이론의 유사성

$계산{\displaystyle \mathbb{}}$ 가능한 분석의 기본 결과 중 하나는 R ${\$에서 R ${\$까지 계산 가능한 모든 함수가 연속적이라는 것이다(Weihrauch 2000, 페이지 6). 이것을 더 자세히 보면, 위상의 기본 개념과 계산성의 기본 개념 사이에 유사성이 있음을 알 수 있다.

• 계산 가능한 함수는 연속 함수와 유사하다.
• 반간 호환 세트는 오픈 세트와 유사하다.
• 공동 분리 가능한 세트는 닫힌 세트와 유사하다.
• 위상학적 압축성의 계산 가능한 아날로그가 있다. Namely, a subset ${\displaystyle S}$ of ${\displaystyle \mathbb {R} }$ is computably compact if it there is a semi-decision procedure "${\displaystyle \forall _{S}}$" that, given a semidecidable predicate ${\displaystyle P}$ as input, semi-decides whether every point in the set ${\displaystyle S}$ sa$술어{\displaystyle }$ P ${\displaystyle$ P$\}.$
• 위의 계산 가능한 컴팩트 개념은 하이네-보렐 정리의 아날로그를 만족시킨다. 특히 단위 간격${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1]}$은(는) 계산적으로 콤팩트하다.
• 위상에서의 이산 공간은 요소들 간의 동일성이 반결정 가능한 계산가능성의 집합과 유사하다.
• 위상에서의 하우스도르프 공간은 요소들 사이의 불평등이 반결정 가능한 계산가능성의 설정과 유사하다.

그 유추에 따르면 일반적인 위상과 연산성은 거의 서로 거울에 비친 이미지라고 한다. 계산가능성 이론과 일반 위상은 모두 건설적인 논리로 수행할 수 있다는 사실을 이용하여 유추를 설명할 수 있다.

참고 항목

• 스피커 수열

참조

• 올리버 애버스(1980), 계산 가능한 분석, 맥그로우 힐, ISBN0-0700-0079-4.
• Marian Pour-El과 Ian Richards (1989년), 분석 및 물리에서의 연산성, Springer-Verlag.
• Stephen G. Simpson(1999년), 2차 산술의 서브시스템.
• 클라우스 웨이하치(2000), 계산가능 분석, 스프링거, ISBN 3-540-66817-9.

외부 링크

• 분석 네트워크의 연산성과 복잡성