什麼是計算的本質，它與編程語言的關係？

01-13

上次在知乎看到了關於數學本質的問題http://www.zhihu.com/question/19925292，上面
陳浩大牛的回答讓我有種茅塞頓開的感覺。最近在鑽研編程語言的時候看到了很多關於計算本質的描述,自己有了一點想法，望大家指正：
1.所謂計算，它也是構建在一套公理體系上的，並且在此基礎上不斷向上演化。比如我們日常的四則運算，我的猜測是它的公理體系則是由三大類組成，一類是數字，一類是基本運算符，一類是它們組合方式。下面是我的理解。
a.數字是我們定義的一個描述數據的集合。
b.運算符是我們用來描述一個計算過程的最小單位，它不能再被拆分。這裡我的感覺是好像建立起了一種從輸入數據(即被運算符操作的數字)到輸出數據(即計算結果數字)的映射。即在這個地方我們定義了1+1=2,2+1=3.....這些最基本的元運算，他們沒有為什麼，因為我們規定映射就是這樣。所以運算符應該是一個映射過程的符號表示。

c.組合方式應該是計算向上演化的規則，由此我們可以得到非常複雜的表達式，即如何由最基礎的元運算按照一系列規則組成複合運算，也可逆向分解。比如(1+1)+1+1*5=8等不是元運算，而是複合運算，我們可以根據組合方式的規則將它劃分成為最基礎的元運算 ，然後求出最後的結果。
這是我對於數學上的一點思考，我數學不好，還希望大家見諒，多多指教。關於這個思考中，我對於組合方式的理解還是有些模糊，大家是否能夠指出四則運算當中我們規定的組合方式到底有哪些呢？
2.如果我們站在計算機學科的角度來說，所謂的計算的本質，也許就是一個解釋器，我們將數據放入其中，這個數據就是代碼。計算過程就是解釋器的運行過程，最後我們會得到一個結果。不同的解釋器對應著不同的計算模型，那麼抽象而言，計算即解釋器。
比如我們常說的符號計算和數值計算，其實就是指我們輸入的數據是數值或是符號，然後各自對應一個自己的解釋器，得出各自需要的結果。它們是不同的計算模型，但是它們都是計算。
綜上所述，我的感覺是計算的本質是一個黑箱，我們把數據放入黑箱，黑箱按照人們規定的過程一步一步(即元運算)執行下去，然後得出結果。
而編程語言和計算的關係在於，編程語言可以去描述指導這個黑箱的運行過程，好的編程語言還能夠給我們提供一種搭建「良好黑箱」的框架，編程語言是黑箱過程的具體展現。
上面就是我的一些yy，還希望大家給出自己獨特的見解。由於自己剛處於學習開始階段，所以錯誤一定很多，還希望大家們多多指教，感激不盡！

計算就是通過演化產生新的信息，其實我們的宇宙也可以看成一個計算模型

編程語言只是演化規則的描述系統而已

在計算這個問題上有兩種範式，一種是計算理論的研究，側重於從數學角度證明表達能力和正確性，比較典型的圖靈機、lambda演算、pi演算這些都屬於這個範疇。另一種是計算模型的研究，側重於對真實系統的建模和刻畫，比如馮諾伊曼模型、BSP模型、LogP模型等等。編程語言的切入點不同，同時可能會是兩種範式之一或混合，比如 Lisp 更側重於前者，C 更注重後者，而更多的語言都在尋求某種折衷。

題主可以看一看皮亞諾的自然數公理體系，最好結合著lambda演算一起看，很簡單普適的模型，可以從這個角度去看計算。

另，在這個公理體系的基礎上1+1=2,1+2=3是可以被證明的，皮亞諾給出了詳細證明，邱奇數可以看作是在lambda演算的基礎上建立起來的一個具體實現。

計算到底是什麼，目前沒有準確說法，人們連數學是什麼也還有爭論。就計算來講，從圖靈機和lambda運算元看過去，就已經是兩個世界了，更何況完備的計算模型遠不止這兩個。

尚無定論。粗淺地說，計算是對信息的處理。但信息的本質是什麼？信息熵和熱力學熵的關係。這些人類的認識都尚淺。

1. 計算的本質

可以先看下維基百科上對計算的介紹：

A calculation is a deliberate process that transforms one or more inputs into one or more results, with variable change.

引用：Calculation - Wikipedia

Computation is any type of calculation[1][2] that follows a well-defined model understood and expressed as, for example, an algorithm.

引用：Computation - Wikipedia

計算是基於給定的基本規則進行演化的過程。計算其實是在探索事物之間的等價關係，或者說同一性。

看西方哲學史的時候，會發現哲學家們相信紛繁複雜的世界存在某種本原，比如德謨克利特認為世界由原子組成，比如柏拉圖認為世界是由理念創造，比如萊布尼茨認為邏輯是世界的本原。計算既是對這種本原如何演繹成紛繁世界的過程的描述。

2. 計算與編程語言的關係

計算與編程語言的關係可以從兩個方面探討。其一為計算理論，即關於計算能做什麼、如何進行計算的研究。其二為計算的物理實現。

關於計算理論可以參考維基百科的描述。推薦看下《計算理論導論》。

計算理論（英語：Theory of computation）是數學的一個領域，和計算機有密切關係。其中的理論是現代密碼協議、計算機設計和許多應用領域的基礎。該領域主要關心三個方面的問題：
採用什麼計算模型（即形式語言、自動機）

解決哪些是能計算的、哪些是不能計算的（即可計算性理論）
要用多少時間、要用多少存儲（即計算複雜性理論）
計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入通過演算法來獲取一個問題的答案（Computation），因此，計算理論屬於計算機科學和數學。計算理論早於現代計算機發明前的20世紀便開始了。

引用：https://zh.wikipedia.org/wiki/計算理論

關於計算的物理實現，也可以看看看維基百科怎麼說的

A computation can be seen as a purely physical phenomenon occurring inside a closed physical system called a computer. Examples of such physical systems include digital computers, mechanical computers, quantum computers, DNA computers, molecular computers, microfluidics-based computers, analog computers or wetware computers. This point of view is the one adopted by the branch of theoretical physics called the physics of computation as well as the field of natural computing.

引用：Theory of computation

編程語言可以理解為一套符號系統，用於描述計算模型。理論上，依照λ-calculus這樣的計算模型設計符號就可以進行完備的計算了。但是，我們現在的大多數計算機都是基於馮若依曼模型，考慮到計算能力的限制，編程語言會做一些折衷，從而更充分的利用計算資源。

理解一門編程語言可以先從他的語義開始，語義體現了編程語言中包含的計算模型。

既然是問本質，那一定是與具體形式無關更為抽象的東西

計算是對指定集合的元素執行定義好的規則

計算本質上是一種變換。

這種變換的方法稱為演算法。

lambda 演算算嗎？

計算不是應用數學的一部分嗎？