nlp - 自然语言图灵完备吗？

Question

我很确定人类语言（例如英语）足以模拟图灵机，这将使图灵机完整。然而，这意味着自然语言的表达能力并不比编程语言多或少，这似乎是有问题的。

自然语言图灵完备吗？

Answer 1

首先，“语言 X 图灵完备”只是一个定义明确的问题，给定语言 X 的明确语义。由于自然语言的复杂性以及对上下文和直觉的依赖，几乎不可能为自然语言定义一个问题. 大多数（全部？）自然语言甚至没有明确定义的语法。

除此之外，您的主要困惑是基于这样的假设，即计算模型不可能比图灵机更强大，即能够模拟图灵机，但也可以表达图灵机不能的计算。这不是真的。例如，我们可以用预言机扩展图灵机，我们得到一个比普通图灵机更强大的计算模型。

同样，我们可以定义一种编程语言 MagicLang，它可以做普通编程语言可以做的所有事情，还可以解决停机问题。为这种语言定义语义很容易：只需将我们使用的语言的语义作为基础，并添加一个bool halts(string src, string input)语义为“如果源代码描述的程序src在给定的有限时间后成功终止，则返回 true”的函数输入input“。所以这很容易。实现这种语言是困难的，或者说是不可能的。

现在有人可能会争辩说，自然语言也可以描述停止问题，我们的大脑可以“执行”自然语言，即它可以回答“这个程序是否停止”的问题。因此，如果我们可以制造一台可以完成我们大脑可以做的所有事情的计算机，它也应该能够做到这一点。但问题是我们的大脑无法以 100% 的准确率解决停机问题。我们的大脑甚至无法以 100% 的准确率执行常规程序。请记住，您有多少次在脑海中逐步完成一个程序并得出与现实不同的结果。我们的大脑非常擅长学习、建立直觉联系和应用启发式方法，但这些事情总是伴随着给出错误结果的风险。

那么计算机可以做同样的事情吗？是的，我们可以使用启发式算法和机器学习来解决其他无法解决的问题，并且正常的编程语言可以尝试解决可以用自然语言描述的所有问题（甚至是无法确定的问题）。但就像大脑一样，这些程序有时会给出错误的结果。事实上，它们会更频繁地给出错误结果，因为我们的机器学习算法和启发式算法远不如人脑先进。

Answer 2

如果一种软件语言足够复杂，可以用来定义对自身的任意扩展（例如定义任意新函数），那么它显然是图灵完备的。

使用自然语言，如果有足够的时间，我可以教其他人类术语和概念，以扩展他们的理解力和讨论他们以前无法讨论的任意主题的能力——例如，我可以教他们版权法或天体物理学（如果他们没有'还不知道他们）。因此，虽然这可能更像是一个类比而不是一个确切的身份，但自然语言似乎确实具有类似图灵完备性的属性：它们可以用来定义和传输任意扩展给自己。（诚​​然，并不是每个人都适合学习天体物理学——但是任何非理想化的车床只有有限的内存量，所以总是有可能定义一个它不能运行的程序，因为它没有有足够的内存。）