4、经典与量子计算基础：从图灵机到复杂度理论

经典与量子计算基础：从图灵机到复杂度理论

1. 计算理论基础

计算在数学尤其是数论的发展中一直是重要的驱动力。许多伟大的定理（如素数定理）和猜想（如黎曼假设和BSD猜想）都源于计算实验。计算是计算数论和量子计算数论的核心要素。下面我们将探讨与计算相关的几个关键问题：
- 什么是计算/量子计算？
- 计算机能做什么和不能做什么？
- 量子计算机能做什么和不能做什么？

2. 经典可计算性理论

2.1 图灵机

图灵机的概念和理论由英国逻辑学家和数学家艾伦·图灵在1936年提出。一个标准的多带图灵机 (M) 是一个代数系统，定义如下：
[M = (Q, \Sigma, \Gamma, \delta, q_0, \sqcup, F)]
其中：
1. (Q) 是有限的内部状态集合；
2. (\Sigma) 是有限的输入字母表，且 (\Sigma \subseteq \Gamma \setminus {\sqcup})；
3. (\Gamma) 是有限的磁带字母表；
4. (\delta) 是转移函数：
- 如果 (M) 是确定性图灵机（DTM），则 (\delta: Q \times \Gamma^k \to Q \times \Gamma^k \times {L, R}^k)；
- 如果 (M) 是非确定性图灵机（NDTM），则 (\delta: Q \times \Gamma^k \to 2^{Q \times \Gamma^k \times {L, R}^k})，其中 (L) 和 (R) 分别表示读写头向左或向右移动。当 (k = 1) 时，就是标准