資源描述：
《計算中的“神諭”論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、計算中的“神諭”論文摘要：本文通過回顧對計算工具的發(fā)展歷史和人類對計算本質(zhì)認識的歷史，提出量子計算系統(tǒng)的發(fā)展和成熟，會為最終解開量子世界的“神諭”提供工具和思考方法。并且提出了人類認識未知世界的規(guī)律：“計算工具不斷發(fā)展——整體思維能力的不斷增強——公理系統(tǒng)的不斷擴大——舊的神諭被解決——新的神諭不斷產(chǎn)生”不斷循環(huán)。關(guān)鍵詞：計算工具；圖靈模型；量子計算；哥德爾不完備定理；神諭一、引言與計算的產(chǎn)生在人類社會的早期時代，加減乘除的概念就被人們所認識到。隨著人類文明的發(fā)展和技術(shù)的進步，對求方程的解，求函數(shù)的
2、微分和積分等概念也納入了計算的范疇。伴隨人類生產(chǎn)活動的不斷增加，人們對計算的要求也越來越大，計算工具也再不斷的改進。二、遠古的計算工具人們開始產(chǎn)生計算之日.freelan)在美國《科學》上公布DNA計算機的理論，并成功運用DNA計算機解決了一個有向哈密頓路徑問題7。DNA計算機的提出，產(chǎn)生于這樣一個發(fā)現(xiàn)，即生物與數(shù)學的相似性：(1)生物體異常復雜的結(jié)構(gòu)是對由DNA序列表示的初始信息執(zhí)行簡單操作(復制、剪接)的結(jié)果；(2)可計算函數(shù)f(ω)的結(jié)果可以通過在ω上執(zhí)行一系列基本的簡單函數(shù)而獲得。阿德勒曼不
3、僅意識到這兩個過程的相似性，而且意識到可以利用生物過程來模擬數(shù)學過程。更確切地說是，DNA串可用于表示信息，酶可用于模擬簡單的計算。這是因為：首先，DNA是由稱作核昔酸的一些單元組成，這些核昔酸隨著附在其上的化學組或基的不同而不同。共有四種基：腺嘌呤、鳥嘌呤、胞嘧啶和胸腺嘧啶，分別用A、G、C、T表示。單鏈DNA可以看作是由符號A、G、C、T組成的字符串。從數(shù)學上講，這意味著可以用一個含有四個字符的字符集∑=A、G、C、T來為信息編碼(電子計算機僅使用0和1這兩個數(shù)字)。其次，DNA序列上的一些簡單
4、操作需要酶的協(xié)助，不同的酶發(fā)揮不同的作用。起作用的有四種酶：限制性內(nèi)切酶，主要功能是切開包含限制性位點的雙鏈DNA；DNA連接酶，它主要是把一個DNA鏈的端點同另一個鏈連接在一起；DNA聚合酶，它的功能包括DNA的復制與促進DNA的合成；外切酶，它可以有選擇地破壞雙鏈或單鏈DNA分子。正是基于這四種酶的協(xié)作實現(xiàn)了DNA計算。DNA計算與電子計算機完全不同，它的計算單元是裝在試管培養(yǎng)液中的DNA長鏈。通過控制試管的溫度和向試管中投放反應物，來進行計算。八、量子計算系統(tǒng)量子計算最初思想的提出可以追溯到2
5、0世紀80年代。物理學家費曼RichardP.Feynman曾試圖用傳統(tǒng)的電子計算機模擬量子力學對象的行為。他遇到一個問題11：量子力學系統(tǒng)的行為通常是難以理解同時也是難以求解的。以光的干涉現(xiàn)象為例，在干涉過程中，相互作用的光子每增加一個，有可能發(fā)生的情況就會多出一倍，也就是問題的規(guī)模呈指數(shù)級增加。模擬這樣的實驗所需的計算量實在太大了，不過，在費曼眼里，這卻恰恰提供一個契機。因為另一方面，量子力學系統(tǒng)的行為也具有良好的可預測性：在干涉實驗中，只要給定初始條件，就可以推測出屏幕上影子的形狀。費曼推斷認
6、為如果算出干涉實驗中發(fā)生的現(xiàn)象需要大量的計算，那么搭建這樣一個實驗，測量其結(jié)果，就恰好相當于完成了一個復雜的計算。因此，只要在計算機運行的過程中，允許它在真實的量子力學對象上完成實驗，并把實驗結(jié)果整合到計算中去，就可以獲得遠遠超出傳統(tǒng)計算機的運算速度。在費曼設想的啟發(fā)下，1985年英國牛津大學教授多伊奇DavidDeutsch提出是否可以用物理學定律推導出一種超越傳統(tǒng)的計算概念的方法即推導出更強的丘奇——圖靈論題15。費曼指出使用量子計算機時，不需要考慮計算是如何實現(xiàn)的，即把計算看作由“神諭”來實現(xiàn)
7、的：這類計算在量子計算中被稱為“神諭”（Oracle）。有種種跡象表明：量子計算至少在一些特定的計算領(lǐng)域內(nèi)確實比傳統(tǒng)計算更強，例如，現(xiàn)代信息安全技術(shù)的安全性在很大程度上依賴于把一個大整數(shù)（如1024位的十進制數(shù))分解為兩個質(zhì)數(shù)的乘積的難度。這個問題是一個典型的“困難問題”，困難的原因是目前在傳統(tǒng)電子計算機上還沒有找到一種有效的辦法將這種計算快速地進行。目前，就是將全世界的所有大大小小的電子計算機全部利用起來來計算上面的這個1024位整數(shù)的質(zhì)因子分解問題，大約需要28萬年，這已經(jīng)遠遠超過了人類所能夠等
8、待的時間。而且，分解的難度隨著整數(shù)位數(shù)的增多指數(shù)級增大，也就是說如果要分解2046位的整數(shù)，所需要的時間已經(jīng)遠遠超過宇宙現(xiàn)有的年齡。而利用一臺量子計算機，我們只需要大約40分鐘的時間就可以分解1024位的整數(shù)了。更重要的是，量子計算從本質(zhì)上說是可逆的，朗道證明了可逆計算可以不消耗資源———也就是說，量子計算的運算速度可以不違背熵持續(xù)增加原理而無限增加。從這個例子我們可以直覺地認為量子計算在處理大規(guī)模計算問題時優(yōu)越性是十分明顯的，但目前還沒法用數(shù)學證明這一點。九、計算的
