圖靈機的數據在哪裡

Ⅰ 圖靈機是什麼東西啊

其實呢，圖靈機的來歷忒單純。以前一個叫圖靈的閑人養了只無所事事的小母雞。圖靈成天忙著跑馬拉松，懶得照顧它，就裝了條在雞看來無限長分格的傳送帶，定時傳送食物和水。而雞閑來無聊，便走來走去，在帶子上擺放物事，權作耍子。郁悶時在格子里放根樹枝。興奮了在某個格子里下個蛋。想起了還可以把蛋換成樹枝，或者把樹枝換成蛋。不高興了在傳送帶上扔顆石頭，於是傳送帶就卡住了。某天小母雞不小心把一株野生大麻當雞骨草吞了，high得不行，繞著傳送帶發瘋：
在傳送帶靠左的地方放下一根樹枝一個蛋：10
在傳送帶靠右的地方放下兩根樹枝：11
回到左邊，把樹枝揀起來，再把蛋換成樹枝：1
回到右邊，把兩根樹枝換成一根樹枝兩個蛋：100
回到左邊，把樹枝揀起來
回到右邊，把最右邊的蛋換成樹枝：101
這下左邊的樹枝和蛋都沒了。小母雞意興索然，一怒之下扔顆石頭卡死機器。

剛從雜貨店提了袋蘋果的圖靈路過，目睹這一切。不由靈光一現：這不2+3=5么？原來加法還可以這么玩兒啊！以後不用為算帳發愁了。不過圖靈的興趣不在算帳，而在玩兒tic-tac-toe。問題是小母雞智力有限。要她理解tic-tac-toe這樣的東東還不如讓公牛上樹兔子下蛋。幸好圖靈是個好琢磨的勤快人，沒事喜歡讀一個叫Kurt Godel的德國人的文章。而Godel崇拜一個叫David Hilbert的老鄉。Hilbert在德國哥廷根討生活時沒事喜歡玄想，一不小心在世紀之交提出23個問題。居然引得此後100年來無數閑人神魂顛倒。Godel對第10個問題著了迷。研究幾年後，寫了篇帖子總結心得，順便告訴大家，Hilbert也有猜錯的時候。第10個問題的答案是我們不能依靠形式化方法找到所有丟番都方程的解。而推論就是大家就不用指望設立幾個事實（閑人們管這叫公理），再用一套規則推出所有真理。「我們必須知道，我們必將知道」的難度比Hilbert預計的大多了。這一下徹底broke Hilbert』s heart。不過我跑題了。Godel的論文花了大量篇幅描述怎麼用數字來表示自然數以外更復雜的東東（黑話叫encoding）。圖靈應該看過這篇文章。他很快發現，用樹枝和蛋完全可以模擬出tic-tac-toe。比如說四個蛋表示左上角畫圈。三個蛋一根樹枝, 0001，表示左上角畫X。而且他證明了就算小母雞吃了大力丸能用更復雜的符號在傳送帶上描述tic-tac-toe，也不過比她用樹枝和蛋少花4log(|∑|)倍的時間而已。這里的|∑|代表一共有多少所謂的復雜符號。 於是圖靈寫了帖子，介紹他的雞。後人就把這只雞叫圖靈雞了。 而且人們驚奇地發現，雖然他們做出的機器越來越花哨，下國際象棋能讓大尾巴狼卡斯帕羅夫肝腸寸斷，失意江湖，也不過是一隻擺放樹枝和蛋時快如閃電的圖靈雞而已，和作古的正宗圖靈雞沒有本質區別。我們為了紀念這個現象，就造了一專用名詞，圖靈等價。人們還觀察到有些問題非圖靈雞不可，於是再造一詞：圖靈完備。現在很多老大喜歡把圖靈完備和圖靈等價混用。這好比說命題成立所以逆命題成立，多數時候不靠譜。不過這個話題值得單獨寫一帖子，以後再說吧。
圖靈並不滿足於簡單的2＋3＝5和tic-tac-toe，所以他敏銳地注意到另一個重大挑戰：如果每隻雞都只能做一種計算，他得養多少雞組裝多少傳送帶才能算帳啊？更別說下國際象棋了。人肉計算機圖靈是做化繁為簡的高手。這個高難問題被他舉重若輕地解決了：首先他證明了任何圖靈機都可以用樹枝和蛋表達。然後他養了只更聰明的雞(圖靈搞了N年的數學生理學和形態發生學，大家知道是為什麼了吧？)。這只雞吃腦白金喝農夫山泉，嘛都不幹，不打鳴不下蛋，但會識別理解用樹枝和蛋描述的其它圖靈機，並在傳送帶上模擬它們的操作。用閑人們的黑話總結，就是對任意問題x, 和 , 總存在一隻雞U，使得 。這里的 是用a這串樹枝加蛋的長列表示的圖靈雞。這樣的雞，一隻頂一萬只啊。從此，圖靈不需要再養那麼多雞了，他只需用樹枝和蛋擺出算帳的方法，和提供數據，這只雞就能算出結果。想到這里，圖靈只覺元氣充沛，不禁仰天長嘯：I do chicken right. 這只新品種的雞從此被稱為元圖靈雞(Universal Turing Machine)。Universal者，我雞一出百雞殺之意也。元圖靈雞具有重大意義，代表了兩大計算支柱（還有一個是self-reference）：universality，和ality。Universality我們才說了。而ality是說數據和程序本是如來佛祖座前絞在一塊兒的兩根燈芯。比如用樹枝和蛋表示的圖靈雞，你說它是程序呢，還是數據？理論界的元老Martin Davis在他的書里甚至說儲存程序的計算機這一革命性的概念就是起源於這只元圖靈雞。對了，當年英國有圖靈這樣的先驅，造出世界上第一台通用計算機，為什麼到頭來計算機歷史讓美國人獨大呢？說來也是一段讓人嗟嘆的故事。一言以蔽之，籠中雞不如走地雞，走地雞不如野雞。有興趣的可以讀Andy Kessler的How We Got Here。這本書語言之生動，段子之幽默，故事之曲折，史料之有趣，實在不可多得。而且免費。不能不推薦的說。
當然，一隻雞是遠遠不夠的。圖靈在1952年寫了一坨國際象棋程序，當時居然沒有機器能跑動。很快閑人們一窩蜂撲向計算復雜性這個嶄新的研究領域。4、50年前實在是烽煙四起的戰國時代啊，到處是傳奇英雄的傳奇故事。好像隨便什麼領域都有震撼人心的發現。1964年，Alan Cobham和Jack Edmonds在ACM BBS上發帖，說如果一個問題能被一隻圖靈雞用有限步驟解決，而解決的步數是這個問題長度的多項式，那麼這個問題的復雜度就是P。P是Polynomial的縮寫。可惜有些問題的演算法遠比P復雜，比如找出國際象棋對局的最佳策略。不過很快有人提出，有些問題雖然看似復雜，但驗證這些問題的演算法是否正確需要的復雜度卻是P。比如判斷一堆整數裡面有沒有幾個整數的和剛好為0。驗證某個可能答案太簡單了：對答案里的數求和就行，花的時間最多等於這堆整數的個數。於是有達人就想：這樣好辦啊。如果一個問題的備選答案有N個，那我們就養它N只雞，讓每隻雞驗證一個答案。如果每個答案的驗證復雜度都是P，那最終的復雜度不也是P了么？可惜，得到驗證結果前我們不知道哪個候選答案一定正確，也不能確定哪只雞先得到答案，就好像不知道哪個女工先找到旺卡巧克力工廠的金券。為了和普通的圖靈雞區分，閑人們把這種兵團做戰的雞群叫做non-deterministic圖靈雞 。因為用這種圖靈雞能在多項式時間內找到答案，所以我們把這種復雜度叫NP，也就是Non-deterministic Polynomial的簡寫。還是很直觀的吧？很明顯，P是屬於NP的，因為既然我們能在P內找到答案，自然能在P內驗證答案。那有沒有屬於NP但不屬於P的呢？俺就不知道了。如果我知道的話，我就證明了P=NP或P != NP，拿了Cray研究院的100萬美元花紅，到Bora Bora的海灘悠哉游哉地喝Pina Colada樂。
不能證明P是否等於NP沒有打擊閑人們的積極性。不知道是否等於總比知道不等於好吧？所以牛人們還是前赴後繼地探索。於是NP-Hard就被提出來樂。NP-hard的概念也直觀：我不知道你具體有多復雜，但我知道你至少和NP問題一樣復雜。什麼叫一樣復雜呢？於是有牛人提出，反正多項式加上多項式還是多項式。所以可以判斷，如果我們已知一個問題H的演算法並且每一個屬於NP的問題都可以在多項式時間內通過把玩H得出，那H就是NP-hard。也就是說，如果存在一個函數（或者演算法）f, 使得f(H)＝所有NP問題的集合，且計算f(H)的開銷是P，那H就是NP-hard的。當然，我們還是可以讓一隻圖靈雞來執行這個函數，所以有函數f存在被稱為圖靈多項式可歸約（polynomial time Turing recible）如果H同時也屬於NP，那H就是NP-Complete樂。我們可以相對容易地證明，如果有一個問題，哪怕只有一個問題，既屬於NP也屬於P，那整個P和NP就坍塌了，P＝NP。有興趣的老大可以自己證明一下。到了這里，關於復雜性的研究好像被堵死了。確定一個問題是否為NP-Hard，就得證明它能被多項式歸約到所有NP問題。簡直就是mission impossible嘛。就在這存亡之際，出身水牛城安家多倫多的庫克爺爺小宇宙爆發，於1971年證明了SAT問題（也就是判斷什麼樣的集合能讓一個布爾公式為1）屬於NP-Complete。一時間眾生顛倒。有了SAT墊底，我們就不用去對付所有的NP問題，而只需要對付規約到SAT這一相對簡單得多的問題。到目前為止，屬於NP-Complete的問題沒有1000也有500了吧？人們還相繼發現了其它復雜類。這里羅列了幾乎所有的復雜類，共有462種。

