"Turing Complete"这个表达式的意思是什么?
你能简单地解释一下,不涉及太多理论细节吗?
"Turing Complete"这个表达式的意思是什么?
你能简单地解释一下,不涉及太多理论细节吗?
Turing完备意味着它至少与图灵机一样强大。
我认为这是不正确的,一个系统只有在与图灵机完全相等时才是Turing完备的,即机器执行的每个计算都可以由该系统执行,但该系统执行的每个计算也可以由图灵机执行。
如果一种语言是可由图灵机决定的,但不可由比图灵机更低级别的任何东西决定,则我们称其为图灵完备。例如,字母表{a,b}上的回文语言可以由图灵机和下推自动机决定;因此,这种语言不是图灵完备的。真正的图灵完备语言——需要图灵机的全部计算能力——非常罕见。也许字符串x.y.z的语言就是一个例子,其中x是一个数字,y是一个图灵机,z是一个初始磁带配置,并且y在少于x!步骤中停止——也许这就符合条件(尽管需要证明!)
常见的不精确用法将图灵完备性与图灵等效性混淆。图灵等效性指的是一种计算系统的属性,该系统可以模拟图灵机,并且可以被图灵机模拟。例如,我们可以说Java是一种图灵等效的编程语言,因为您可以在Java中编写图灵机模拟器,并且可以定义一个模拟执行Java程序的图灵机。根据Church-Turing论题,图灵机可以执行任何有效的计算,因此图灵等效性意味着系统具有最大的能力(如果Church-Turing论题成立的话!)
图灵等价是一个更为主流的问题,而不仅仅是真正的图灵完备性;这一点以及“complete”比“equivalent”更短可能解释了为什么“Turing-complete”经常被错误地用来表示图灵等价,但我岔开了话题。关系型数据库能够输入地点和道路的经纬度,并计算它们之间的最短路径吗?答案是否定的。这是一个表明SQL并非图灵完备的问题。
但是C++可以做到,而且可以解决任何问题。因此它是优秀的选择。