概率图灵机
此条目不符合维基百科的质量标准，需要完全重写。 (2024年10月16日) |
在计算复杂性理论内，概率图灵机（probabilistic Turing machine）是一个非决定型图灵机，在每个转折点根据某种概率分布随机选择某种可行的转变（transition）。
在转变是均匀分布概率的例子里面，我们可以定义为决定型图灵机多了一个新增的"写入"指令，这一个写入指令的值是所有图灵机能用符号的均匀分布概率选择出的符号（概括地说，这个写入指令以相同的概率在纸带上面写入“1”或者“0”。）另一个常用的定义是多了一条随机纸带，上面布满了许多随机比特值的确定型图灵机。
所以，概率图灵机可以有随机的结果（与决定型图灵机不同）；给定一个输入和一个状态机，机器运作的时间长度会不同，或者甚至不会停止；甚至，这机器可能在这一次操作下回传为接受，下一次相同的输入值却回传为拒绝。
因此如何去理解被一个概率图灵机接受字符串的方式可以用许多不同的方式定义。同时也有许多种因为我们对accept方式的不同，而产生了许多的多项式时间随机复杂度类，包含了RP、Co-RP、BPP和ZPP。如果我们把多项式时间的限制改成对数空间的限制，我们则有了跟上面雷同的RL、Co-RL、BPL和ZPL。如果我们同时限制两者，则有了RLP、Co-RLP、BPLP和ZPLP。
随机计算对于定义大多数的交互式证明系统也是极为重要的，因为验证者机器需要随机性来避免被全能的证明者预测或者欺骗。例如说，IP这个类别等同 PSPACE，但是如果把验证者的随机性移除，我们就只有NP，一个一般而言相信（但尚未证明）是比起IP要小的复杂度类。
复杂度理论的其中一个重点问题是：是否随机性增加了算法的能力？换句话说，是否有问题在多项式时间内可以以概率图灵机解决但是不能以决定型图灵机解决？或者是决定型图灵机可以在至多只有多项式时间的变慢之下，完全的模仿随机图灵机的动作？现今的研究者大部分相信后者，这同时可以推出P = BPP。相同问题的对数空间（log space）版本（是否L = BPLP?）则比起多项式时间版本更被广泛相信为真。另外，随机性给予交互式证明系统的力量，以及对困难问题所能建立更简单的算法的特质，例如多项式时间内的素性测试（primality testing）和对数空间的图相连测试（graph connectedness testing），又隐含着随机性是有可能增加计算能力的。
量子计算机则是另一种先天就具有着概率性质的计算模式。