自然语言图灵完备吗？
Is natural language Turing complete?
我很确定人类语言（例如英语）的功能足以模拟图灵机，这将使它成为图灵完备的。然而，这意味着自然语言的表达能力不比编程语言高或低，这似乎值得怀疑。
自然语言图灵完备吗？
首先，"Is language X Turing complete" 只是一个定义明确的问题，因为语言 X 具有定义明确的语义。由于自然语言的复杂性和对语言的依赖，几乎不可能为自然语言定义一个问题上下文和直觉。大多数（全部？）自然语言甚至没有明确定义的语法。
除此之外，您的主要困惑是基于这样的假设：计算模型不可能比图灵机更强大，即能够模拟图灵机，但也可以表达计算图灵机不行。这不是真的。例如，我们可以用预言机扩展图灵机，我们得到一个比普通图灵机更强大的计算模型。
以同样的方式，我们可以定义一种编程语言 MagicLang，它可以完成普通编程语言可以做的所有事情，还可以解决停机问题。为这种语言定义语义很容易：只需以我们使用的语言的语义为基础，添加一个具有语义 "returns true if the program described by the source code src successfully terminates after a finite amount of time when given the input input" 的函数 bool halts(string src, string input)。所以这很容易。实现这种语言是困难的，或者说是不可能的。
现在有人可能会争辩说，自然语言也可以描述停机问题，我们的大脑可以 "execute" 自然语言，即它可以回答问题 "does this program halt"。因此，如果我们可以制造一台可以完成我们大脑所能做的一切的计算机，那么它也应该能够做到这一点。但问题是我们的大脑无法 100% 准确地解决停机问题。我们的大脑甚至无法 100% 准确地执行常规程序。请记住，您有多少次在脑海中逐步执行某个程序并得出与现实不同的结果。我们的大脑非常擅长学习、建立直觉联系和应用启发式方法，但这些事情总是伴随着给出错误结果的风险。
那么计算机可以做同样的事情吗？是的，我们可以使用启发式和机器学习来解决其他无法解决的问题，并且普通的编程语言可以尝试解决所有可以用自然语言描述的问题（甚至是不可判定的问题）。但就像大脑一样，这些程序有时会给出错误的结果。事实上，它们会更频繁地给出错误结果，因为我们的机器学习算法和启发式算法远不如人脑先进。
如果一种软件语言足够复杂，可以用来定义任意扩展自身（例如定义任意新功能），那么它显然是 Turing-complete。
如果有足够的时间，我可以使用自然语言教授其他人类术语和概念，以扩展他们的理解力和讨论他们以前无法讨论的任意主题的能力——我可以教他们版权法或天体物理学，因为示例（如果他们还不知道）。因此，虽然这可能更像是一个类比而不是一个确切的身份，但似乎确实存在 Turing-completeness-like 属性 自然语言：它们可用于定义和传输任意扩展到自己. （不可否认，并不是每个人都适合学习天体物理学——但是任何 non-idealized 车床只有有限的内存，所以总是可以定义一个程序，它不能 运行 因为它没有足够的内存。）
我很确定人类语言（例如英语）的功能足以模拟图灵机，这将使它成为图灵完备的。然而，这意味着自然语言的表达能力不比编程语言高或低，这似乎值得怀疑。
自然语言图灵完备吗？
首先，"Is language X Turing complete" 只是一个定义明确的问题，因为语言 X 具有定义明确的语义。由于自然语言的复杂性和对语言的依赖，几乎不可能为自然语言定义一个问题上下文和直觉。大多数（全部？）自然语言甚至没有明确定义的语法。
除此之外，您的主要困惑是基于这样的假设：计算模型不可能比图灵机更强大，即能够模拟图灵机，但也可以表达计算图灵机不行。这不是真的。例如，我们可以用预言机扩展图灵机，我们得到一个比普通图灵机更强大的计算模型。
以同样的方式，我们可以定义一种编程语言 MagicLang，它可以完成普通编程语言可以做的所有事情，还可以解决停机问题。为这种语言定义语义很容易：只需以我们使用的语言的语义为基础，添加一个具有语义 "returns true if the program described by the source code src successfully terminates after a finite amount of time when given the input input" 的函数 bool halts(string src, string input)。所以这很容易。实现这种语言是困难的，或者说是不可能的。
现在有人可能会争辩说，自然语言也可以描述停机问题，我们的大脑可以 "execute" 自然语言，即它可以回答问题 "does this program halt"。因此，如果我们可以制造一台可以完成我们大脑所能做的一切的计算机，那么它也应该能够做到这一点。但问题是我们的大脑无法 100% 准确地解决停机问题。我们的大脑甚至无法 100% 准确地执行常规程序。请记住，您有多少次在脑海中逐步执行某个程序并得出与现实不同的结果。我们的大脑非常擅长学习、建立直觉联系和应用启发式方法，但这些事情总是伴随着给出错误结果的风险。
那么计算机可以做同样的事情吗？是的，我们可以使用启发式和机器学习来解决其他无法解决的问题，并且普通的编程语言可以尝试解决所有可以用自然语言描述的问题（甚至是不可判定的问题）。但就像大脑一样，这些程序有时会给出错误的结果。事实上，它们会更频繁地给出错误结果，因为我们的机器学习算法和启发式算法远不如人脑先进。
如果一种软件语言足够复杂，可以用来定义任意扩展自身（例如定义任意新功能），那么它显然是 Turing-complete。
如果有足够的时间，我可以使用自然语言教授其他人类术语和概念，以扩展他们的理解力和讨论他们以前无法讨论的任意主题的能力——我可以教他们版权法或天体物理学，因为示例（如果他们还不知道）。因此，虽然这可能更像是一个类比而不是一个确切的身份，但似乎确实存在 Turing-completeness-like 属性 自然语言：它们可用于定义和传输任意扩展到自己. （不可否认，并不是每个人都适合学习天体物理学——但是任何 non-idealized 车床只有有限的内存，所以总是可以定义一个程序，它不能 运行 因为它没有足够的内存。）