Ⅱ 第一台電腦為什麼要叫埃尼阿克

1946年2月15日是計算機發展史上值得紀念的一個日子。這一天美國賓夕法尼亞大學的莫爾學院喜氣洋洋，許多人心情激動地來到莫爾學院，參加一個可載入史冊的典禮，即人類歷史上第一台現代電子計算機的揭幕典禮。這台機器名為「電子數值積分和計算機」(簡稱埃尼阿克，見圖 1.1)，它看上去完全是一個龐然大物，佔地面積達170m2，質量達30t，耗電量也很驚人，功率為150kW，共使用了近兩萬個電子管，在工作時這些管子看上去活像兩萬只點著的燈泡。埃尼阿克主要用來進行彈道計算的數值分析，用十進制進行計算。它在 1s圖1.1埃尼阿克計算機內能進行數百次的加法運算，這在當時已是劃時代的高速計算機了。用它計算炮彈著彈位置所需要的時間，比炮彈離開炮口到達目標所需要的時間還要短。它一度被譽為「比炮彈還要快的計算機」。經過多次改進，後來的埃尼阿克成為一台能進行各種科學計算的通用計算機。它的最大特點是採用了電子線路來執行算術運算、邏輯運算和儲存信息。同以往的計算機相比，它的速度極快，比兩年前艾肯研製的機電式自動控制計算機要快1000倍。這使得它能勝任相當廣泛的現代科學計算。埃尼阿克是人類計算工具發展史上一座不朽的豐碑。它是世界上第一台真正能運轉的大型電子計算機。正是它同幾年後製成的馮·諾伊曼機一起，奠定了現代計算機原型。
在從蒙昧時代到文明社會的艱難進行過程中，人類發明了輪子、杠桿、熱機、機床、電話、電視等。這些人類智慧的果實已經延長了人類的感官的功能，從而促進人類社會不斷發展。而電子計算機的發明更是史無前例，對人類生活的影響將是不可估量的，因為它延長了人類最神秘也最寶貴的部分——腦的功能。埃尼阿克的問世也充分表明，一項重大發明只有為社會發展所迫切需要，才能脫穎而出。反之，如果社會沒有這方面的需求，多麼美妙的設想也逃脫不掉為歷史所淘汰的命運。電子計算機製造技術在20世紀30年代已經成熟，而在20世紀40年代才開花結果， 也許正是這個原因。在冷酷無情的歷史面前，個人的力量太渺小了。是莫克利而非阿塔納索夫發明了電子計算機，這不是個人的力量所能決定的，這是歷史的選擇。
雖然埃尼阿克的運算速度已經相當快了，但是，它仍然沒有最大限度地發揮採用電子技術所提供的巨大潛力。初生的電子計算機存在著明顯的缺陷：① 它的存儲容量太小；② 它的程序是用線路連接的方式實現的，不能存儲。為了進行幾分鍾或幾小時的數字計算，要花費幾小時甚至1～2天的時間做准備。而且，由於它耗電量大，工作起來常常會因燒壞電子管而被迫停機檢修。
圖1.2馮·諾伊曼還在1944年，即 ENIAC尚未竣工時，人們已經意識到了這些問題。美國軍方要求莫爾學院在建造 ENIAC的同時，立即設計效率更高的計算機。就在這一關鍵時刻，計算機發展史上又一重要人物——馮·諾伊曼教授(見圖1.2)承擔了這一重要任務。1903年，馮·諾伊曼出生於匈牙利的布達佩斯，他從小就顯示出多方面的天才，不到18歲，就和輔導老師合寫了一篇數學論文。他精通7門語言，為其從事科學研究奠定了深厚的基礎。幾乎在獲得布達佩斯大學數學博士學位的同時，興趣廣泛的馮·諾伊曼又通過了蘇黎世高等技術學院化學方面的學士學位考試。博學多才的馮·諾伊曼在理論科學和技術科學方面都有較高的造詣。他的早期工作主要涉及純數學領域，但他並不僅僅關心純數學的進展。他堅信在現代文明社會中對基礎學科的評價會降低，技術永不停息的發展對人類社會的推動作用會大大加強。因此，他特別關注物理科學和技術科學的狀況，努力發掘使用現代數學方法的潛在威力。1944年的夏天，一個偶然的機會，馮·諾伊曼得知莫爾小組正在研製電子計算機。當時，他正參加第一顆原子彈的研製工作，面臨著原子核裂變反應過程中的大量計算問題。這些問題涉及數十億初等算術運算和初等邏輯指令。它們雖然不需要非常精確的最終數據，但所有中間的和細節的運算都必須相當精確。為此，曾有成百名女計算員一天到晚用台式計算機演算，結果還是不能令人滿意。作為彈道研究所和洛斯·阿拉莫斯科學研究所的顧問，馮·諾伊曼一直在尋找解決計算問題的新方法。因此，當聽到製造電子計算機的消息後，他大為驚喜，隨即專程到莫爾學院參觀了還未竣工的ENIAC 。科學家的洞察力以及深厚的科學素養，使他立刻覺察到了電子計算機應用的廣闊前景。這位著名數學家毫不猶豫地投入到成敗未卜的新型計算機的設計工作中，並迅速成為這一領域的帶頭人。
查看演示
正是在馮·諾伊曼的帶領下，從1944年8月到1945年6月短短10個月的時間內，計算機的設計工作獲得了巨大的進展。人們定期在莫爾學院舉行學術會議，提出各種報告，許多富有創見的思想接二連三地涌現出來。經過嚴肅的爭論和激烈的交鋒，形成全新的科學思想，前所未有的存儲程序通用電子計算機方案——EDVAC 方案就這樣問世了。這份浸透了科學家們的智慧和心血的報告草案共101頁，它明確規定新型計算機有5個組成部分：① 計算器CA；② 邏輯控制裝置CC；③ 存儲器M；④ 輸入I；⑤ 輸出O。並詳細描述了這5個部分的職能和相互關系。同ENIAC相比，EDVAC方案有兩個重大改 進：① 為充分發揮電子元件的高速度而採用了二進制；② 提出了「存儲程序」，可以自動地從一個程序指令進到下一個程序指令，其作業順序可以通過一種稱為「條件轉移」的指令而自動完成。長達101頁的EDVAC方案是計算機發展史上的一個劃時代的文獻。在這個方案中，首次提出了存儲程序的概念，解決了第一台電子計算機 ENIAC的重大缺陷。也正是在這一方案中，提出了現代計算機發展的基本體系結構，從而奠定了現代計算機的發展基礎。由於馮·諾伊曼的巨大的聲望和榮譽，他的參與使得計算機的研製工作受到社會上的廣泛重視，從而為計算機的迅猛發展開辟了道路。
存儲程序的概念是計算機發展史上的又一座豐碑。長期以來，人們一直認為這一重要概念是馮·諾伊曼和 ENIAC小組最先提出來的。然而，馮·諾伊曼從來沒有說過存儲程序型計算機的概念是他最先提出的。相反，他不止一次地指出，圖靈是現代計算機設計思想的提出者。那麼，圖靈是怎樣一個人呢? 圖靈是英國著名的數學家和科學家，他的深刻的思維能力和非凡的創造力使人們不能不承認他是一個天才。在他短暫的42年的人生旅途中，他獲得了來自各個方面的崇高榮譽和極大聲望。人們確信如果不是正當壯年卻意外死亡，他一定會為科學史的長卷寫出更美的篇章。圖靈生於1912年，1931年進入劍橋大學學數學，畢業後留校任教。1936年，年僅24歲的圖靈便提出了理想計算機——圖靈機的理論。圖靈機由三部分組成，包括一條帶子、一個讀寫頭和一個控制裝置。他證明存在一種圖靈機，它能模擬任何給定的圖靈機，這就是通用圖靈機。通用圖靈機把程序和數據都以數碼的形式存儲在紙帶上，是「存儲程序」型的，這種程序能把高級語言寫的程序譯成機器語言寫的程序。通用圖靈機實際上是現代通用數字計算機的數學模型。這個理論是在第一台電子計算機問世的10年前提出的，這就不能不讓人感嘆圖靈思想的深刻與超前。特別值得指出的是，圖靈提出理想計算機的理論，其目的並不是為了研製某種具體的計算機，而是為了解決線性數學的一個基礎理論問題。也就是說，圖靈關於計算機的種種設想都是在抽象的純粹的理論思維領域進行的。他涉及的是現代計算機工作的基本理論問題，而不僅是實際製造和操作。正是因為圖靈研究的是計算機技術的深層理論問題，他才比其同代人更早地發現計算機理論研究的新情況、新問題。圖靈在1950年發表的《計算機能思考嗎？》一文又在西方世界引起了巨大反響，並掀起了關於機器能否思維這樣一場激烈爭論。就在這篇論文中，圖靈設計了一個聞名於世的「圖靈測驗」，即一個人在不接觸對象的情況下，同對象進行一系列的問答。如果他根據這些回答無法判斷對象是人還是機器，那麼就可以認為這個計算機具有與人相當的智力。目前，還沒有一台計算機能通過圖靈測驗。但是，圖靈認為在理論上有可能存在這樣的機器，它們能做某些非常接近於思維的事情。圖靈預言20世紀末將會製造出與人腦的活動方式極為相似的機器。作為計算機理論的先驅，圖靈的思想已遠遠走在時代的前面。然而，圖靈本人也並沒有遠離計算機的研製工作。在第二次世界大戰中，圖靈曾在英國外交部所屬的一個絕密機構服役。這個機構的主要任務是破譯德軍的密碼。現在發現的資料表明，在1943年，這個機構曾製造出一台有1500個電子管的破譯密碼的專用電子計算機。這台機器採用了圖靈機的某些概念，破譯了德國的很多密碼，在戰爭中發揮了重大作用。從英國政府20世紀70年代透露出來的一些文件來看，很可能世界上第一台電子計算機不是 ENIAC，而是與圖靈有關的。只是這種計算機的許多資料至今仍然是保密的，因此，就給人們留下了一個未解的謎。圖靈退役以後，來到英國國家物理研究所工作。在那裡，他積極參與了自動計算機ACE的研製工作。1945年，圖靈提供了一份長達50頁打字紙的ACE設計說明書。在這份報告中，他提出了模擬系統的思想，而帶有模擬系統的計算機直至20世紀70年代才被製造出來。兩年以後，在一份關於人工智慧的內部報告中，圖靈又提出了不少令人感興趣的概念。其中，關於自動程序設計的思想是20年後發展起來的人工智慧研究的重要課題。一般認為，現代計算機的基本概念源於圖靈。也正是為了紀念圖靈對計算機理論與研究的卓越貢獻，美國計算機學會設立的一年一度的計算機大獎，是以圖靈的名字來命名的

