Tutte le funzioni pure nella programmazione funzionale sono continue?

Question

So che l'insieme delle funzioni Haskell è solo un sottoinsieme di tutte le funzioni matematiche, perché è un linguaggio di programmazione, quindi tutte le sue funzioni devono essere calcolabili. Ma è vero che tutte le funzioni di Haskell (e pure le funzioni in generale) sono continuous, da un punto di vista matematico?

Answer 1

Le funzioni computabili sono continue nel senso della continuità di Scott, menzionate nel secondo paragrafo della pagina di Wikipedia a cui ti sei collegato.

Un esempio di una funzione che è non continuo è (pseudo-Haskell)

isInfinite :: [a] -> Bool 
isInfinite xs 
    | {- xs is an infinite list x0 : x1 : x2 : ... -}  = True 
    | {- xs is a finite list x0 : x1 : x2 : ... : xn : [] -} = False 
    | {- xs is a list with diverging spine 
          x0 : x1 : x2 : ... : xn : _|_ -} = _|_ 

non riesce a essere continuo perché

() :() :() : ... 

è l'estremo superiore della sequenza

_|_ 
() : _|_ 
() :() : _|_ 
... 

ma

True = isInfinite (() :() :() : ...) 

non è l'estremo superiore della sequenza

_|_ = isInfinite (_|_) 
_|_ = isInfinite (() : _|_) 
_|_ = isInfinite (() :() : _|_) 
... 

Funzioni calcolabili sono continue, essenzialmente perché in un tempo finito una funzione può ispezionare solo una quantità finita di suo ingresso. Quindi, se una funzione calcolabile restituisce, per esempio, True su un particolare input, deve restituire True su ogni input nel set di input che concordano con l'input originale su una determinata raccolta di osservazioni finite. Qualsiasi sequenza crescente che converge all'ingresso originale finirà per atterrare e rimanere all'interno di questo set, quindi la sequenza di valori della funzione su questa sequenza crescente convergerà a True.

Una funzione continua non è necessariamente calcolabile. Ad esempio qualsiasi conservazione degli ordini (ad esempio f _|_ = _|_ o f è costante) la funzione Integer -> Bool è continua, poiché Integer è un dominio piatto. Ma ovviamente solo molti di loro sono calcolabili.