sam*_*ara 11 theory computability turing-machines turing-complete
你如何争论lambda演算是图灵完整的事实(以最简单的方式)？
最直接的方法是在Lambda微积分中实现图灵机.这很容易,因为Lambda微积分实际上是一种高级编程语言.这种方法的优点是不需要任何其他数学依赖,因此它应该提供最简单的方法来提供你的论证.
就数学证明而言,最短的方法是实现另一个已经显示为图灵完备的范例,如μ递归函数.这些已经递归定义,因此它们在Lambda演算中的表达比图灵机本身稍微优雅一些.