Pourquoi les fonctions calculables sont-elles continues?

Question

Je travaille sur l'écriture d'un facile à lire Document sur la sémantique dénotationnelle du calcul Lambda. Pour cela, j'introduis les CPO, la monotonie et la continuité. Un CPO est un ensemble $ M $ avec un ordre partiel $ leq $ et un élément inférieur $ bot $, exigeant $ bot $ être le plus petit élément de $ M $ et l'existence de la limite supérieure la moindre ($ bigsqcup $) pour chaque chaîne $ d_0 leq d_1 leq d_2 leq ... $ dans $ M $. Une fonction $ f $ Entre deux CPO $ M $, $ N $ est monotone, si pour tous $ a, b in m $ Ce qui suit est soutenu:

$$ a leq b implique f (a) leq f (b) $$

Une fonction $ f $ Entre deux CPO $ M $, $ N $ est continu, s'il est monotone et pour toutes les chaînes $ d_0 leq d_1 leq d_2 leq dots $ Nous avons

$$ f ( bigsqcup_ {i in mathbb {n}} d_i) = bigsqcup_ {i in mathbb {n}} f (d_i). $$

Je veux donner à mes lecteurs une bonne intuition sur le sens de ces définitions. Cependant, je n'en ai pas un que je pourrais écrire. Suivre Glynn Winskel dans son livre »La sémantique formelle des langages de programmation« (1993), $ a leq b $ doit être lu comme $ a $ se rapprocher $ b $ (page 72), signifiant $ b $ a au moins autant d'informations que $ a $. Cela conduit à des fonctions monotones reflétant plus d'informations sur l'entrée dans plus d'informations sur la sortie (page 122). C'est quelque peu compréhensible pour moi. Cependant, l'explication de la continuité n'est pas claire pour moi:

Comme nous le verrons, que les fonctions calculables devraient être continues découlent de l'idée que l'apparition d'une unité d'information dans la sortie d'une fonction calculable ne devrait dépendre que de la présence de nombreuses unités d'informations dans l'entrée.

(page 73)

Cela ne m'est pas encore clair après avoir lu l'exemple de flux dans la section 8.2 (pages 121–123), ou cette réponse.

Donc, ma dernière question est: comment convaincre mes lecteurs que les fonctions calculables sont continues? pourquoi y a-t-il non fonction calculable qui est ne pas continu?

Ce serait bien si vous pouvez me donner des réponses / exemples qui ne nécessitent pas l'introduction rigoureuse de la calculabilité ou de la théorie du point de fix, car je ne veux pas me concentrer sur ces choses. Il serait également formidable s'il n'est pas nécessaire de connaître le calcul Lambda et sa sémantique dénotationnelle à l'avance, car je veux (et dois) introduire la monotonie et la continuité avant eux.

Édité par calculable Je veux dire Turing-Computable. Veuillez me corriger si je mal compris la définition de Winskels de Computable à la page 337, car elle n'est pas explicitement définie comme Turing-informable mais d'une manière équivalente (au moins à mes yeux).

Aussi je veux en souligner un autre la source J'ai trouvé qui essaie d'expliquer mon problème. Mais je ne comprends toujours pas son exemple, car il est fondamentalement le même que l'exemple de flux de Winskel.

Edit 2: Ce serait également un bon début pour m'aider à comprendre la question pour montrer que chaque fonction calculable est monotone, c'est-à-dire qu'il n'y a pas de fonction non calotone calculable.