图灵完备性

理论

• 百度百科

  百度百科

  在可计算性理论里，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）按照一定的顺序可以计算出结果，被称为图灵完备（turing complete）

  什么是图灵完备性语言？一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。

  一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（if、while、goto语句）以及改变内存数据。 如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。

  图灵不完备的语言常见原因有循环或递归受限(无法写不终止的程序,如 while(true){}; ), 无法实现类似数组或列表这样的数据结构(不能模拟纸带). 这会使能写的程序有限

  图灵完备的意思就是可以做到图灵机所能做到的所有事情，解决所有的可计算问题的逻辑系统、装置或者编程语言就叫做图灵完备。