計算中的“神諭”論文

《計算中的“神諭”論文》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、計算中的“神諭”論文摘要：本文通過回顧對計算工具的發(fā)展歷史和人類對計算本質認識的歷史，提出量子計算系統(tǒng)的發(fā)展和成熟，會為最終解開量子世界的“神諭”提供工具和思考方法。并且提出了人類認識未知世界的規(guī)律：“計算工具不斷發(fā)展——整體思維能力的不斷增強——公理系統(tǒng)的不斷擴大——舊的神諭被解決——新的神諭不斷產生”不斷循環(huán)。關鍵詞：計算工具；圖靈模型；量子計算；哥德爾不完備定理；神諭一、引言與計算的產生在人類社會的早期時代，加減乘除的概念就被人們所認識到。隨著人類文明的發(fā)展和技術的進步，對求方程的解，求函數的

2、微分和積分等概念也納入了計算的范疇。伴隨人類生產活動的不斷增加，人們對計算的要求也越來越大，計算工具也再不斷的改進。二、遠古的計算工具人們開始產生計算之日.freelan)在美國《科學》上公布DNA計算機的理論，并成功運用DNA計算機解決了一個有向哈密頓路徑問題7。DNA計算機的提出，產生于這樣一個發(fā)現，即生物與數學的相似性：(1)生物體異常復雜的結構是對由DNA序列表示的初始信息執(zhí)行簡單操作(復制、剪接)的結果；(2)可計算函數f(ω)的結果可以通過在ω上執(zhí)行一系列基本的簡單函數而獲得。阿德勒曼不

3、僅意識到這兩個過程的相似性，而且意識到可以利用生物過程來模擬數學過程。更確切地說是，DNA串可用于表示信息，酶可用于模擬簡單的計算。這是因為：首先，DNA是由稱作核昔酸的一些單元組成，這些核昔酸隨著附在其上的化學組或基的不同而不同。共有四種基：腺嘌呤、鳥嘌呤、胞嘧啶和胸腺嘧啶，分別用A、G、C、T表示。單鏈DNA可以看作是由符號A、G、C、T組成的字符串。從數學上講，這意味著可以用一個含有四個字符的字符集∑=A、G、C、T來為信息編碼(電子計算機僅使用0和1這兩個數字)。其次，DNA序列上的一些簡單

4、操作需要酶的協助，不同的酶發(fā)揮不同的作用。起作用的有四種酶：限制性內切酶，主要功能是切開包含限制性位點的雙鏈DNA；DNA連接酶，它主要是把一個DNA鏈的端點同另一個鏈連接在一起；DNA聚合酶，它的功能包括DNA的復制與促進DNA的合成；外切酶，它可以有選擇地破壞雙鏈或單鏈DNA分子。正是基于這四種酶的協作實現了DNA計算。DNA計算與電子計算機完全不同，它的計算單元是裝在試管培養(yǎng)液中的DNA長鏈。通過控制試管的溫度和向試管中投放反應物，來進行計算。八、量子計算系統(tǒng)量子計算最初思想的提出可以追溯到2

5、0世紀80年代。物理學家費曼RichardP.Feynman曾試圖用傳統(tǒng)的電子計算機模擬量子力學對象的行為。他遇到一個問題11：量子力學系統(tǒng)的行為通常是難以理解同時也是難以求解的。以光的干涉現象為例，在干涉過程中，相互作用的光子每增加一個，有可能發(fā)生的情況就會多出一倍，也就是問題的規(guī)模呈指數級增加。模擬這樣的實驗所需的計算量實在太大了，不過，在費曼眼里，這卻恰恰提供一個契機。因為另一方面，量子力學系統(tǒng)的行為也具有良好的可預測性：在干涉實驗中，只要給定初始條件，就可以推測出屏幕上影子的形狀。費曼推斷認

6、為如果算出干涉實驗中發(fā)生的現象需要大量的計算，那么搭建這樣一個實驗，測量其結果，就恰好相當于完成了一個復雜的計算。因此，只要在計算機運行的過程中，允許它在真實的量子力學對象上完成實驗，并把實驗結果整合到計算中去，就可以獲得遠遠超出傳統(tǒng)計算機的運算速度。在費曼設想的啟發(fā)下，1985年英國牛津大學教授多伊奇DavidDeutsch提出是否可以用物理學定律推導出一種超越傳統(tǒng)的計算概念的方法即推導出更強的丘奇——圖靈論題15。費曼指出使用量子計算機時，不需要考慮計算是如何實現的，即把計算看作由“神諭”來實現

7、的：這類計算在量子計算中被稱為“神諭”（Oracle）。有種種跡象表明：量子計算至少在一些特定的計算領域內確實比傳統(tǒng)計算更強，例如，現代信息安全技術的安全性在很大程度上依賴于把一個大整數（如1024位的十進制數)分解為兩個質數的乘積的難度。這個問題是一個典型的“困難問題”，困難的原因是目前在傳統(tǒng)電子計算機上還沒有找到一種有效的辦法將這種計算快速地進行。目前，就是將全世界的所有大大小小的電子計算機全部利用起來來計算上面的這個1024位整數的質因子分解問題，大約需要28萬年，這已經遠遠超過了人類所能夠等

8、待的時間。而且，分解的難度隨著整數位數的增多指數級增大，也就是說如果要分解2046位的整數，所需要的時間已經遠遠超過宇宙現有的年齡。而利用一臺量子計算機，我們只需要大約40分鐘的時間就可以分解1024位的整數了。更重要的是，量子計算從本質上說是可逆的，朗道證明了可逆計算可以不消耗資源———也就是說，量子計算的運算速度可以不違背熵持續(xù)增加原理而無限增加。從這個例子我們可以直覺地認為量子計算在處理大規(guī)模計算問題時優(yōu)越性是十分明顯的，但目前還沒法用數學證明這一點。九、計算的