Le terme “continuité” ont une signification différente en mathématiques et en CS?

Question

Je pose cette question parce que de certains états dans la question "Qu'est-ce que la "continuité" comme un terme de formalisation de l'analyse?" faisant de moi un suspect.

Je suis ingénieur, pas informaticien, donc je n'ai pas la machine de Turing, mais les portes de logique à l'esprit quand je pense à algébrique opérations effectuées avec des appareils.

J'ai lu la réponse à la question "Pourquoi sont calculables fonctions continues?" et bien compris la façon suivante:

Parce que le périphérique d'entrée est de longueur infinie (un nombre décimal avec un nombre infini de chiffres après la virgule), l'appareil (par ex.Machine de Turing ou l'ordinateur) ne peut pas lire l'intégralité du numéro avant d'écrire le $n$-ème chiffre de la production.

Au lieu de cela, l'appareil peut uniquement avoir lu m $(n)$ chiffres de l'entrée lorsqu'il écrit l' $n$-ème chiffre de la production.

Si le premier $n$ les chiffres de la production de certaines fonctions dépendent uniquement de la première m $(n)$ chiffres de l'entrée, la fonction est continue.

Cependant, si je comprends bien l'argumentation correctement, le mot "continu" dans le calcul, la théorie n'est pas identique au mot "continue" en mathématiques:

L'arrondi vers zéro n'aurait besoin que de la lecture de l'entrée jusqu'à ce que le point décimal (donc $m(n)= ext{const.}$);cependant, la fonction mathématique calculée n'est pas "continu", selon la définition mathématique du terme.

Nous avons pu également effectuer un chiffre-sage de l'opération ($m(n)=n$) et l'échange de certains chiffres après la virgule;par exemple, remplacer tous les 4s par 9s et de tous les 9s par 4s.Comme je le comprends, la fonction calculée n'est pas continue sur tout intervalle de $\mathbb{R}$ (toutefois, il serait de droite continue sur $[0,\infty)$ et à gauche en continu sur $(-\infty,0]$).

Et si je n'ai pas fait une erreur conceptuelle et nous utilisons un équilibrée système de numération (comme un Informatique russe dans les années 1960 au lieu du système décimal, un algorithme similaire (par l'échange de 0s et 1s au lieu de 4s et 9s) serait à même de représenter une fonction mathématique qui est même pas directionnelle continue sur n'importe quel intervalle de $\mathbb{R}$.

Questions:

La compilation dépendent du système de numération utilisé (comme l'exemple avec la équilibrée système numéral l'indique) ou est le terme "calculable" même en supposant un certain système de numération utilisé?

L'observation est-elle correcte que le terme "continu" n'ont pas le même sens en mathématiques et CS?

Answer 1

Si nous devions utiliser la virgule expansion pour représenter les nombres réels, votre raisonnement serait de travailler.Mais qui nous donne un très mal comportés notion de compilation:

Proposition:Multiplication par 3 n'est pas calculable par rapport à la représentation décimale.

La preuve:Supposent que l'entrée commence 0.3333333...À un certain point, notre calcul doit commencer à la sortie de quelque chose.Les meilleurs choix sont 0.et 1..Dans le premier cas, nous ont foutu si notre entrée 4 en chiffre suivant nous n'avions pas regardé;dans le deuxième cas, une 2 nous fait mal.Ainsi, nous ne pouvons pas sortie une garantie de préfixe de la solution.

À l'aide d'une base différente donnerait une notion différente de la compilation, mais aucun d'entre eux sont adaptés.Certains des moyens qui conduisent toutes à la même notion exacte de compilation sont:

1. Code un réel $x$ comme une suite de rationnels $(q_n)_{n \in \mathbb{N}}$ tels que $|x - q_n| < 2^{-n}$.
2. Code un réel via un signé chiffres de la représentation, à l'aide $\{-1,0,1\}$.
3. Code un réel $x$ comme une séquence d'intervalles rationnels $(I_n)_{n \in \mathbb{N}}$ avec $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

Lorsque l'on parle de compilation d'une fonction sur le corps des réels, sans préciser de quel type de représentation que nous utilisons, nous entendons l'un de ces (ou un autre équivalent).C'est juste comme nous ne sommes pas toujours à l'aide de la topologie Euclidienne sur le corps des réels si nous le faisons, c'est juste le cas standard.Nous pouvons maintenant affirmer:

Le théorème de:Les fonctions sur les réels qui sont calculables (wrt la représentation standard) par rapport à certaines oracle sont exactement les fonctions continues (par rapport à la topologie Euclidienne).

De retour de l'arrondissement, ce qui montre parfaitement arrondi exact ne peut pas travailler.Cependant, nous pouvons circumvene ce par pas de nous limiter à des fonctions.Par exemple, la tâche suivante est calculable:

Étant donné un nombre réel $x \in [0,1]$, la production ou l'autre $0$ ou $1$.Si $x < 0.501$, puis $0$ est une solution acceptable et si $x > 0.499$, puis $1$ est une solution acceptable.

Si l'entrée de la tâche est au-dessus de $[0.499,0.501]$, puis la réponse que nous obtenons ne dépend pas seulement sur le réel, nous sommes en train de regarder, mais le code pour que le réel que notre algorithme lit.Que peut faire un raisonnement sur des algorithmes un peu plus encombrante, mais on ne peut pas l'éviter.