什么是图灵完成？

Question

"图灵完成"的含义是什么意思？

你可以给出一个简单的解释,而不会涉及太多的理论细节吗？

Answer 1

这是最简短的解释:

图灵完成系统是指一个系统,在该系统中可以编写一个可以找到答案的程序(尽管不保证运行时或内存).

因此,如果有人说"我的新东西是图灵完全",这意味着原则上(虽然通常不在实践中)它可以用来解决任何计算问题.

有时这是一个笑话......一个人在vi中写了一个图灵机模拟器,所以可以说vi是世界上唯一需要的计算引擎.

Answer 2

这是最简单的解释

Alan Turing创建了一个可以接受程序并运行该程序并显示一些结果的机器.但他必须为不同的程序创建不同的机器.所以他创造了"通用图灵机",可以接受任何程序并运行它.

编程语言与那些机器类似(尽管是虚拟的).他们接受程序并运行它们.现在,编程语言被称为"图灵完成",如果它可以运行任何程序(不论语言)图灵机可以运行给定足够的时间和内存.

例如:假设有一个程序需要10个数字并添加它们.图灵机可以轻松运行该程序.但是现在想象由于某种原因你的编程语言不能做同样的添加,那么它的图灵机不完整.另一方面,如果它可以运行任何程序,如通用图灵机可以运行,那么它的图灵完成.

大多数现代编程语言,如Java,JavaScript,Perl等都是完整的,因为它们都实现了运行程序所需的所有功能,如加法,乘法,if-else条件,返回语句,存储/检索/擦除数据的方法等等.

更新:您可以在我的博客文章中了解更多信息:"JavaScript是图灵完成" - 解释

Answer 3

来自维基百科:

以阿兰图灵命名的图灵完整性非常重要,因为迄今为止先进的计算设备的每一个合理的设计都可以通过一个通用的图灵机来模仿 - 这一观察被称为Church-Turing论文.因此,可以充当通用图灵机的机器原则上可以执行任何其他可编程计算机能够进行的任何计算.但是,这与为机器编写程序所需的工作量,机器执行计算所需的时间或机器可能具有的与计算无关的任何能力无关.

虽然真正图灵完备的机器很可能在物理上是不可能的,因为它们需要无限存储,但图灵完整性通常松散地归因于物理机器或编程语言,如果它们具有无限存储,它们将是通用的.在这个意义上,所有现代计算机都是图灵完整的.

我不知道你怎么能比那更具技术性,除非说"图灵完整的手段'能够在给定足够的时间和空间的情况下回答可计算的问题".

Answer 4

非正式定义

图灵完整语言是可以执行任何计算的语言.该教会图灵论文指出,任何可执行的计算可以通过图灵机来完成.一个图灵机是无限的随机存取存储器和有限的"程序"指示何时应该读,写,和整个内存,当它应该有一个确定的结果终止移动,它下一步应该做什么的机器.图灵机的输入在启动前放入其内存中.

可以使语言无法完成的事情

图灵机能够根据它认为在内存中的决策 - "语言",只有支持+,-,*,和/对整数不是图灵完成,因为它不能使基于其输入一个选择,但图灵机多能.

图灵机可以永远运行 - 如果我们使用Java,Javascript或Python并删除了执行任何类型的循环,GOTO或函数调用的能力,它就不会是图灵完成的,因为它不能执行任意计算永远不会结束.Coq是一个定理证明器,无法表达不终止的程序,所以它不是图灵完整的.

图灵机可以使用无限内存 - 一种与Java完全相同的语言,但是一旦使用超过4千兆字节的内存就会终止,因为图灵机可以使用无限内存.这就是我们实际上无法构建图灵机的原因,但Java仍然是图灵完整语言,因为Java 语言没有限制它阻止它使用无限内存.这是正则表达式不是图灵完成的一个原因.

图灵机具有随机存取存储器 - 一种只允许你处理存储器push并对pop堆栈进行操作的语言不会图灵完成.如果我有一个"语言",上面写着一串一次,并且只能通过推并从堆栈弹出使用内存,它可以告诉我,是否每个(字符串中有自己的)以后通过它看到的时候推(它时看到弹出).但是,它不能告诉我,如果每一个(都有自己)后来和每一个[都有自己]以后(注意,([)]符合此标准,但([]]没有).图灵机可以使用它的随机存取存储器跟踪()的和[]的分别,但这种语言只有一个堆栈不能.

图灵机可以模拟任何其他图灵机 - 图灵机,当给定适当的'程序'时,可以采用另一个图灵机的'程序'并在任意输入上模拟它.如果你有一种被禁止实现Python解释器的语言,它就不会是图灵完成的.

图灵完整语言的例子

如果您的语言具有无限的随机存取存储器,条件执行和某种形式的重复执行,则可能是图灵完成的.有更多的奇特系统仍然可以实现图灵机所能实现的一切,这也使得图灵完成了:

• 没有类型的lambda演算
• 康威的生活游戏
• C++模板
• 序言

Answer 5

从根本上说,图灵完整性是一个简洁的要求,无限的递归.

甚至没有记忆的限制.

我独立地想到了这一点,但这里有一些关于断言的讨论.我对LSP的定义提供了更多的上下文.

这里的其他答案并没有直接定义图灵完备性的基本要素.

Answer 6

图灵完成意味着它至少与图灵机一样强大.这意味着图灵机可以计算的任何东西都可以通过图灵完备系统来计算.

还没有人发现一个比图灵机更强大的系统.所以,暂时说系统是Turing Complete就像说系统和任何已知的计算系统一样强大(参见Church-Turing Thesis).

Answer 7

简而言之,图灵完备系统可以解决任何可能的计算问题.

其中一个关键要求是暂存区域大小无限制,可以倒带以访问先前写入暂存器的内容.

因此在实践中没有系统是图灵完备的.

相反,一些系统通过对无界内存进行建模并执行可适合系统内存的任何可能计算来近似图灵完备性.

Answer 8

Brasilford 教授在此视频中解释的内容的超级简短摘要。

\n

图灵完备 \xe2\x89\x85 可以做图灵机可以做的任何事情。

\n

\n

1. 它具有条件分支（即“if 语句”）。此外，还意味着“转到”，从而允许循环。

   \n
\n

2. 它获得程序需要的任意数量的内存（例如足够长的磁带）。

   \n
\n

\n