7

Haskell 関数のセットはすべての数学関数のサブセットにすぎないことを知っています。これはプログラミング言語であるため、その関数はすべて計算可能でなければなりません。しかし、数学的な観点から、すべての Haskell 関数 (および一般的な純粋関数) は連続的であるというのは本当ですか?

4

1 に答える 1

19

計算可能な関数は、リンク先のウィキペディア ページの 2 番目の段落で言及されているスコット連続性の意味で連続的です。

連続でない関数の例は (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 : _|_ -} = _|_

連続ではないので

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

シーケンスの最高値です

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

しかし

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

はシーケンスの最高値ではありません

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

計算可能な関数は連続的です。基本的に、関数は有限の時間内に有限の量の入力しか検査できないためです。したがって、計算可能な関数が特定の入力に対して返される場合、特定の有限コレクションの観測に対する元の入力と一致する入力セット内のすべての入力に対してTrue返される必要があります。True元の入力に収束する増加数列は、最終的にはこのセット内に収まって留まるため、この増加数列の関数の値の列は に収束しTrueます。

連続関数は必ずしも計算可能ではありません。たとえば、は平坦な領域であるため、順序を維持する (つまりf _|_ = _|_、 またはfが定数である) 関数Integer -> Boolは連続です。Integerしかしもちろん、それらの多くは計算可能です。

于 2016-01-05T17:47:14.210 に答える