什么是图灵完备

图灵完备（Turing Completeness） 是计算机科学中的一个概念，用来描述一个系统（通常是编程语言或计算模型）是否具备和图灵机（Turing Machine）等价的计算能力。

一、通俗解释

如果一个编程语言或系统能够模拟任意图灵机的行为，也就是说它可以计算任何可计算的函数（只要有足够的内存和时间），那么它就是图灵完备的。

换句话说：

只要一门语言能实现 “条件判断（if）”、循环（while/for/递归），那么它基本上就能做到图灵完备。

二、图灵完备的常见条件

一个系统通常需要具备以下三种能力才是图灵完备的：

1. 条件分支（如：if、switch）

2. 循环或递归（如：for、while、函数调用）

3. 无限存储空间（理论上，内存不受限制）

三、常见例子

图灵完备的系统：

• 大多数通用编程语言（如：C、Java、Python、Go、PHP、JavaScript）

• 汇编语言

• 有些看似不正规的语言如：

  • Brainfuck（极简编程语言）

  • λ-演算（Lambda calculus）

非图灵完备的系统：

• SQL（标准 SQL 没有循环或递归）

• HTML（标记语言，不具备运算能力）

• CSS（样式语言，同样不具备控制流程）

不过，一些非图灵完备的系统可以通过扩展或结合其他语言（如 PL/SQL）变成图灵完备。

四、为什么图灵完备重要？

• 编程语言设计：说明一种语言理论上能完成任意计算任务。

• 安全与限制：某些 DSL（领域特定语言）故意设计成非图灵完备，防止用户写出无限循环或不受控的代码（如配置语言、模板语言等）。

• 计算理论：是判断问题是否“可计算”的重要基础。

本作品采用《CC 协议》，转载必须注明作者和本文链接