图灵完备与图灵等效

如今的所有通用计算机都是图灵机的一种实现，两者的能力是等价的。当一个计算系统可以模拟任意图灵机时，我们称其是图灵完备的（Turing complete）；当一个图灵完备的系统可以被图灵机模拟时，我们称其是图灵等效的（Turing equivalent）。图灵完备和图灵等效成为衡量计算机和编程语言能力的基础指标。如今几乎所有的编程语言都是图灵完备的，这意味着它们可以相互取代，一种语言能写出的程序用另一种也照样可以实现。