47.随机计算

title: 47. 随机计算 tags: zk computation theory probabilistic turing machine BPP amplification lemma polynomial identity testing WTF zk 教程第 47 讲：随机计算 在本讲中，我们将探讨随机计算，包括概率图灵机和BPP类的概念。所有零知识证明都是概率证明，理解随机计算非常重要。 概率图灵机 概率图灵机（Probabilistic Turing Machine，简称 PTM）是对确定性图灵机的扩展，它引入了随机性。 1.1 定义 概率图灵机是一个七元组 $(Q, \Sigma, \Gamma, \delta, q0, q{accept}, q{reject})$，其中： $Q, \Sigma, \Gamma, q0, q{accept}, q{reject}$ 的定义与确定性图灵机相同 $\delta: P(Q \times \Gamma \times Q \times \Gamma \times \{L,R\})$ 是转移分布函数，给出所有可能转移的概率分布，其...