Czy wszystkie czyste funkcje w programowaniu funkcjonalnym są ciągłe?

Question

Wiem, że zestaw funkcji Haskella jest tylko podzbiorem wszystkich funkcji matematycznych, ponieważ jest to język programowania, więc wszystkie jego funkcje muszą być obliczalne. Ale czy to prawda, że ​​wszystkie funkcje Haskella (i ogólnie funkcje czyste) są z matematycznego punktu widzenia continuous?

Answer 1

Funkcje obliczalne są ciągłe w sensie ciągłości Scotta, o których mowa w drugim akapicie strony Wikipedii, do której jesteś podłączony.

Przykładem funkcji, która jest nie stała jest (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 : _|_ -} = _|_ 

to nie w sposób ciągły, ponieważ

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

jest Supremum sekwencji

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

ale

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

nie supremum sekwencji

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

funkcje obliczalne są ciągłe, ponieważ w skończonym czasie funkcja może kontrolować tylko skończoną ilość jego wejścia. Jeśli więc funkcja obliczeniowa zwróci, powiedzmy, True na określonym wejściu, musi zwrócić True na każdym wejściu w zestawie wejść, które zgadzają się z pierwotnym wejściem w pewnym skończonym zbiorze obserwacji. Każda rosnąca sekwencja, która zbiega się z pierwotnym wejściem, ostatecznie wyląduje i pozostanie w tym zbiorze, więc sekwencja wartości funkcji w tej rosnącej sekwencji będzie zbieżała się z True.

Funkcja ciągła nie musi być obliczalna. Na przykład funkcja zachowywania porządku (tj. f _|_ = _|_ lub f jest stała) funkcja Integer -> Bool jest ciągła, ponieważ Integer jest domeną płaską. Ale oczywiście tylko niezliczona liczba z nich jest obliczalna.