41.计算理论入门

title: 41. 计算理论入门 tags: zk computation theory finite autonoma language regular expression WTF zk 教程第 41 讲：计算理论入门 零知识证明（ZKP）是计算理论（Theory of Computation）的重要应用之一，用于验证一个命题的真实性而不泄露任何附加信息。在深入研究零知识证明之前，了解计算理论的基础是至关重要的。这一讲，我们将介绍计算理论的基本概念，包括有限自动机（Finite Automata）和正则语言。 计算理论概览 计算理论是研究计算过程及其能力的理论分支，主要分为两部分：可计算性理论（Computability Theory）和复杂性理论（Complexity Theory）。 1.1 可计算性理论 定义：研究哪些问题可以通过计算解决以及如何解决。 活跃时间：1930-1960。 图灵机是可计算性理论的基础模型，用于定义算法和计算。 1.2 复杂性理论 定义：研究解决问题所需的资源（时间、空间等）及其优化。 活跃时间：1960至今。 主要研究对象是复杂性类：如P类、NP...