Ⅲ 睡前說：關於圖靈機

圖靈機，可以被定義為下面這樣一個七元結構：
Q：內部狀態集，具有有限元素；
q：初始內部狀態；
f：接受狀態；
L：可接受字元集，具有有限元素；
b：空白字元；
T：初始有序字元集，其元素記為T(i)，如果某個i的T(i)未定義，則為b；
s：狀態轉移規則表，是一個部分函數，將狀態<q, t>（q不為f）映射為<q', t'>（q'可以是f），並將當前字元集上的指標i進行轉移，成為i-1或者i+1。
當然，這里還有一個上面沒給出的圖靈機的狀態：
w：圖靈機是否已停機。

因此，一台圖靈機一旦開始工作，就是從初始狀態<q, t>開始的一連串的狀態轉移，此時w為false。
而如果遇到某個狀態<q', t'>是規則表中沒有定義的，即無法通過部分函數s進行映射，則圖靈機停機，w為true，但圖靈機當前狀態不為f。
如果更具狀態轉移規則s，圖靈機進入到了某個狀態<f, t>，則此事圖靈機停機。
因此，圖靈機的狀態<w,q>有這么三種：<false, *>，<true, not f>，<true, f>。

上面這些都很基本，沒啥好說的。

我們容易證明，上述對圖靈機的定義和一些別的定義是等價的。

