Perché le funzioni calcolabili sono continue?

Question

Sto lavorando a scrivere un facile da leggere Documento sulla semantica denotazionale del calcolo Lambda. Per questo introduco CPO, monotonicità e continuità. Un CPO è un set $ M $ Con un ordine parziale $ leq $ e un elemento inferiore $ bot $, richiedendo $ bot $ essere l'elemento più piccolo in $ M $ e l'esistenza del limite superiore ($ bigsqcup $) per ogni catena $ d_0 leq d_1 leq d_2 leq ... $ in $ M $. Una funzione $ f $ tra due CPO $ M $, $ N $ è monotono, se per tutti $ a, b in m $ Di seguito è riportato:

$$ a leq b implica f (a) leq f (b) $$

Una funzione $ f $ tra due CPO $ M $, $ N $ è continuo, se è monotono e per tutte le catene $ d_0 leq d_1 leq d_2 leq dots $ noi abbiamo

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

Voglio dare ai miei lettori una buona intuizione sul significato di queste definizioni. Tuttavia, non ne ho uno che potrei scrivere. A seguito di Glynn Winskel nel suo libro »La semantica formale dei linguaggi di programmazione« (1993), $ a leq b $ deve essere letto come $ a $ approssimarsi $ b $ (pagina 72), significato $ b $ ha almeno quante più informazioni $ a $. Ciò porta alle funzioni monotone che riflettono ulteriori informazioni sull'input in maggiori informazioni sull'output (pagina 122). Questo è in qualche modo comprensibile per me. Tuttavia, la spiegazione della continuità non è chiara per me:

Come vedremo, che le funzioni calcolabili dovrebbero essere continue seguenti dall'idea che l'aspetto di un'unità di informazione nell'output di una funzione calcolabile non dovrebbe dipendere solo dalla presenza di unità di informazione finitamente infinita nell'input.

(Pagina 73)

Questo non è ancora chiaro per me dopo aver letto l'esempio del flusso nella Sezione 8.2 (pagine 121–123) o questo Rispondere.

Quindi la mia ultima domanda è: come convinco i miei lettori che le funzioni calcolabili sono continue? perché è lì No funzione calcolabile che è non continuo?

Sarebbe bello se potessi darmi risposte/esempi che non richiedono la rigorosa introduzione della calcolabilità o della teoria dei punti fissi, dal momento che non voglio concentrarmi su quelle cose. Inoltre sarebbe bello se non fosse necessario conoscere in anticipo il calcolo Lambda e la sua semantica di denotazionale, perché voglio (e devo) introdurre monotonicità e continuità davanti a loro.

EDIT: di calcolabile Intendo Turing-computabile. Per favore, correggimi se fraintende la definizione di Winskels Computable a pagina 337, poiché non è esplicitamente definita come Turing-computabile ma in modo equivalente (almeno ai miei occhi).

Inoltre voglio segnalarne un altro fonte Ho scoperto che cerca di spiegare il mio problema. Ma ancora non capisco il suo esempio, dal momento che è sostanzialmente lo stesso dell'esempio di streaming di Winskel.

EDIT 2: sarebbe anche un buon inizio per aiutarmi a capire la questione per dimostrare che ogni funzione calcolabile è monotone, cioè non esiste una funzione calcolabile non monotono.