plá*_*omo 3 theory nlp programming-languages turing-complete
我很确定一种人类语言(例如英语)足以模拟图灵机,这将使图灵完整.然而,这意味着自然语言与编程语言相比没有或多或少表达,这似乎是有问题的.
图灵的自然语言是否完整？
首先,"语言X图灵完成"只是一个定义明确的问题,因为语言X的定义语义很明确.由于自然语言的复杂性和依赖于语境和直觉,几乎不可能为自然语言定义一个语法. .大多数(全部？)自然语言甚至没有明确定义的语法.
除此之外,您的主要困惑是基于这样的假设:计算模型不可能比图灵机严格地更强大,即能够模拟图灵机,而且还表示图灵机不能的计算.这不是真的.例如,我们可以使用oracles扩展图灵机,我们得到的计算模型比纯图灵机更强大.
同样,我们可以定义一种编程语言MagicLang,它可以完成普通编程语言可以做的所有事情,并解决暂停问题.为这样的语言定义语义很简单:只需将我们使用的语言的语义作为基础,并添加bool halts(string src, string input)具有语义的函数"如果源代码描述的程序src在给定的有限时间后成功终止,则返回true 输入input".这很容易.实施这种语言有什么困难,或者说是不可能的.
现在有人可能会争辩说,自然语言也可以描述停止问题,我们的大脑可以"执行"自然语言,即它可以回答"这个程序是否停止"的问题.因此,如果我们能够构建一台可以完成我们大脑所能做的一切的计算机,它也应该能够做到这一点.但问题是我们的大脑无法100%准确地解决停止问题.我们的大脑甚至无法以100%的准确度执行常规程序.只要记住你经常在脑海中完成一个程序,并得出与现实不同的结果.我们的大脑非常善于学习,建立直观的联系并应用启发式方法,但这些东西总是带来给出错误结果的风险.
那么计算机可以做同样的事情吗？是的,我们可以使用启发式和机器学习来解决其他无法解决的问题,并且正常的编程语言可以尝试解决可以用自然语言描述的每个问题(甚至是不可判断的问题).但就像大脑一样,这些程序有时会产生错误的结果.事实上,他们会更频繁地给出错误的结果,因为我们的机器学习算法和启发式算法并不像人类大脑那样先进.