比如說，對於狀態轉移規則表，原本的定義為(Q / {f}) × T ==> Q × T × {1, -1}的一個部分函數，但我們實際上也可以略加拓展為(Q / {f}) × T ==> Q × T × {1, 0, -1}，這樣的一個函數。
只需要對Q的選擇加以調整，使得新的Q包含原Q的所有內容，還包含一個狀態back，當當前轉移規則將狀態轉移為back時，這一步必然是+1，而後的一部必然是-1，那麼就實現了從只能前後移的雙態拓展為可以前後移與停留的三態。

非但如此，對於任意多個有限集，它們總是可以和一個有限集做一一對應的，因此即便Q是n維離散有限空間，或者T是n維離散有限空間，本質上都和一維的Q及一維的T的配置沒有區別。
更進一步，即便不是有限集，只要是離散集，N維集總是存在到一個一維集的一一映射的，因此T所處的介質即便不是一維的紙帶而是N維的超平面（從而N是n維離散空間），也和只能左右移動的原始圖靈機沒有分別。

接著，除了一次前後移動或者前後移動或停留這么一個三態以外，我們也很容易證明，即便移動規則調整為「在n處數據為t狀態為q根據規則s將數據修改為t'再運動到n'處並將狀態修改為q'」這么一種更加寬泛的運動，本質上也不會和原始的圖靈機的定義。
而，在這個定義下，狀態轉移規則s不再是(Q / {f}) × T ==> Q × T × {1, -1}的部分函數，而是一個(Q / {f}) × T × N ==> Q × T × N的部分函數，或者可以簡單寫為Q × T × N ==> Q × T × N的部分函數（既然是部分函數了，那麼只要在初態為f時無定義即可）。
而，在此定義下，原本作為背景而存在的定位用的「紙帶」，或者說「定位背景」，則可以被賦予更多的意義，比如它也兼顧了數據和狀態的功能。
事實上，既然N、Q和T都是離散集，Q和T還是有限集，那麼總可以構造一個N'，它和N × Q × T同構，從而整個圖靈機的運算就變成了在這個N'上，Q和T都是{0}的單元素集，而狀態轉移函數s則完全是N'到N'的部分函數。
在這個意義上，我們其實可以認為，將N、Q、T看作一個整體的話，那麼圖靈機就是在這個離散集上的群作用G（當然，既然s本身是部分函數的話，所以嚴格說來其實這里也不能稱為是群作用，只能視為某種morph吧）：
對於初始狀態S_0，圖靈機可以看作S_n = G^n S_0。然後存在狀態判定函數check，判斷S_n是否符合某組特徵，如果符合則停機。

當然，上面這種全部混搭在一起的觀點未必能把問題都看清楚，所以我們還是保留N、Q、T的三元結構，N不再記錄狀態和數據，而僅僅給出不同狀態和數據之間的「相鄰」關系。
我們可以很顯然地看到，T其實和N是很有強關系的。雖然可以接受的字元的全體構成T，但N的不同位置上的T的元素數據t，卻是和N的元素位置n「綁定」在一起的。
而，另一方面，Q的元素，圖靈機的狀態q，卻和N或者T都沒有太明顯的關系，一台圖靈機只有一個狀態q。
這樣的情況可以和物理上的一些情況做個類比：
假定N是時空背景，T是某個規范場的勢能，而Q是一個粒子M和這種規范場耦合的荷。M在N上運動，遇到勢T(n)，改變規范場的同時自己也被作用，從而軌跡不斷地被修正，因此整個運動過程可以看作是一個粒子M與規范場T不斷相互作用的過程，M在N上的位置不斷被修改，Q和T也不斷被修改。狀態轉移規則s在此就是規定了如何相互作用的規則。

當然了，實際上圖靈機和規范場論的相似性也就僅僅停留於此了。嚴格的規范場論，Q、T和s之間的耦合是非常嚴密的，從而這三者都不會如圖靈機一般自由。但，如果我們摒棄規范場的想法，僅僅是從纖維叢的角度來考慮的話，則會發現，或許圖靈機和物理之間的差異，也沒那麼大。
從纖維叢的角度來看，圖靈機就是一個不斷改變著纖維叢截面和自身所帶荷的在背景時空上運動的粒子，而規范場論和圖靈機的區別在於，規范場論的背景時空與纖維都是連續的，滿足特定的群結構，勢與粒子的作用關系滿足一套物理預設；而圖靈機的背景時空與纖維則是離散的，且不滿足群結構，也不滿足那套物理預設。如果不考慮纖維叢是離散的還是連續的這點，那麼我們可以說圖靈機的范疇比規范場論的范疇更大。

下面，我們來考慮上述模型下，圖靈機工作的時候是怎麼樣一個樣子。

我們先將狀態轉移規則s分解為兩部分：S_Q和S_T。
他們都是Q × T × N的函數，且有：

其中，對於Q部分，如果根據狀態轉移規則s，圖靈機的讀寫頭應該左移（-1）或者右移（+1）的，那麼就有：

現在，我們可以做一個一般化：
將Q和T看作是同一個空間的兩個字空間，從而（跟隨讀寫頭所在位置的）狀態q和（記錄在底流形N的每個點上所有的矢量空間內的）狀態t可以看作是一個更大的矢量空間中矢量v的兩個不同方向上的分量。
因此，我們可以將動力學方程寫為：

且當我們知道讀寫頭的移動dn後，上述方程可以寫為：

這樣的空間和函數總是可以構造出來的，因為它不過就是原本狀態轉移規則加上一些額外規則後的一個變種罷了。

下面，我們將其「連續」化，並引入可以在N上任意移動而不單單是左右移一格的模型（並略作調整）：

這樣一來，我們基本上就得到了一個最一般化的、連續空間中的類圖靈機的概念模型。
而，如果我們將移動局限在n的領域，而非全空間，那麼在進行恰當的調整悉數後，上面的積分方程（在一類不那麼變態的函數S的情況下）可以被寫成如下的微分方程：

於是，現在整個模型就是這樣的：
一個連續空間N上有一個纖維叢V，然後類圖靈過程就是在這樣一個纖維空間上的熱擴散過程。
當然，和真正嚴格意義上的圖靈機相比，除了現在底流形和纖維從離散變成了連續外，狀態轉移規則s也變成了傳播子S，且支持更豐富類型的狀態轉移。
而，一個標准圖靈過程現在就是在纖維叢N × V上一個初始區域出發，經過一系列擴散過程後，終止與某個特殊的末態位置，其中該末態位置的矢量v滿足v的Q部分為結束狀態q_stop。
在這個模型下，NTM（非確定圖靈機）可以看作這個纖維空間上的路徑積分。
因此，NTM=DTM的本質就是說：如果一個NTM可以來到某個停機區域中的位置，那麼必有一根經典路徑，其對應一台DTM，也可以在該位置停機。
由於NTM僅僅是給出了多DTM同時擴散，彼此之間沒有相互作用，所以NTM=DTM並沒有什麼好驚訝的。

