是否存在可计算但不可curcurable的函数?



对不起,如果我有点迷路了。我最近开始学习不同的编程语言范式,我发现所有的文本都假定用编程语言编写的所有函数都是可弯曲的。我还没有看到任何证明,在寻找了一段时间后,我发现了关于笛卡尔闭范畴的信息。我的数学知识很有限,所以我不知道这是否适用于,所有可以用图灵机完成的事情。我的猜测是,这样的东西是被证明的(或者可能是显而易见的,我的知识太有限)。提前谢谢你。

我试着在谷歌上找到一些答案,但是我运气不好。

没有上下文很难回答这个问题。套用意味着一个接受一对参数的函数等价于一个有一个参数的函数,它返回第二个参数的函数。因此,很明显,在函数不是一等公民的编程语言中,柯里化是没有意义的,因为您不能返回函数。另一方面,在函数式语言中,curry从一开始就是内置的。在lambda演算中,所有东西都是函数,对本身被定义为返回函数的函数。

在柯里化函数和非柯里化函数之间存在同构关系。例如在Haskell中通过

curry :: ((a, b) -> c) -> a -> b -> c
curry f x y =  f (x, y)
uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p =  f (fst p) (snd p)

,

curry . uncurry = uncurry . curry = id

函数的所有属性都通过同构传递。特别是,如果函数f是(不可)计算的,那么curry f也是(不可)计算的,反之亦然。

注意,一种特定的编程语言是否能够表达柯里化的思想是另一个问题。例如,在纯lambda演算中,只有柯里化函数,没有非柯里化函数的语法。不支持高阶函数的语言(例如C语言)使得编写柯里化函数变得困难(如果不是不可能的话)。

最新更新