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

Question

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

自然语言图灵完备吗？

Answer 1

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

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

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

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

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