在上面的模型中，一個NTM其實等於將DTM所處的纖維叢進行了又一次的擴大，從一個q擴展為多個q：q1, q2, q3...qn，從而彼此之間其實沒有耦合，NTM可以從源擴散到目標區域，僅僅是因為源比較多，擴散起來比較「全面」，但本質上和DTM沒有不同。

既然已經推廣到這樣了，那麼讓我們接著推廣：假定現在允許多台連續纖維空間中的類圖靈機同時進行運行，或者說在這個纖維空間中有多個源同時進行擴散，並且傳播子S1和S2之間存在耦合，比如簡單的耦合是所有的傳播子S公用同一個Q區域，於是一台S對V的修改可以影響到另一台S。
當然，這個問題在標准圖靈機模型下，本質上不會改變什麼，因為多台圖靈機和一台圖靈機在標准圖靈機模型下是沒有根本性差別的。
因為，在離散的情況下，我可以讓一個圖靈機記下所有多台圖靈機的狀態，然後模擬每一台的每一步運算，從而將多台同時處理變成一台分步處理，本質上沒有什麼區別。
那麼，在連續空間的情況下，會如何呢？理論上來說，依然沒有本質上的突破。

在現在的模型下，兩台機器（未必是圖靈機，而是這里的類圖靈機，從概念上說更類似 RealMachine ，當然，不是「真實的機器」的意思）如果從任意一個位置作為源，並且當一台在有限時間t1時候，另一台總能在有限時間t2，使得兩者在底流形指定區域內的纖維界面相同，那麼這兩者等價。
因此，上面的問題就變成了：對於任意一組傳播子S的多源擴散，是否總可以找到一個傳播子S，使得單源擴散可以在上述等價的意義上給出等價的結論？
這個就未知了。

如果，進一步，我們為S引入隨機性，並且整個纖維空間都存在熱噪音——每個點上的隨機擴散運動，那麼上述等價意義上的NTM和DTM之間，對於現在的連續纖維叢上的類圖靈機，是否還能給出等價的結論呢？

而且，假定這樣現在傳播子可以判斷何時「放大」熱噪音，何時「抑制」熱噪音的話，這樣的系統不是很奇妙么？

當然，我們知道，對於 RealMachine ，由於熱噪音和計算精度的要求，我們事實上總是會對輸入和輸出進行「離散化」處理的。
因此，前面定義的類圖靈機在輸入和輸出都離散化的情況下，是否可以和某台標准圖靈機對應呢？
顯然，如果這台類圖靈機不停機，而是一直輸出內容的話，就不會和標准圖靈機等價。而，現實世界的libev和uv庫告訴我們，永不停機，其實未必是壞事。

另一方面，計算精度有的時候並不是必須要考慮的東西。
如果我們的計算本身只要求一個大概的分布，而不要求精確值的話，也就是我們處理的是fuzzy function與fuzzy logic，那麼精確並不是必須的，從而整個計算過程並不要求離散化，至少對輸入不作要求，只要在輸出的時候離散化到某幾個特定范疇。這樣的話，由於計算精度要求帶來的約束就可以放寬。

對於熱噪音也是如此，如果S可以根據要求，在某些時候「放大」噪音的空閑，某些時候「抑制」噪音的貢獻，將噪音作為隨機源，甚至是不能作出決策時的決策，那麼噪音也未必就一定要通過離散化給消去。

因此，對RealMachine的約束要求，現在看來，未必就是必然將這里的類圖靈機退化還原到圖靈機的要求——只要我們不要求絕對精確的計算，即可。

這樣的思維產物到底是否真正突破了圖靈機的局限，從而可以和更加精妙的機器，即，我們的人腦，相媲美呢？
這個就很難說啦。

好，睡前嘮叨結束。

Ⅳ 圖靈機的數據和代碼存在哪

