图灵机和可计算性理论

图灵机（Turing machine）是一种理想的计算模型，是一种假想的由纸带、读写头和一定计算规则组成的机器，可以用来模拟任何可以计算的问题。你可以把图灵机理解为一种抽象的、通用的计算机。

如果一个函数可以被图灵机计算并得出答案，这个函数就具有图灵可计算性（Turing-computability）。从现实层面来讲，任何可以在计算机上模拟的问题都是图灵可计算的，只要这个问题可以由计算机程序给出答案而不会陷入死循环。

停机问题（Halting Problem）不是图灵可计算的，它要求计算机判断一个程序在给定的输入下会停机还是会陷入死循环。图灵机和任何计算机都不能解决它。

// 停机问题的伪代码表示
int H(procedure,Input);
int U(P)
{
    while(H(P,P)){}
    return 0;
}

如果一个系统（一系列操作数据的规则）可以模拟图灵机（Turing machine），就说它是图灵完备的（Turing-complete）。简单来说，具有图灵完备性的系统可以识别另一个系统的数据操作规则，图灵完备的计算机或计算机语言可以模拟另一种计算机或计算机语言的行为和用途。

几乎所有编程语言都是图灵完备的，这表示几乎所有编程语言都可以被用来重新编写由另一种编程语言实现的计算机程序，能实现其他语言也能实现的功能。如果一个编程语言能实现条件判断、循环和变量，它基本上就是图灵完备的。
标记语言（数据语言）不是图灵完备的，比如 JSON、XML、HTML 和 Markdown，因为他们只能描述数据而不能描述行为。

如果一个系统是图灵完备的，那它就可以被用来模拟另一个图灵完备的系统。也就是说，这两个系统是图灵等价的。

如果系统 A 可以模拟系统 B，而系统 B 也可以模拟系统 A，那么系统 A 和系统 B 就是图灵等价的。

所有图灵完备的系统都是图灵等价于图灵机的。

2025-06-04