計算與計算複雜性

初稿于20060521
計算在本質上是什么？
對這個問題的回答經歷了一個漫長的歷史，直到二十世紀30年代，哥德爾，丘奇，圖靈等大家的工作，才弄清了什么是計算的本質，什么是可計算的，什么是不可計算的等根本性問題。
計算：從一個符號串f變為另一個符號串g,其可以分為兩大類：數值就算和符號計算。但在本质上等价，可以相互转化。
二十世纪四十年代左右，数理逻辑学家们建立了四种计算模型，分别是：一般递归函数，lambda可计算函数，图灵机和波斯特(E.L.Post)系统，从不同的角度探究计算过程或者证明过程，但在本质上却证明是等价的，于是形成了著名的丘奇－图灵论点：凡是可计算的函数都是一般递归函数(图灵机可计算函数)。从而确立了计算与可计算性的数学含义。
ps:似乎后来又有一般递归和尾递归的推论。在这之中，自动机，可计算性和复杂性是连在一起的。在后来的文档中，会涉及到。