理論計算機科計算性概念與嚴格數描述算解證明系列重要數問題眾所周知事實直1935著名算計算函數遞歸函數教論文提算計算性直觀概念精確數刻畫需要指哥德爾（KGDEL）於1931引進原始遞歸函數概念明確給般遞歸函數定義1934前與教1934春（A教）要討論問題何讓精確數算計算定義哥德爾沒及竹崎主題圖靈加贊賞接受丘奇 - 圖靈論文
我認重要原圖靈構思想完全沿著摹DEL給定算概念析第澄清圖靈機內涵概念式系統概念;20想圖靈論文指該機做計算系統物理世界討論引發信息革命 - 腦 - 計算機圖靈論文揭示事實絕哥德爾承認計算性依賴於系統概念
使用計算機發展摩爾定律假設普遍認幾素更理論實際意義計算機發展表明摹德爾圖靈工作贊賞世紀80代始討論何超越圖靈計算算或計算純粹抽象數概念實施案物理定律作自結自規律計算系統特別丘奇 - 圖靈論文結論物理原理更比1985奇（D.Deutsch）建議由教 - 圖靈論題物理版本（稱奇原則）基於原則量計算機計算本質自1990關注焦點我相信今認知科認知計算研究計劃提質疑更必要澄清教內涵 - 圖靈論題奇數原則必要量計算機計算本質適邏輯析
1哥德爾提教主題
歷史迪特金（R.Dedekind）皮亞諾（G.Peano）司寇倫（T.Skolem）希爾伯特（D.Hilbert）阿克曼（W.Ackermann）研究遞歸函數哥德爾確切定義概念今我所說原始遞歸函數介紹哥德爾文章程碑意義論文19312月至19345月哥德爾普林斯頓研究所講座系列完整結引入般遞歸函數概念：
般遞歸函數（我現稱原始遞歸函數）具重要特點通限程每參數設置值計算值函數
歷史悠久手段哥德爾相建設性說明（著名腳注3）本補充：
逆命題每函數計算限程序原始遞歸函數似乎真實除[原創]遞歸...其形式遞歸（例與另外兩變數應遞歸）否允許由於差計算概念沒定義命題逆能證明幫助檢測原則 [6]
哥德爾腳注戴維斯（馬丁·戴維斯）認種形式教論文即使名稱哥德爾其表達主題：
每機械計算函數般遞歸函數定義
編譯判定介紹哥德爾演講徵文戴維斯表示見解草案發送哥德爾評價完全相反戴維斯意外哥德爾發表同意見問題復：
注3教論文說確說我都超提限計算性計劃遞歸程相於猜想系列講座我沒想我遞歸概念包含所能遞歸[3]
信至少我看GDEL今遞歸函數定義給1934春完全沒猜定義廣泛包容切遞歸認自算計算性猜測（即Davis說G德爾主題）教論文等價說作種輔助手段探索原則幫助尋求算數計算性概念滿意表徵
2升定義教主題
教宣布論文19354月美數第份報告事實教首先關注計算性進行升定義概念根據聲明教鎳（SCKleene）科林1933教L定義熟概念傳播普林斯頓邏輯家猜測L-自定義函數算計算函數並終提題科林鎳憶說：
堂提題我准備使用偽造角化想指算計算函數超L-自定義函數類我快意識能所晚間我題支持者教[9]
戴維斯考察雖教1933至1934明顯計算性概念濃厚興趣直哥德爾普林斯頓系列講座沒明確跡象表明認算計算性與某種嚴格致數概念涉及任何特別要說許討論與哥德爾2月 - 19345月立明確說給教論文 193511月29科林鎳信教給些模糊說：
談哥德爾遞歸函數算計算段歷史初概念與哥德爾升討論定義概念我找定義算計算性我建議使用l定義作定義哥德爾認完全合適我說提供任何即使令滿意定義部我證明必須包括l定義概念摹德爾唯想候第算計算性陳述確定概念描述概念公認特徵公理做其事情基礎顯認計算性概念厄爾·布朗向沿（J.Herbrand）提遞歸函數概念特別指意義遞歸算補充說認兩概念計算性令滿意相互致認意義幫助除非檢測[3]
教數界1935宣布論文表情：建議采礦納厄爾布朗重要面已經於1934修訂系列講座哥德爾遞歸函數定義拍攝本質摹DEL整數遞歸函數定義需要強調整數算計算函數確定致遞歸函數算計算像真定義原口概念所要遞歸等價性或弱於遞歸[3]
顯教並沒提論文L定義術語使用術語厄爾尼諾 - 布朗哥德爾般遞歸函數候定義性暗示繪制算計算合理定義措辭給印象1935春教沒確定升定義性厄爾·布朗 - 哥德爾般遞歸相於直19364月初等數論教解決問題結論升自定義功能般遞歸函數
1936論文教給我現都知道教論文語句標准：現我貫遞歸函數整數（整數l自定義功能）概念定義算計算概念已經討論積極整數選定義致計算性與直觀概念認具通認證[1]
教間等價算計算性遞歸性稱定義（E.Post）1936所定義基準應僅作工作假設看曾極力反科林鎳指1943等價命題描述包含強工作假說特點我必須相信充理由建議使用詞表達種主張主題
雖教主題哥德爾計算性與遞歸贊或l定義性等效聲明看前公理描述算計算性概念包含沒找公認特點能嚴格數定義完全滿意直1936圖靈（A.Turing）公布結哥德爾承認已經克服困難
3哥德爾升值圖靈論文
我認1934至1936教堂科林Ni哥德爾計算性概念數描述做系列工作並終教提標准形式教主題期間圖靈完全獨立普林斯頓數家思考計算性問題終特徵算通用圖靈機計算性概念即算計算通用圖靈機實現圖靈論題表示所示：
每算編程通用圖靈機
哥德爾1965普林斯頓講義（1934）記圖靈工作給予高度評價哥德爾接受教主題贊賞圖靈論文主要理由至少我認點：
（1）澄清概念式系統通用圖靈機概念
說事實證明哥德爾完備性定理系統形式仍相模糊概念否則哥德爾採取更加簡潔式證明定理圖靈機概念形式更清楚更准確握規系統系統特性產定理機械程序圖靈機工作案數家實際工作系統程形式或者式系統允許做選擇按照與預定范圍內圖靈機些步驟虧圖靈機概念哥德爾完備性定理數形式系統同圖靈機程序式版本版本停機問題復雜性理論算信息性版本 [10]
（2）圖靈貼近G結論沿德爾設想
精道優雅教工作完全純粹數析基礎圖靈析並局限於世界數形式值稱道理念應用程序實例 [3]外圖靈設想沿著密切哥德爾研究作結論哥德爾曾評論說圖靈工作概念機械程序（稱算計算程序或相結合程序）提供析概念圖靈機等效前等價定義計算性任何情況少適用於我初目 [2]
哥德爾說：顯已經定義概念主張優先算計算初衷考慮能夠描述概念認識特徵集公理基礎做些事情看尋求確計算嚴格數描述圖靈並沒使用任何式意義言自明處理??問題指算計算公認特點避免導致某類功能精確定義??類功能圖靈給定圖靈機機械程序概念清晰准確表達局部遞歸函數般遞歸函數圖靈機哥德爾圖靈准確概念與比賽令信服理由直觀概念使用圖靈機程序或圖靈機實現獨特概念算計算性特點都確符合我初衷
（3）圖靈機計算概念揭示計算取決於該系統形式事實即
使我進步看圖靈哥德爾重要工作應該檢查哥德爾理解絕計算性概念 6月191935哥德爾證明維納報告度指所謂加速定理[7]定理嚴格語句用於系統S種形式函數φ（ x）計算概念指每數M數字n應φ（M）=證明系統滿足每系統系統相比前更式系統序列S1S2 ...表示Si函數計算我依賴
份報告哥德爾附加絕計算性：能注意即使超級差計算函數計算式系統硅注意事項S1計算某種意義說計算概念絕現實所其知名元數概念（允許定義）完全依賴於給定系統
哥德爾絕意義理解計算致1934至1935於1946普林斯頓數問題思考誕辰200周紀念GDEL已特別強調絕意義：
我看般遞歸或圖靈機計算概念極端重要性似乎歸於事實概念第功給定意義認識論概念絕定義計算取決於式制度選擇判定或定義定義舉例說像前處理所其情況依靠給定語言盡管絕計算判定性概念種特殊情況已經完全與往同[8]
（4）圖靈機計算系統物理世界概念
另G德爾值稱道圖靈工作能原20世紀20代想圖靈指電腦做計算系統物理世界或者否計算問題轉化問題實現物理引發信息革命 - 腦 - 計算機辯論圖靈指所形式化描述算東西快速准確找通用圖靈機計算機種特殊情況原則已經辟新代類智慧機模擬圖靈計算說親自研究計算積極性僅形式精神科哥德爾甚至增減直晚探索 - 腦 - 計算機所提圖靈興趣題我害怕於智科情所鍾
5丘奇 - 圖靈論文物理版本量計算機計算本質
完全幾素G德爾升值圖靈現代計算機理論發展基礎力第台通用電計算機物理設備真讓看通用圖靈機（限存儲空間）物理實現起始認現實世界計算論物理模擬客觀現實理想模擬機原理客觀世界通用圖靈機模擬范圍外呢面相部物理家樂觀態度1985奇教授牛津引進挑釁教 - 圖靈論題物理版本取代能做點物理系統實現限計算函數闡述所謂奇原則（稱物理教堂 - 圖靈原則）：每限物理系統實現通用模擬機總限操作模式完全模擬[4]我知道根據現代物理物物理許物理家認巨體身體我身體命直類腦限物理系統實現系統根據 - 奇見些原則使用於通用計算機操作系統限式完美模擬
顯奇原理代表教 - 圖靈論題工作假說教堂 - 圖靈論題奇原則我計算領土斷擴奇原則確顯示物理現實深刻性物理主義計算立場完全工智能專家工作假說追求核 DOCH其算計算純粹抽象數概念物理定律體現計算系統研究律本質自結看通用概念電腦僅確認律性質且能自則內要求事實我知道所宣傳虛擬現實技術工命工智能相信真理原則奇怪沒任何確鑿科證據反駁奇原則全名普遍通用模擬機模擬機概念原則實現算（程序）數量限命題
量計算機支持者宣稱按照理論計算機能夠實現奇原則通用模擬機新進展能量通用圖靈機量場旗手傑拉爾德·米爾本（GLMilburn）指1998作物理理論物理版本教 - 圖靈論題密切相關事實即所觀察數據物理理論數些數據數據我稱計算問題所些數據通用圖靈機運行算論古典或量物理系統任意精度高模擬某些問題程序運行間能世界經典效模擬蒙特卡羅隨機性世界約隨機性量能用解釋量隨機性基於經典隨機性隱藏文數字變數量世界游戲需要遵循費曼規則實現種解決問題建造台量計算機量程本身作計算裝置使用計算基本步驟原或亞原水平弗曼（R.Feynmen）1998教 - 圖靈論題奇原則已糾：
限所描述結通用量計算機物理測量系統模擬完美運行限式記錄測量結終產品
限描述物理測量系統指建立並操縱測量裝置命令必須能夠使用限代碼表達;完美類似物指與實際測量獲數據產模擬數據能區;產品指所模擬測量必須定間結束再繼續產新結
超越傳統計算機量計算機其計算本質呢
首先量計算機完經典計算機完計算：例任意精度模擬量物理系統解決案隨間呈指數增問題例完解64位數字計算首要素產品甚至使用超級計算機花費更間比宇宙齡彼·肖爾貝爾實驗室（彼·肖爾）量算相短間內產品首要素解64位量計算機依賴於規模量糾纏功超越經典圖靈機量計算機並行計算產量相乾性力量
量計算機實現計算物理設備運行物理系統量物理量計算機律建立現代計算機量圖靈機基礎通用圖靈機算完全確定確定算圖靈機前列印狀態前存儲單元內容間安排狀態部運完全確定古典概率算前狀態所述存儲單元前內容定圖靈機定概率轉換狀態部運完概率函數值實數[0,1]完全確定圖靈機概率性質量計算機與經典概率圖靈機唯同前列印狀態前存儲單元內容量態經典交狀態（0,1）（0,1,01機疊加態） 並值概率復雜??振幅函數概率函數性質量計算機確定由概率幅功能高效計算量計算機做完全益於量疊加效應即原狀態01疊加狀態概率般情況使用L量比特量計算機2L數量處理間完相於通經典計算機2L數計算計算步驟量計算機量態應計算機數據程序（需要更換經典位量比特）部物理狀態量物理所描述由量物理力機制機器更重要問題我必須說明輸我需要經典位量比特要解決棘手退相干
我必須清醒認識論量計算機速度快理論量計算機量圖靈機受哥德爾量計算機邏輯限制限制計算功能計算解決停機問題說底量計算機計算本質仍圖靈機遞歸函數計算所丘奇 - 圖靈論文仍量計算機理論基礎嘗試整物理世界奇納入計算范圍嘗試仍擺脫終量計算機模擬智能內邏輯計算哥德爾說種形式系統依賴於絕概念量計算機另種計算更快計算載體
值深思否計算技術懈追求使我能夠效捕捉真致程序完整世界性質問題提供科答否任何邏輯障礙[11]除圖靈機其計算模型DNA計算機存靈能超圖靈機機器DOCH原則告訴我僅物理確定計算機做事情反電腦做決定終物理性質律絕僅限於計算載體變化要指現實世界物理世界世界奇原則意圖明顯

