图灵完备是什么意思?

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


当前回答

图灵完备意味着它至少和图灵机一样强大。这意味着任何可以被图灵机计算的东西都可以被图灵完备系统计算出来。

目前还没有人发现比图灵机更强大的系统。因此,就目前而言,说一个系统是图灵完备的,就等于说这个系统与任何已知的计算系统一样强大(参见丘奇-图灵论文)。

其他回答

以下是最简单的解释:

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

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

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

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

关系数据库能否输入地点和道路的经度和纬度,并计算它们之间的最短路径?这是一个表明SQL不是图灵完备的问题。

但是c++可以做到,并且可以解决任何问题。事实就是这样。

Brasilford教授在这段视频中对所解释的内容进行了超级简短的总结。

图灵完备≅做图灵机能做的任何事情。

它具有条件分支(即。“如果声明”)。此外,暗示“go to”,因此允许循环。 它获得程序所需的任意数量的内存(例如足够长的磁带)。

从维基百科:

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.

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