"연속성"이라는 용어는 수학과 CS에서 다른 의미를 갖나요?

Question

질문의 일부 진술 때문에 이 질문을 합니다. "계산 분석에서 '연속성'이라는 용어는 무엇입니까?" 나를 의심하게 만든다.

저는 컴퓨터 과학자가 아니라 엔지니어이기 때문에 장치를 사용하여 수행되는 대수 연산을 생각할 때 튜링 기계가 아니라 논리 게이트를 염두에 두고 있습니다.

질문에 대한 답변을 읽었습니다. "계산 가능한 함수는 왜 연속인가요?" 그리고 그것을 다음과 같이 이해했습니다.

장치의 입력은 무한 길이(소수점 이하 자릿수가 무한한 십진수)이기 때문에 장치(예:튜링 기계나 컴퓨터)는 숫자를 쓰기 전에 전체 숫자를 읽을 수 없습니다. $n$- 출력의 번째 자리.

대신, 장치는 읽기만 할 수 있습니다. $m(n)$ 쓸 때 입력의 숫자 $n$- 출력의 번째 자리.

첫 번째 경우 $n$ 일부 함수의 출력 숫자는 첫 번째 숫자에만 의존합니다. $m(n)$ 입력의 자릿수에 따라 기능은 연속됩니다.

그러나 이 주장을 올바르게 이해한다면 계산 이론의 "연속"이라는 단어는 수학의 "연속"이라는 단어와 동일하지 않습니다.

0으로 반올림하려면 소수점까지만 입력을 읽어야 합니다. $m(n)= ext{const.}$);그러나 계산되는 수학 함수는 해당 용어의 수학적 정의에 따라 "연속"되지 않습니다.

숫자별 연산을 수행할 수도 있습니다($m(n)=n$) 소수점 이하의 특정 숫자를 교환합니다.예를 들어 모두 교체 4에 의해 9그리고 모두 9에 의해 4에스.내가 이해하는 한, 계산되는 함수는 어떤 간격에서도 연속적이지 않습니다. $\mathbb{R}$ (단, 오른쪽 연속은 $[0,\infty)$ 그리고 왼쪽 연속 $(-\infty,0]$).

그리고 제가 개념적 실수를 하지 않고 다음을 사용한다면 균형 잡힌 숫자 시스템 (같은 1960년대 러시아 컴퓨터) 십진법 대신 유사한 알고리즘(교환 0모래 1대신에 4모래 9s) 심지어는 수학 함수를 나타낼 수도 있습니다. 방향성 연속성도 아니고 어떤 간격으로든 $\mathbb{R}$.

질문:

계산 가능성은 사용되는 숫자 체계에 따라 달라지나요(균형 숫자 체계의 예에서 알 수 있듯이), 아니면 특정 숫자 체계가 사용된다고 가정하더라도 "계산 가능"이라는 용어가 사용됩니까?

"연속"이라는 용어가 수학과 CS에서 동일한 의미를 갖지 않는다는 관찰이 정확합니까?

Answer 1

실수를 표현하기 위해 소수 확장을 사용한다면 당신의 추론은 효과가 있을 것입니다.그러나 이는 우리에게 계산 가능성에 대한 매우 잘못된 개념을 제공합니다.

제안:3을 곱하는 것은 소수 표현을 기준으로 계산할 수 없습니다.

증거:입력이 0.3333333...으로 시작한다고 가정합니다.어느 시점에서 우리의 계산은 무언가를 출력하기 시작해야 합니다.최선의 선택은 0입니다.그리고 1..첫 번째 경우, 우리가 보지 않은 입력의 다음 숫자가 4라면 우리는 실수를 저지른 것입니다.두 번째 경우에는 2가 잘못되었습니다.따라서 우리는 보장된 해의 접두어를 출력할 수 없습니다.

다른 기준을 사용하면 계산 가능성에 대한 다른 개념이 생성되지만 그 중 어느 것도 적합하지 않습니다.모두 동일한 좋은 계산 가능성 개념을 산출하는 몇 가지 방법은 다음과 같습니다.

1. 실제 코딩하기 $x$ 일련의 합리성으로서 $(q_n)_{n \in \mathbb{N}}$ 그렇게 $ | x -q_n | <2^{-n} $.
2. 다음을 사용하여 부호 있는 숫자 표현을 통해 실수를 코딩합니다. $\{-1,0,1\}$.
3. 실제 코딩하기 $x$ 일련의 유리수 간격으로 $(I_n)_{n \in \mathbb{N}}$ ~와 함께 $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

우리가 사용하는 표현의 종류를 지정하지 않고 실수에 대한 함수의 계산 가능성에 관해 말할 때, 우리는 이들 중 하나(또는 다른 동등한 표현)를 의미합니다.이것은 우리가 실제로 그렇게 한다고 해서 항상 유클리드 토폴로지를 사용하는 것을 지적하지 않는 것과 같습니다. 그것은 단지 표준 사례입니다.이제 다음과 같이 말할 수 있습니다.

정리:일부 오라클과 관련하여 계산 가능한(표준 표현으로) 실수의 함수는 정확히 연속 함수(유클리드 토폴로지로)입니다.

반올림으로 돌아가면 완벽하게 정확한 반올림이 작동하지 않음을 보여줍니다.그러나 우리는 기능에 제한을 두지 않음으로써 이를 피할 수 있습니다.예를 들어 다음 작업을 계산할 수 있습니다.

실수가 주어지면 $x\in [0,1]$, 출력 중 하나 $0$ 또는 $1$.만약에 $x < 0.501$, 그 다음에 $0$ 허용 가능한 솔루션이고, $x > 0.499$, 그 다음에 $1$ 허용되는 솔루션입니다.

위 작업에 대한 입력이 다음에서 나온 경우 $[0.499,0.501]$, 그러면 우리가 얻는 대답은 우리가 보고 있는 실수뿐만 아니라 알고리즘이 읽는 실수에 대한 특정 코드에 따라 달라집니다.이는 알고리즘에 대한 추론을 약간 더 번거롭게 만들 수 있지만 실제로는 이를 피할 수 없습니다.