Ⅳ 圖靈機與現代計算機的關系

圖靈機的意義與思想內涵：


圖靈提出圖靈機的模型並不是為了同時給出計算機的設計，它的意義我認為有如下幾點：

1、 它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、 圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、 圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

對圖靈機給出如此高的評價並不是高估，因為從它的設計與運行中，我們可以看到其中蘊涵的很深邃的思想。

通用圖靈機等於向我們展示這樣一個過程：程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。

另外，我們可以隱約看到現代計算機主要構成（其實就是馮諾依曼理論的主要構成），存儲器（相當於存儲帶），中央處理器（控制器及其狀態，並且其字母表可以僅有0和1兩個符號），IO系統（相當於存儲帶的預先輸入）；

(5)圖靈機的數據在哪裡擴展閱讀：

圖靈機，又稱圖靈計算、圖靈計算機，是由數學家艾倫·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人們進行數學運算。

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。

在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

圖靈機有很多變種，但可以證明這些變種的計算能力都是等價的，即它們識別同樣的語言類。證明兩個計算模型 A 和 B 的計算能力等價的基本思想是：用 A 和 B 相互模擬， 若 A 可模擬 B 且 B 可模擬 A， 顯然他們的計算能力等價。注意這里我們暫時不考慮計算的效率，只考慮計算的理論上「可行性」。

首先我們可以發現，改變圖靈機的帶字母表並不會改變其計算能力。例如我們可以限制圖靈機 的帶字母表為 {0,1}，這並不會改變圖靈機的計算能力，因為我們顯然可以用帶字母表為 {0,1} 的圖靈機模擬帶字母表為任意有限集合 Γ 的圖靈機。

另一個要注意的是，如果我們允許圖靈機的紙帶兩端都可以無限伸展，這並不能增加圖靈機的計 算能力，因為我們顯然可以用只有紙帶一端能無限伸展的圖靈機來模擬這種紙帶兩端都可以無限 伸展的圖靈機。

如果我們允許圖靈機的讀寫頭在某一步保持原地不動，那也不會增加其計算能力，因為我們可以用 向左移動一次再向右移動一次來代替在原地不動。

郵局發行與零售發行相結合的發行方式

郵局發行：國家郵局強大發行體系確保廣大讀者能及時和穩定地得到《現代計算機》。其覆蓋面和影響力不僅服務大中城市和發達地區，而且照顧到各邊遠地區。

零售發行：遍布城市大街小巷的報刊零售攤點既能補充郵發渠道，更能方便靈活地服務於廣大電腦愛好者。

此外，讀者服務部郵購起到拾遺補缺的作用；向電腦領域有關人士和相關電腦軟硬體公司定向贈閱，確保對信息產品的購買和應用有直接或間接影響力的人及時閱讀到《現代計算機》雜志，並使對信息產品和技術感興趣的潛在用戶隨時了解其中的產品和信息。

讀者分布及發行范圍

《現代計算機》由於其准確的定位及實用新穎的風格受到廣大讀者和市場的認可，而且有進一步快速增長的勢頭。

根據發行部的統計，《現代計算機》雜志的發行范圍已基本覆蓋到全國所有省份（除台灣外），一般較集中於各大中城市及縣級城市。雜志讀者群的年齡范圍主要集中在15～35歲之間，讀者的職業范圍主要集中在學校、家庭、辦公室。

Ⅵ 圖靈機在計算機發展史上主要貢獻是什麼

它的意義有如下幾點:

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

通用圖靈機向人們展示這樣一個過程:程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。更重要的是，隱約可以看到現代計算機主要構成，尤其是馮・諾依曼理論的主要構成。

(6)圖靈機的數據在哪裡擴展閱讀：

圖靈機是中央處理器（CPU）的一般示例，該處理器控制計算機完成的所有數據操作，而規范機則使用順序存儲器來存儲數據。更具體地說，它是一種能夠枚舉字母表中有效字元串的任意子集的機器（自動機）；這些字元串是遞歸枚舉集的一部分。圖靈機具有無限長的磁帶，可以在其上執行讀取和寫入操作。

假設黑匣子，圖靈機無法知道它最終是否會使用給定程序枚舉子集的任何特定字元串。這是由於無法解決暫停問題，這對計算的理論限制具有重大意義。

