第四十二章 DNA計(jì)算機(jī)
半個(gè)月后,
3號(hào)樓503寢室的就寢率直降為零。
因?yàn)榘_(dá)否也終于開始夜不歸宿了,。
易天霖本就神出鬼沒。自上次外場(chǎng)試驗(yàn)失敗后,,便一頭扎進(jìn)實(shí)驗(yàn)室里,試圖將他的燙手大腸桿菌提升一個(gè)檔次,,進(jìn)化為烈焰大腸桿菌,。
盧赫自打下了定了決心后,,經(jīng)常在實(shí)驗(yàn)室抱著鋅指平臺(tái)睡到后半夜,把結(jié)果做完電泳之后,,再回寢室睡一個(gè)不超過3個(gè)小時(shí)的回籠覺,。
于是艾達(dá)否經(jīng)常獨(dú)享一個(gè)二十多平米的大單間,一人霸占三張椅子,,半躺著對(duì)著三個(gè)屏幕敲敲打打,。有時(shí)是在世界第一程序員交友平臺(tái)gayhub上攢綠格子;有時(shí)是接下了幾個(gè)私活,,用和他同名的小軟件,,反編譯幾個(gè)小程序,掙點(diǎn)零花錢,;而更多的時(shí)候,,則是徜徉在游戲的海洋里。
每每看到盧赫披著月光進(jìn)門,,或者頂著白露出門,,他都要嘲諷一句:
“卷王!”
而如今,,他卻成為了503乃至全學(xué)院的卷中卷中卷中卷,。
這天,盧赫又一次披星戴月地返回寢室,,半路上看見隔壁計(jì)算機(jī)學(xué)院院樓的小廣場(chǎng)里,,半人多高的茂盛萬年青上,飄著一個(gè)人頭,。
那人頭緩緩地沿著綠化帶,,從南飄到北,又從北飄到南,。如此反復(fù)幾趟,,然后越飄越遠(yuǎn),直至只露出頭頂上幾縷被風(fēng)掀起的頭發(fā),。伴隨著噗通一聲,,人頭徹底消失在視線,。
盧赫連忙上前查看,,發(fā)現(xiàn)艾達(dá)否正跪拜在花壇中央的銅制的艾倫·麥席森·圖靈的全身雕像前。
他悄聲走到艾達(dá)否身后,,把手從衣兜里抽出,,輕撫對(duì)方的肩膀,“平身,?!?p> 艾達(dá)否被驚得一得瑟,,轉(zhuǎn)頭發(fā)現(xiàn)是盧赫,便立刻起身照著盧赫的屁股揣了一腳,,“瞅你那揍性,,竟敢占我便宜。你腦袋里有哏丘還是咋地,,大半夜的不睡覺,,到處瞎轉(zhuǎn)?!?p> “你腦子才有毛病,。”盧赫連連躲閃,,“閑得沒事拜那玩意兒干啥,,知道那位神死得有多慘嗎?不如去拜數(shù)學(xué)院的那尊祖沖之,?!?p> “祖沖之太遠(yuǎn)了,懶得走過去,?!卑_(dá)否抬腳又踢了個(gè)空,“讓你侮辱我偶像,?!?p> 兩人嬉鬧地繞著花壇追逐了兩圈,隨后一同癱在長椅上喘氣發(fā)呆,。
“老艾,,說正經(jīng)的,你最近抽什么風(fēng),,怎么突然就那么卷,?”盧赫從背包中掏出一瓶礦泉水,咕咚灌了一口,。
艾達(dá)否仰面望著天空上的半輪月,,砸了砸嘴,“我遇見難事了,。DNA計(jì)算機(jī)聽說過沒,?”
“什么玩意兒?”盧赫被水嗆了一口,。
“DNA計(jì)算機(jī),,這是我的研究方向?!卑_(dá)否的臉上閃過一絲得意,,“我告訴這東西可牛了,,理論上與量子計(jì)算機(jī)比肩,可以解決NP完全問題,?!?p> “噗?!北R赫聽后嘲諷道,,“民科?!?p> 艾達(dá)否被激得起身坐直,,正言道:“你知道什么是NP完全問題嗎?”
“知道啊,?!北R赫把水瓶擰好,捏在手里心不在焉地晃著,,“如果一個(gè)問題可以在多項(xiàng)式時(shí)間內(nèi)猜出它的一個(gè)解,,那它就是NP問題。如果一個(gè)NP問題可以被其它所有NP問題約化到,,那么它就是一個(gè)NP完全問題,。”
艾達(dá)否聽后,,連忙豎起大拇指,,“牛啤啊,你還知道多項(xiàng)式時(shí)間和約化,?”
“切,。”盧赫得意地?fù)P起下巴,,“多大點(diǎn)事兒,,當(dāng)誰沒編過程似的。不就是時(shí)間復(fù)雜度里的n出現(xiàn)在底數(shù)位置嗎,?非得給人重起個(gè)名叫多項(xiàng)式時(shí)間,,故弄玄虛?!?p> “至于約化,,不就是解決不了一個(gè)問題,就繞過它,,去研究一個(gè)更復(fù)雜的問題,,對(duì)其進(jìn)行降維打擊嗎,?舉個(gè)例子,,你腦子不好使死活解不出一元一次方程,,靈機(jī)一動(dòng)想出了個(gè)點(diǎn)子:
既然我解不出一元一次的,那我干脆去研究二元一次的,。一旦我把二元一次的給解出來,,那一元一次的就該像喝水一樣簡單了?!?p> “至于你說得什么NP完全問題,,那不就是以多項(xiàng)式時(shí)間作為上限,,無限去做約化,。我解不出一元一次的,我就去解更復(fù)雜的二元一次,;解不出二元一次,就去解更復(fù)雜的三元一次,。
這樣無限套娃下去,,約化到一個(gè)無限復(fù)雜的問題,你拍著胸脯說:嘿,,只要把這道題解出來,世界上所有問題就都難不倒我了,!”
盧赫說完,右手搭在艾達(dá)否肩膀上,,左手指著天空:“老艾啊,哥送你一句話:仰望星空,,腳踏實(shí)地,。左腳蹬右腳永遠(yuǎn)都上不了天?!?p> 艾達(dá)否聽后不屑地笑了笑,,“你可去拉倒吧,,你個(gè)思想落伍的保守分子,。DNA計(jì)算機(jī)是怎么工作的你知道嗎?”
“怎么工作的?。俊北R赫來了興致,。
艾達(dá)否一臉認(rèn)真地娓娓道來:
“你知道哈密頓問題嗎,?圖論里面的最著名難題。不知道也沒關(guān)系,,給你簡單點(diǎn)描述一下:
假如你是一個(gè)時(shí)間管理大師,,同時(shí)交往著5的女朋友,,這些女朋友分布在5個(gè)不同的城市。有一天,,你被老板派到另一個(gè)城市出差。好巧不巧,,在那個(gè)城市你一個(gè)女朋友都沒有,而你非常想念她們,,想借著公費(fèi)出差的機(jī)會(huì),,把這5個(gè)女朋友都見一遍。
由于經(jīng)費(fèi)有限,,你又很摳門不想多掏機(jī)票錢,所以每個(gè)城市只能去一次,。同時(shí)這些城市之間又不全部都有雙向直飛航線,你該怎么做呢,?
你可以想想,,但我告訴你不論你怎么想都沒用,。因?yàn)檫@類問題的解法只有一個(gè),那就是試,!和我們暴力破解密碼一樣,一個(gè)一個(gè)試,!
進(jìn)一步的,如果你不只五個(gè)女朋友,,而是有50個(gè)、500個(gè),、5萬個(gè)、無窮個(gè),,你該怎么辦,?”
盧赫對(duì)著艾達(dá)否逐漸由認(rèn)真轉(zhuǎn)為嬉笑的臉,,思索片刻,答道:“我覺得這個(gè)問題我不需要考慮,。5個(gè)女朋友大眼一瞅在紙上畫畫也就出來了,如果再多,,我肯定會(huì)先死在床上?!?p> “你個(gè)死變態(tài),。”艾達(dá)否一臉嫌棄道:
“很難對(duì)吧,?這其實(shí)是一個(gè)時(shí)間復(fù)雜度為n!的問題,,也就是說,如果你有n個(gè)女朋友,,就要嘗試n的階乘次,。如果你女朋友多達(dá)萬個(gè),就算是擁有4萬個(gè)核心天河三號(hào),,也要算到你年過花甲,。
可這個(gè)問題對(duì)于DNA計(jì)算機(jī)來說,卻是小菜一疊,。它是這么算的:
假如你現(xiàn)在剛見完1號(hào)女朋友,,準(zhǔn)備奔赴到2號(hào)的懷抱。那么你離開1號(hào)女朋友的行為,,就被編碼為ACAC,;奔赴2號(hào)女朋友的行為,被編碼為GTGT,。把這兩串編碼合起來,,ACACGTGT就代表你從1號(hào)到2號(hào)的路徑。
接下來,,你見完了2號(hào)女朋友,,又匆匆趕往3號(hào)。這個(gè)過程可以再用編碼表示為TCTCAGAG,。
也就是說,,8個(gè)堿基就可以用來表示你和其中一個(gè)女朋友從見面到拜拜的全過程。這個(gè)時(shí)候你肯定就要問了,,我要你規(guī)劃一條連續(xù)的路徑,可ACACGTGT,、TCTCAGAG是分離的兩條鏈,這還怎么能玩兒的下去,?
很簡單嘛,,堿基對(duì)是可以互補(bǔ)的。你再找一條CACAAGAG,,不就可以跟膠水一樣,把那兩條毫不相關(guān)的鏈給粘起來了嗎,?
接下來的事情就更簡單了,。你有幾個(gè)女朋友,,就用幾串8位編碼來表示和她們的見面和拜拜的過程,。然后你把你的女朋友和膠水都合成一下,擴(kuò)增個(gè)幾萬億條,,放在一起,養(yǎng)蠱,。
根據(jù)堿基配對(duì)原則,膠水分分鐘就能發(fā)揮作用,,把各種女朋友給粘起來。這個(gè)時(shí)候,,你會(huì)得到幾萬億條路徑,。這就是路徑遍歷的所有結(jié)果,。
那你又要問,我怎么把最省錢的那一條路徑給篩選出來呢,?
這也很簡單,你的起點(diǎn)和終點(diǎn)是固定的,。只要拿起點(diǎn)和終點(diǎn)作引物,擴(kuò)增一下,起終點(diǎn)正確的路才能被擴(kuò)增,,不正確的會(huì)被逐漸稀釋掉,。至于有些路徑上,,你少見了幾個(gè)女朋友,或者重復(fù)多見了幾個(gè)女朋友,,這些鏈的長度肯定是不對(duì)的,。
最終,你把它們電泳一下,,鏈長的和鏈短的分開,,挑出長度剛好的鏈,測(cè)個(gè)序,,答案不就出來了嗎?”
艾達(dá)否說完,,搶過盧赫手里的水,,猛灌了幾口,“要知道,,1克的DNA可以存儲(chǔ)215PB的數(shù)據(jù),,相當(dāng)于2億部小電影。這還不算完,,由于堿基配對(duì)的速度不慢,,這215PB可以直接當(dāng)作內(nèi)存用,,有幾條鏈就相當(dāng)于有幾個(gè)線程并行運(yùn)行,。
有個(gè)神仙已經(jīng)設(shè)計(jì)出了多項(xiàng)式時(shí)間的,、基于DNA算法的NP完全算法,,只不過減少時(shí)間復(fù)雜度的時(shí)候,,犧牲掉了空間復(fù)雜度。這個(gè)算法實(shí)現(xiàn)起來,,需要有指數(shù)數(shù)量的編碼方式,,和巨額的存儲(chǔ)空間,。
可這些對(duì)DNA來說都是灑灑水,剛才都說了,,DNA的存儲(chǔ)效率極高,。因此,DNA解決NP完全問題,,指日可待,!”
盧赫聽后連連拱手稱贊道,“厲害,,厲害,。不過我有個(gè)問題,,你剛才說的那個(gè)哈密頓路徑算法,,頂多就是個(gè)算法,,它有邏輯判斷能力嗎,?它算個(gè)哪門子計(jì)算機(jī)呦?”
艾達(dá)否擰緊瓶蓋,,把水瓶仍會(huì)盧赫懷里,,“你還真是瞎狗端星星——死活看不出個(gè)樣兒來,。我就是給你舉個(gè)簡單的例子,,至于邏輯判斷,,不就是幾個(gè)通用邏輯門的組合嗎,?
與,、或,、非、與非,、或非等通用邏輯門都已經(jīng)被設(shè)計(jì)出來了,。實(shí)際上,,只要與非或者或非,所有的邏輯門就都可以實(shí)現(xiàn),?!?p> “呵呵?!北R赫細(xì)品了一下艾達(dá)否的話,,品出了他正極力掩飾的東西,幽幽開口道:“門都已經(jīng)實(shí)現(xiàn)了,,可為什么這種神仙東西卻遲遲不面世,?”
艾達(dá)否的氣勢(shì)瞬間萎了下來,“因?yàn)檫€有點(diǎn)問題,。你知道鏈置換過程吧,,兩條互補(bǔ)鏈相遇就會(huì)立刻粘起來,不管兩條鏈一不一樣長,,先粘起來再說。就好比你找女朋友,,一見鐘情一般都是很難的,,肯定是遇到合適的,就先談起來再說,。
可是如果日后遇到更合適了的呢,?我想以你的人品,肯定會(huì)毫不猶疑地把原來那位甩掉,,然后和更合適的談,。DNA也一樣,如果基鏈遇到了更搭配的互補(bǔ)鏈,,就會(huì)通過鏈置換原理把當(dāng)前的互補(bǔ)鏈踢掉,,換成更匹配的一條,。
比如與門,它的實(shí)現(xiàn)過程就是先給一條基鏈上貼上一條互補(bǔ)鏈,,然后再給它兩條更搭配的置換鏈,,把原來那條互補(bǔ)鏈給擠出去。這樣,,兩條置換鏈為輸入真,,原互補(bǔ)鏈為輸出真,就形成了一個(gè)基本的計(jì)算單元:與門,?!?p> “你大爺?shù)木垢屹|(zhì)疑我的人品,你不了解我,,我可是很專一的一個(gè)人,。”盧赫拿起懷里的水瓶,,猛地砸向艾達(dá)否,,“還有,你這是什么破爛與門,,那輸入鏈和輸入鏈都是基鏈的一部分互補(bǔ)鏈,,二者這么相似,你這計(jì)算單元計(jì)算了個(gè)寂寞???1+1等于1?”
艾達(dá)否揉了揉被砸疼了的肩膀,,長嘆了一口氣,,“就是啊,輸入和輸出都差不多,,計(jì)算了個(gè)寂寞,。所以我現(xiàn)在正在想法子,解決這個(gè)問題,?!?p> 他說完仰頭長嘯:“蒼天啊,各位神啊,,保佑我吧,,賜給我一個(gè)開天辟地的靈感,拯救我于水火之中吧,。下輩子我肯定給你們當(dāng)牛做馬,。”
盧赫在一旁暗自思忖,,然后發(fā)話道,,“老艾,,你可能要當(dāng)我的馬了?!?p> 艾達(dá)否眼前一亮:“什么意思,?”
“沒想到啊老艾,當(dāng)我的馬你這么激動(dòng),?!北R赫笑著說:“我有一個(gè)大膽的想法。你知道發(fā)夾環(huán)嗎,?就是DNA上的富含GC的回文序列,,轉(zhuǎn)錄成mRNA之后,形成的一個(gè)倒T形的長得像奶嘴一樣的東西,。
如果你在基鏈上設(shè)計(jì)兩個(gè)回文序列,,它們就有粘在一起的傾向,形成一個(gè)發(fā)夾環(huán),。發(fā)夾環(huán)底座上的互補(bǔ)鏈作為輸入,,它往底座上粘的時(shí)候會(huì)促使奶嘴兩側(cè)的回文序列越粘越緊,直至其上原本的互補(bǔ)鏈被擠下去,,完成鏈置換,。奶嘴上被擠下去的那條鏈,就是輸出,。
這樣,,雖然輸出是固定的GC回文序列,但是輸入可以是任意的,,從而做到輸入和輸出毫不相關(guān),,你這問題不就解決了嗎?”
艾達(dá)否聽后立刻激動(dòng)地蹦起,,狠狠地?fù)肀Я艘幌卤R赫,,然后小跑到圖靈雕像前還愿:
“范內(nèi)瓦·布什,什爺,;馮·諾依曼,,馮叔;麥席森·圖靈,,麥伯伯;唐納德·克努特,,唐哥,。”他圍著雕像轉(zhuǎn)了一圈后,,跑回盧赫面前,,鞠了一躬,,“還有你,我親愛的兒子,,盧小弟,。感謝你們賜予我靈感?!?p> 盧赫一腳踹向艾達(dá)否:“你大爺?shù)?,我才是你爸爸。還說我人品不好,,我看你才是個(gè)花心大蘿卜,,拜了這么多人?!?p> 艾達(dá)否靈活地閃躲,,“這你就不懂了,buff不嫌多,。你這么些天早出晚歸的,,一定也遇上什么困難了吧?”
艾達(dá)否說完,,走上前把盧赫拉起來,,“走走走,拜拜去,。老祖宗說得好,,心誠則靈?!?p> 盧赫起身,,但并沒有走向雕像,而是轉(zhuǎn)身面朝生科樓,,樓側(cè)里德實(shí)驗(yàn)室?guī)讉€(gè)大字被燈帶圍了起來,,正發(fā)著慘白的光。
他并不相信艾達(dá)否的鬼話,。但如果一定讓他拜一個(gè)人的話,,他只想真誠地問羅伯特·里德一句話:
我尊敬的里德先生,你發(fā)明的鋅指技術(shù),,曾經(jīng)創(chuàng)造了那么多的輝煌,。可又為什么在幾十年后的今天,,如此黯然失色,?