(3)密码中的因难问题 >什么是计算 >计算模型 >可计算问题 >计算复杂度 21
21 （3）密码中的困难问题 ➢什么是计算 ➢计算模型 ➢可计算问题 ➢计算复杂度
随着计算机日益广泛而深刻的运用，计算这个原本专 门的数学概念已经泛化到了人类的整个知识领域，并 上升为一种极为普适的科学概念和哲学概念，成为人 们认识事物、研究问题的一种新视角、新观念和新方 法。 ·在大众的意识里，计算首先指的就是数的加减乘 除，其次则为方程的求解、函数的微分积分等； 懂的多一点的人知道，计算在本质上还包括定理 的证明推导。可以说 ,“计算”是一个无人不知 元人不晓的数学概念， 事实上，直到1930年代，由于哥德尔K.Godel, 1906-1978)、丘奇(A.Church,1903-1995)、图灵 (A.M.TU-ing,1912-1954)等数学家的工作，人们才 弄清楚什么是计算的本质，以及什么是可计算的、什 么是不可计算的等根本性问题。 22
22 随着计算机日益广泛而深刻的运用，计算这个原本专 门的数学概念已经泛化到了人类的整个知识领域，并 上升为一种极为普适的科学概念和哲学概念，成为人 们认识事物、研究问题的一种新视角、新观念和新方 法。 • 在大众的意识里，计算首先指的就是数的加减乘 除，其次则为方程的求解、函数的微分积分等； •懂的多一点的人知道，计算在本质上还包括定理 的证明推导。可以说，“计算”是一个无人不知 元人不晓的数学概念， 事实上，直到1930年代，由于哥德尔K.Godel， 1906-1978）、丘奇(A.Church，1903-1995)、图灵 (A.M.TUI-ing，1912-1954)等数学家的工作，人们才 弄清楚什么是计算的本质，以及什么是可计算的、什 么是不可计算的等根本性问题
所谓计算，就是从一个符号串变换成另一个符号串g。 例如： >从符号串2+3变换成5就是一个加法计算；如果符号 串f是x2,而符号串g是2x,从到g的计算就是微分。 >定理证明也是如此，令表示一组公理和推导规则， 令g是一个定理，那么从到g的一系列变换就是定理g 的证明。 >文字翻译也是计算，如代表一个英文句子，而 g为含意相同的中文句子，那么从到g就是把英文翻译 成中文。 这些变换间有什么共同点？为什么把它们都叫做计 算？因为它们都是丛己知符号（串）开始，一步一步地改 变符号（串），经过有限步骤，最后得到一个满足预先规 定的符号（串）的变换过程。 23
23 所谓计算，就是从一个符号串f变换成另一个符号串g。 例如: ➢从符号串2+3变换成5就是一个加法计算;如果符号 串f是x 2 ，而符号串g是2x,从f到g的计算就是微分。 ➢定理证明也是如此，令f表示一组公理和推导规则， 令g是一个定理,那么从f到g的一系列变换就是定理g 的证明。 ➢文字翻译也是计算，如f代表一个英文句子，而 g为含意相同的中文句子，那么从f到g就是把英文翻译 成中文。 这些变换间有什么共同点？为什么把它们都叫做计 算？因为它们都是从己知符号(串)开始，一步一步地改 变符号(串)，经过有限步骤，最后得到一个满足预先规 定的符号(串)的变换过程
计算主要有两大类： 数值计算：包括实数和函数的加减乘除、 幕运算、开方运算、方程的求解等。 ■符号推导：包括代数与各种函数的恒等式、 不等式的证明，几何命题的证明等。 无论是数值计算还是符号推导，它们在本质 上是等价的、一致的，即二者是密切关联的， 可以相互转化，具有共同的计算本质。随着数 学的不断发展，还可能出现新的计算类型。 24
24 计算主要有两大类： ◼数值计算：包括实数和函数的加减乘除、 幕运算、开方运算、方程的求解等。 ◼符号推导：包括代数与各种函数的恒等式、 不等式的证明,几何命题的证明等。 无论是数值计算还是符号推导,它们在本质 上是等价的、一致的，即二者是密切关联的， 可以相互转化，具有共同的计算本质。随着数 学的不断发展,还可能出现新的计算类型
计算的实质 : ■为了回答究竟什么是计算、什么是可计算 性等问题，人们采取的是建立计算模型的方 法。 ■四种模型：一般递归函数、入可计算函数、 图灵机和波斯特(E.L.Post,1897-1954)系统 在此基础上，最终形成了如今著名的丘奇： 图灵论点：凡是可计算的函数都是一般递归函 数（或是图灵机可计算函数等）。这就确立了计算 与可计算性的数学含义。 25
25 计算的实质： ◼为了回答究竟什么是计算、什么是可计算 性等问题，人们采取的是建立计算模型的方 法。 ◼四种模型：一般递归函数、λ可计算函数、 图灵机和波斯特(E.L.Post，1897-1954)系统。 在此基础上，最终形成了如今著名的丘奇- 图灵论点：凡是可计算的函数都是一般递归函 数(或是图灵机可计算函数等)。这就确立了计算 与可计算性的数学含义