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

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

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

用最简单的术语来说，图灵完备系统可以解决任何可能的计算问题。

关键要求之一是便签大小不受限制，并且可以倒带访问之前对便签的写操作。

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

相反，有些系统通过对无界内存建模并执行任何可能的计算来接近图灵完备性。

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

甚至不受记忆的限制。

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

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

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

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

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

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

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

We call a language Turing-complete if and only if (1) it is decidable by a Turing machine but (2) not by anything less capable than a Turing machine. For instance, the language of palindromes over the alphabet {a, b} is decidable by Turing machines, but also by pushdown automata; so, this language is not Turing-complete. Truly Turing-complete languages - ones that require the full computing power of Turing machines - are pretty rare. Perhaps the language of strings x.y.z where x is a number, y is a Turing-machine and z is an initial tape configuration, and y halts on z in fewer than x! steps - perhaps that qualifies (though it would need to be shown!)

A common imprecise usage confuses Turing-completeness with Turing-equivalence. Turing-equivalence refers to the property of a computational system which can simulate, and which can be simulated by, Turing machines. We might say Java is a Turing-equivalent programming language, for instance, because you can write a Turing-machine simulator in Java, and because you could define a Turing machine that simulates execution of Java programs. According to the Church-Turing thesis, Turing machines can perform any effective computation, so Turing-equivalence means a system is as capable as possible (if the Church-Turing thesis is true!)

图灵等价比真正的图灵完备性更主流;这一点以及“完全”比“等效”短的事实可能解释了为什么“图灵完全”经常被误用为图灵等效，但我离题了。