Turing機器能夠處理不受限制的語法，這進一步意味著它能夠以無數種方式穩健地評估一階邏輯。通過lambda演算可以證明這一點。

能夠模擬任何其他圖靈機的圖靈機稱為通用圖靈機（UTM，或簡稱為通用機）。用類似的「通用」性質更數學導向的定義是由引進邱奇，上演算，其工作的正式理論與圖靈的交織在一起計算被稱為教會圖靈論題。

Ⅶ 馮·諾伊曼計算機體系結構是如何實現圖靈機模型的

體系結構編輯
(1)採用存儲程序方式，指令和數據不加區別混合存儲在同一個存儲器中，（數據和程序在內存中是沒有區別的,它們都是內存中的數據,當EIP指針指向哪 CPU就載入那段內存中的數據,如果是不正確的指令格式,CPU就會發生錯誤中斷. 在現在CPU的保護模式中,每個內存段都其描述符,這個描述符記錄著這個內存段的訪問許可權(可讀,可寫,可執行).這最就變相的指定了哪個些內存中存儲的是指令哪些是數據）
指令和數據都可以送到運算器進行運算，即由指令組成的程序是可以修改的。
(2)存儲器是按地址訪問的線性編址的一維結構，每個單元的位數是固定的。
(3)指令由操作碼和地址組成。操作碼指明本指令的操作類型,地址碼指明操作數和地址。操作數本身無數據類型的標志，它的數據類型由操作碼確定。
(4)通過執行指令直接發出控制信號控制計算機的操作。指令在存儲器中按其執行順序存放，由指令計數器指明要執行的指令所在的單元地址。指令計數器只有一個，一般按順序遞增，但執行順序可按運算結果或當時的外界條件而改變。
(5)以運算器為中心，I/O設備與存儲器間的數據傳送都要經過運算器。
(6)數據以二進製表示。

4特點編輯
(1)計算機處理的數據和指令一律用二進制數表示
(2)順序執行程序
計算機運行過程中，把要執行的程序和處理的數據首先存入主存儲器（內存），計算機執行程序時，將自動地並按順序從主存儲器中取出指令一條一條地執行，這一概念稱作順序執行程序。
(3)計算機硬體由運算器、控制器、存儲器、輸入設備和輸出設備五大部分組成。[3]

5作用編輯
馮.諾依曼體系結構是現代計算機的基礎，現在大多計算機仍是馮.諾依曼計算機的組織結構，只是作了一些改進而已，並沒有從根本上突破馮體系結構的束縛。馮.諾依曼也因此被人們稱為「計算機之父」。然而由於傳統馮.諾依曼計算機體系結構天然所具有的局限性，從根本上限制了計算機的發展。
根據馮·諾依曼體系結構構成的計算機，必須具有如下功能：把需要的程序和數據送至計算機中。必須具有長期記憶程序、數據、中間結果及最終運算結果的能力。能夠完成各種算術、邏輯運算和數據傳送等數據加工處理的能力。能夠根據需要控製程序走向，並能根據指令控制機

馮· 諾依曼體系結構[3]
器的各部件協調操作。能夠按照要求將處理結果輸出給用戶。[2]
將指令和數據同時存放在存儲器中，是馮·諾依曼計算機方案的特點之一計算機由控制器、運算器、存儲器、輸入設備、輸出設備五部分組成馮·諾依曼提出的計算機體系結構，奠定了現代計算機的結構理念。[4]

Ⅷ 圖靈機與馮諾依曼結構計算機

圖靈機（英語：Turing machine），又稱確定型圖靈機，是英國數學家艾倫·圖靈於1936年提出的一種將人的計算行為抽象掉的數學邏輯機，其更抽象的意義為一種計算模型。

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

為了模擬人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號表示空白。紙帶上的格子從左到右依次被編號為0, 1, 2, ...，紙帶的右端可以無限伸展。
一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

一套控制規則TABLE。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態寄存器的值，令機器進入一個新的狀態，按照以下順序告知圖靈機命令：

一個狀態寄存器。它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。參見停機問題。

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設備。圖靈認為這樣的一台機器就能模擬人類所能進行的任何計算過程。

圖靈機看起來簡單，但是功能非常強大。它把計算思維用形式化語言描述，從而模擬人類的計算方法，為設計計算機提供了理論基礎。

馮·諾依曼（John von Neumann，1903年12月28日-1957年2月8日），美籍匈牙利數學家、計算機科學家、物理學家，是20世紀最重要的數學家之一。 馮·諾依曼是布達佩斯大學數學博士，在現代計算機、博弈論、核武器和生化武器等領域內的科學全才之一，被後人稱為「現代計算機之父」、「博弈論之父」。

數學家馮·諾依曼提出了計算機製造的三個基本原則，即採用二進制邏輯、程序存儲執行以及計算機由五個部分組成（運算器、控制器、存儲器、輸入設備、輸出設備），這套理論被稱為馮·諾依曼體系結構。

先來看看計算機各個功能部件的作用。

計算機使用二進制邏輯有很多好處，利於數據的傳輸、儲存、表示。例如用高電平表示1，用低電平表示0。由此可以建立數字邏輯系統，用簡單的物理元件組合表示更復雜的運算和處理。

程序控制是計算機體系結構里的一個核心思想。先把指令和數據都存放在存儲器中，然後根據指令的地址取出指令，經過解碼產生不同的控制信號，實現對計算機的控制，完成指令的功能。

把存儲器里的信息分為指令和數據是很有必要的。指令就是指揮機器工作的指示和命令，程序就是一系列按一定順序排列的指令，執行程序的過程就是計算機的工作過程。數據是被操作的內容。

計算機可以從時間和空間兩方面來區分指令和數據。在時間上，取指周期從內存中取出的是指令，而執行周期從內存取出或往內存中寫入的是數據；在空間上，從內存中取出指令送控制器，而執行周期從內存從取的數據送運算器、往內存寫入的數據也是來自於運算器。

把圖靈機和馮諾依曼計算機做個對比：
圖靈機的紙帶 ≈ 存儲器，
讀寫頭 ≈ MAR MDR 寄存器，
控制規則 ≈ 運算器+控制器，
狀態 ≈ 時序+各種寄存器。

個人認為，圖靈機是對於人類計算思維的理論模型，馮諾依曼計算機是通用圖靈機的工程化實現。

Ⅸ 哪位大神幫一下忙

這么多人參加啊，不會你們全年級的人都參加吧。既然問題已經提出來了，那我就給你耐心的解答一下，由於人數眾多，賽程較短，在7強前建議進行一局淘汰制。
先對參賽隊員編號，之後抽簽，捉對單局淘汰，這樣第一天幾乎男女單打、混雙前7應該能出來。第二天就是水平較高的之間三局兩勝的對決，也實行淘汰制。

Ⅹ 計算機又稱為圖靈機或馮諾依曼機是為什麼

因為圖靈機(馮諾依曼發明)是有史以來第一次把計算機劃分為處理器、存儲器、輸入輸出設備等幾大模塊，並且對各模塊間的協同工作做了嚴格的定義。現代計算機就是在這個基礎上發展起來的，所以在計算機或者科研等比較專業的行業有時會把計算機稱為圖靈機或馮諾依曼機，以示對馮諾依曼偉大發明創造的尊崇。