这一部分只针对懂计算机编程的工程狮和程序猿看。
图灵完备需要自动机的知识。人们很好奇需要什么样的机器才能表达出某种语言。
大致可以分为有限状态自动机，下推自动机和图灵机那么几档。前者所能表达的语言是后者的真子集。
有限状态自动机只能表达正则语言。下退自动机能够表达上下文无关语言。而图灵机的语言是递归可枚举语言。不过也有语言不是图灵机表达得了的，比如对角语言。
图灵机可以对应到一个字符串，并被别的图灵机模拟。能够模拟图灵机，则称之为图灵完备，当然，图灵机可以模拟有限状态自动机和下推自动机。
我们的电脑便是一台通用图灵机。这又涉及到生活中的问题到语言的一个转换。
P和NP分别是确定型图灵机和非确定型图灵机在多项式的推演步骤下，所能表达的语言集合。
这两类图灵机所能表达的语言集合是一样的。就是多项式推演步骤这个条件一加，就未解之谜了。
可判定性问题，许多问题还真不是图灵机能解决的，比如：图灵机不能表达的语言。著名的问题有图灵机停机问题。
P与NP其实都是可判定问题，他们其实都是指多项式时间内可判定，只是需要动用非确定型图灵机。
判定图灵完备的方法就是看该编程语言能否模拟出图灵机。
图灵不完备的语言常见原因有循环或递归受限，比如：无法写不终止的程序，无法实现类似数组或列表这样的数据结构，使能写的程序有限。
图灵完备可能带来坏处， 如C++模板语言是在类型检查时执行，如果编译器不检查，我们完全可以写出使得C++编译器陷入死循环的程序。
图灵不完备也不是没有意义，有些场景我们需要限制语言本身，比如：限制循环和递归，可以保证该编程语言能写的程序一定是终止的。
（文章原标题：图灵完备—《区块链思维》第36块 作者：袁晔 来源：简书）
免责声明：本网站内容主要来自原创、合作伙伴供稿和第三方自媒体作者投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。任何单位或个人认为本网站中的网页或链接内容可能涉嫌侵犯其知识产权或存在不实内容时，应及时向本网站提出书面权利通知或不实情况说明，并提供身份证明、权属证明及详细侵权或不实情况证明。本网站在收到上述法律文件后，将会依法尽快联系相关文章源头核实，沟通删除相关内容或断开相关链接。
