图灵完备是什么意思?

你能不能给出一个简单的解释,而不是过多的理论细节?


当前回答

在大多数程序员熟悉的实际语言术语中,检测图灵完整性的通常方法是该语言是否允许或允许模拟嵌套的无界while语句(与具有固定上界的pascal风格for语句相反)。

其他回答

从维基百科:

Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other programmable computer is capable of. However, this has nothing to do with the effort required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities the machine may possess that are unrelated to computation. While truly Turing-complete machines are very likely physically impossible, as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage. All modern computers are Turing-complete in this sense.

我不知道你怎么能比这更非技术,除了说“图灵完备意味着‘能够在足够的时间和空间内回答可计算的问题’”。

从根本上讲,图灵完备性是一个简洁的要求,即无界递归。

甚至不受记忆的限制。

我是独立思考的,但这里有一些关于这个论断的讨论。我对LSP的定义提供了更多的上下文。

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

这是最简单的解释

艾伦·图灵创造了一台机器,它可以接收程序,运行程序,并显示结果。但是他必须为不同的程序创造不同的机器。所以他发明了“通用图灵机”,可以接收并运行任何程序。

编程语言类似于这些机器(尽管是虚拟的)。他们获取程序并运行它们。现在,一种编程语言被称为“图灵完备”,如果它可以运行图灵机在足够的时间和内存下可以运行的任何程序(无论哪种语言)。

例如:假设有一个程序需要10个数字并将它们相加。图灵机可以很容易地运行这个程序。但是现在想象一下,由于某种原因,您的编程语言不能执行相同的加法。这将使它成为“图灵不完整”(可以这么说)。另一方面,如果它能运行通用图灵机能运行的任何程序,那么它就是图灵完备的。

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

更新:你可以在我的博客文章中了解更多:“JavaScript是图灵完备的”-已解释

正如韦伦·弗林所说:

图灵完备意味着它至少和图灵机一样强大。

我认为这是不正确的,如果一个系统和图灵机一样强大,那么它就是图灵完备的,即机器所做的每一个计算都可以由系统完成,而且系统所做的每一个计算都可以由图灵机完成。

以下是最简单的解释:

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

所以,如果有人说“我的新东西是图灵完备的”,这意味着在原则上(尽管通常不是在实践中)它可以用来解决任何计算问题。

有时候这是个玩笑……有人用vi写了一个图灵机模拟器,所以可以说vi是世界上唯一需要的计算引擎。