380
《偉大的計算原理》一信息的轉換
本節書摘來華章計算機《偉大的計算原理》一書中的第3章 ，［美］彼得 J. 丹寧（Peter J. Denning）
克雷格 H. 馬特爾（Craig H. Martell）著 羅英偉 高良才 張 偉 熊瑞勤 譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
信息的轉換
一個單純的通信係統隻是簡單地將信息從一處傳輸到另一處，但是計算機會做更多的工作，即轉換信息。轉換就帶來了更多可能，其中最顯著的產品就是新信息的出現。簡單的轉換包括將一個數平方、計算π至指定小數位數、對一列數字按照升序排列，每一次轉換都是將一種信息模式作為輸入，並創建一種信息模式作為輸出。
因為二進製模式可以被解析為數，所以一次轉換在數學上看來就像是一個輸入數到輸出數的映射函數。能夠被機器計算的函數被稱為可計算函數。圖靈和他同時代的人們用這個概念來定義計算。圖靈表示一個簡單的抽象計算機——圖靈機，足以實現任何可計算的函數（Turing 1937）。圖靈機遵循一個非常簡單的指令程序來實現這些轉換。因為每一條指令顯然可以被機器實現，那麼計算機轉換二進製的時候並不考慮它們的含義。這類似於香農所強調的，信道可以被設計得完全可靠並且不考慮傳輸信息的含義。
當我們稍微深入了解機器如何轉換輸入時，就會發現程序設計的一個重要方麵，稱之為含義保留（meaning-preserving）。設想兩個數a和b相加，兩個數相加意味著什麼呢？這意味著我們要遵循一係列加法算法的步驟。這個步驟包括連續對a和b的兩個對應的數字位相加，然後將其進位結果傳遞到更高位。我們對於屬於｛0，1，2，…，9｝中的數字對有明確的加法規則，並且會產生進位0或者1。當為這個算法設計程序時，我們需要注意讓每條指令都能夠產生正確的加法結果。如果成功了，我們可以相信機器能夠正確做出兩個數的加法。若失敗了，我們會說機器壞了。
換句話說，設計過程本身就是將我們腦中的加法過程轉換為機器執行加法的指令模式，加法的含義就存在於機器和其算法的設計之中。
這對於任何其他的可計算函數也是適用的。我們把大腦中想法的具體含義轉換成可計算的函數，將它輸出到程序中，從而控製機器實現這個想法。這個過程也就是將具有我們想法含義的函數轉變為對機器的設計。
從這個角度看，機器和通信係統不考慮二進製數據含義進行信息處理的概念有些站不住腳。算法和機器被工程師和程序員植入了含義，我們設計機器從而使得每個計算步驟和輸出都是我們想要的含義，假設輸入也具有我們想要的含義。仔細精確的設計就是為了不用擔心機器曲解我們想要表達的含義。
計算機將計算函數和信道結合，一個信道將輸入送到執行計算函數的機器，另一個信道將輸出送到目的地。這種情況下信道和計算機似乎隻完成了運輸和操作信息位的工作。然而從人類的角度來看，計算帶來了新的信息，無論計算機輸出比輸入更多還是更少的信息。例如，前文提到的一個計算π的函數，在輸入一個三位數“900”時能生成900位的π的值，輸出擴展了300倍的信息量。一個排序函數的輸出和輸入具有同樣的位數，但是具有不同的順序。一個平均函數能夠計算出少量的數字來代表大量數據的平均值。
數字表示和機器操作都依賴於物理過程，每個機器操作都需要花費少量的時間和功耗。有些我們希望計算的函數需要花費太多的步驟以至於在有生之年無法等到機器返回結果。計算所需的物理處理嚴重限製了我們能夠計算的內容。
計算的邏輯也會帶來限製，其中最有名的就是我們想計算但無法計算的函數。圖靈在1936年提到了停機問題——不存在一個程序，可以檢查任何程序並且判斷其在給定輸入上是否包含無限循環。一個現在的實例是惡意軟件檢測，即不存在一個程序能夠檢測任意給定程序是否嵌入了惡意軟件檢測程序。我們在第6章檢驗計算的物理和邏輯局限性的時候，還會再回到這個話題。
即使當我們將注意力限製在可以計算並且很快返回有用結果的函數，也可以發現一些有趣的問題。當一個函數在計算我們沒有見過的數據位時，這些數據位是新的信息嗎（見圖3.6）？或者它們隻是現有信息的結果？DNA包含信息嗎？很多生物學家認為包含。若DNA是一種信息，那它的信息源和接收端又是什麼呢？如果對DNA解碼，我們能得到什麼信息呢？解碼的DNA可以用來尋找治愈遺傳疾病的治療方案，也可以識別犯罪現場的行為人。將DNA與數據庫匹配僅僅揭示了現有的信息還是生成了新的信息呢？經典的信息論無法回答這樣的問題。
圖3.6 哈勃太空望遠鏡的集光傳感器陣列編碼TB級數據並傳輸到地球，這些數據再被處理成為圖像。計算理論將這個圖像處理過程描述為方程Y = F（X），其中輸入數據X在函數計算後產生輸出圖像Y。這個機器實現的功能（將信號發給它，它又生成信號）不依賴於望遠鏡傳輸的信息的含義，然而人類看到Y輸出的是一張美麗的圖片——船底座星雲的實際展示（圖片來源：NASA）
最後更新：2017-06-26 12:31:42