任何算法谜题都能以纯粹的功能方式实现吗?

Church-Turing Thesis ,

能 用函数式语言表达并不意味着它不会非常尴尬。

好吧,所以丘奇和图灵认为 可能的 但我们实际上是如何做到的 做 什么?

• 每个可变变量都成为函数参数

有时结果是一团糟,但结果往往出乎意料地优雅。唯一真正的诀窍不是传递永远不会改变的论点,而是让它们在外部环境中绑定。

这将影响性能的主要地方是使用可更新数组的算法。命令式实现可以在O(1)时间内更新数组元素,而纯函数式实现的最佳实现是O(log N)(使用排序树)。

请注意,函数式语言通常有一些方法可以使用具有O(1)访问时间的可更新数组(例如,Haskell通过其状态转换器monad提供了这种方法)。然而,这可以说是一种命令式编程方法。..这没什么错;毕竟,你想为特定的工作使用最好的工具。

然而,O(log N)增量数组更新的函数式风格并不都是坏的,因为函数式算法似乎很适合并行化。

太长,无法作为评论发布 @SteveB's answer .

函数式编程和命令式编程具有同等的能力:无论一个人能做什么,另一个人也能做 精确地 递归函数理论和微积分所表达的。

任何

虽然我完全同意引用丘奇-图灵论题的答案,但这实际上引出了一个有趣的问题。如果我有一个并行计算问题(这不是严格数学意义上的算法),比如多个生产者/消费者队列或几台机器之间的某种网络协议,图灵机能充分建模吗?它可以被模拟,但如果我们模拟它,我们就失去了在问题中具有并行性的目的(因为这样我们可以在图灵机上找到更简单的算法)。那么,如果我们不失去问题固有的并行性(以及我们对它感兴趣的原因),我们就不能消除状态的概念呢?

我记得在某个地方读到,当以纯粹的功能方式解决时,有些问题会变得更加困难,但我似乎找不到参考。

从更主观的角度来看,声称所有图灵完备语言都是等价的,这只在狭义的数学意义上是正确的。 Paul Graham 探讨该问题 Beating the Averages 在“模糊悖论”一节中

图灵完备性等形式化结果可能被证明是正确的,但它们不一定有用。这 travelling salesman problem 可能是NP完全的,但推销员一直在旅行。他们似乎不觉得有必要遵循“最优”路径,因此该定理无关紧要。