计算
概述
计算是从输入数据经过一系列确定性步骤产生输出结果的过程，是数学和计算机科学的核心概念，由图灵等人的工作给出了精确的数学定义。
关键内容
- 基本定义：
- 从输入到输出的确定性转换过程
- 按照预定义规则执行的机械步骤序列
-
在有限时间内完成的有目的操作
-
理论发展：
- 1936年前后，为解决希尔伯特判定问题，多种计算模型被提出
- 图灵机给出了最直观的计算概念定义
-
证明了所有合理计算模型的等价性
-
计算模型：
- 图灵机：最经典的抽象计算模型
- λ演算：基于函数变换的计算模型
-
递归函数：基于数学函数的计算模型
-
计算类别：
- 可计算问题：存在算法解决的问题
- 不可计算问题：不存在算法解决的问题（如停机问题）
- 易计算问题：可在多项式时间内解决的问题（P类）
-
难计算问题：目前未找到多项式时间算法的问题（NP类）
-
实际载体：
- 机械计算器
- 电子计算机
- 量子计算机
-
生物计算系统
-
哲学意义：
- 揭示了数学推理的边界
- 定义了算法和自动化的能力范围
- 提出人类智能与机械智能的对比
来源
- 01-turing-on-computable-numbers — 计算概念的精确化
- 论可计算数及其在判定问题上的应用 — 理论基础