圖靈機(jī)的發(fā)明

第二次世界大戰(zhàn)期間，戰(zhàn)斗正在英倫三島和英吉利海峽激烈地進(jìn)行著。當(dāng)?shù)聡ㄎ魉沟娘w機(jī)轟炸英國機(jī)場時(shí)，機(jī)場上卻空空如也，等待著他們的只有密集的高射炮火，德國法西斯最高統(tǒng)帥部碰到這種事已不止一次了。他們意識(shí)到了自己的密碼聯(lián)系已被英軍破譯，英軍已掌握了他們的秘密軍事通訊。納粹頭子急于在自己內(nèi)部尋找叛徒以除后患。然而他們做夢也沒有想到，英國軍事當(dāng)局并沒有拿到密碼本，而是一位年輕的英國數(shù)學(xué)家圖靈用數(shù)學(xué)方法破譯了德軍使用優(yōu)良的恩尼格瑪發(fā)報(bào)機(jī)發(fā)出的任何密碼。一位數(shù)學(xué)家曾經(jīng)這樣說過：“如果沒有圖靈發(fā)明的設(shè)備，真不知第二次世界大戰(zhàn)的歷史是不是會(huì)另個(gè)一樣子！或許第二次世界大戰(zhàn)的歷史會(huì)重寫?！边@也許有點(diǎn)言過其實(shí)，但圖靈的功績確實(shí)很偉大。

1912年6月23日，圖靈出生在倫敦的一個(gè)中上層家庭里。他自幼聰明伶俐，刻苦好學(xué)。1931年他進(jìn)入劍橋大學(xué)后，他的多方面才能迅速爆發(fā)出來。1935年就以《關(guān)于高斯誤差函數(shù)》的論文獲博士學(xué)位，同時(shí)榮獲史密思獎(jiǎng)。在整個(gè)第二次世界大戰(zhàn)中，他受聘于英國外交部的通訊處，用他特有的數(shù)學(xué)知識(shí)設(shè)計(jì)了破譯密碼的機(jī)器，獲得了帝國勛章。

圖靈的工作主要是把人們在進(jìn)行計(jì)算時(shí)的動(dòng)作分解成比較簡單的動(dòng)作。我們想象一個(gè)人在一張方格紙上做計(jì)算，他需要（1）一種貯存計(jì)算結(jié)果的貯存器，即紙張；（2）一種語言，表示加減乘除等操作和數(shù)字的符號(hào)；（3）掃描區(qū)，在計(jì)算過程中，看到的上下左右?guī)讉€(gè)方格中的數(shù)字；（4）計(jì)算意向，即在計(jì)算的每一階段打算下一步做什么。例如看到6＋9就要準(zhǔn)備進(jìn)位等；（5）執(zhí)行下一步計(jì)算。圖靈成功地把人的計(jì)算活動(dòng)機(jī)械化，從理論上說，如果解方程，搞近似計(jì)算，無非是按照某種算法，告訴機(jī)器在遇到注視格中出現(xiàn)什么情況時(shí)按什么計(jì)算意向去執(zhí)行下一步動(dòng)作。因此，凡是人或其他機(jī)器執(zhí)行的算法，圖靈機(jī)都可以做到。這架機(jī)器就是我們所說的圖靈機(jī)，通過上述大略描寫，我們也許能大概揣測出圖靈機(jī)為什么能破譯密碼了：因?yàn)榕碾妶?bào)無非是按一定的規(guī)則在一條紙帶上穿孔，其規(guī)律正和計(jì)算機(jī)執(zhí)行某種程序相同。因此我們就能夠把密碼和程序聯(lián)系起來，通過設(shè)法檢驗(yàn)程序，也就破譯了密碼。