背景

Von-Neumann架構(gòu)描述了存儲(chǔ)程序計(jì)算機(jī)，其中指令和數(shù)據(jù)存儲(chǔ)在存儲(chǔ)器中，并且機(jī)器通過改變其內(nèi)部狀態(tài)來工作，即指令對(duì)一些數(shù)據(jù)進(jìn)行操作并修改數(shù)據(jù)。因此，系統(tǒng)中存在狀態(tài)。

圖靈機(jī)架構(gòu)通過操縱磁帶上的符號(hào)來工作。即存在具有無限數(shù)量的槽的磁帶，并且在任何一個(gè)時(shí)間點(diǎn)，圖靈機(jī)都在特定的槽中。根據(jù)在該插槽讀取的符號(hào)，機(jī)器可以更改符號(hào)并移動(dòng)到不同的插槽。所有這些都是確定性的。

問題

這兩個(gè)模型之間有什么關(guān)系嗎？馮·諾伊曼模型是基于圖靈模型還是受其啟發(fā)？

我們可以說圖靈模型是Von Newman模型的超集嗎？

功能編程是否適合圖靈模型？如果是這樣，怎么樣？我假設(shè)

功能性編程并不適合Von Neuman模型。

圖靈機(jī)是發(fā)明的理論概念，用于在數(shù)學(xué)上探索可計(jì)算問題的領(lǐng)域并獲得描述這些計(jì)算的方法。

Von-Neumann架構(gòu)是用于構(gòu)建實(shí)際計(jì)算機(jī)的架構(gòu)(其實(shí)現(xiàn)圖靈機(jī)在理論上描述的內(nèi)容)。

函數(shù)式編程基于lambda演算，這是描述計(jì)算的另一種方法，或者更準(zhǔn)確地說是可計(jì)算的函數(shù)。雖然它使用了一種完全不同的方法，但它對(duì)圖靈機(jī)也同樣強(qiáng)大(據(jù)說它是完整的)。

每個(gè)lambda演算程序(術(shù)語)T僅使用組合來編寫

變量如x

像λx. T這樣的匿名函數(shù)

功能應(yīng)用T T

盡管是無狀態(tài)的，但這對(duì)于計(jì)算機(jī)可以進(jìn)行的每次計(jì)算都是足夠的。圖靈機(jī)和lambda術(shù)語可以相互模擬，Von-Neumann計(jì)算機(jī)可以同時(shí)執(zhí)行(除了提供無限存儲(chǔ)等技術(shù)限制，圖靈機(jī)可能需要)。

但是由于其無狀態(tài)和更抽象的性質(zhì)，功能性程序在Von-Neumann計(jì)算機(jī)上的效率可能會(huì)降低，而且與按照二進(jìn)制，內(nèi)存和更新方式遵循的命令式程序相比，不那么"直觀"。

清晰的擴(kuò)張。但是，Von Neuman架構(gòu)能否實(shí)現(xiàn)圖靈機(jī)所能描述的一切？

@Santosh：理論上，沒有真正的真實(shí)計(jì)算機(jī)可以做到這一點(diǎn)，也沒有人會(huì)這樣做 - 因?yàn)閳D靈機(jī)需要無限量的存儲(chǔ)空間。

@Santhosh，邁克爾：嗯，好點(diǎn)。編輯了答案。

任何圖靈可計(jì)算功能必須由停止的圖靈機(jī)描述。停止的圖靈機(jī)不需要無限存儲(chǔ)(如何在有限的時(shí)間內(nèi)讀取或?qū)懭霟o限多的數(shù)據(jù)？)。因此，理論圖靈機(jī)可計(jì)算的任何東西都可以由具有足夠存儲(chǔ)空間的實(shí)際計(jì)算機(jī)計(jì)算。所需的存儲(chǔ)空間可能是任意大的，但不會(huì)是無限的。

@Tyler：不是一個(gè)無限循環(huán)圖靈可計(jì)算的嗎？當(dāng)然它不會(huì)停止......

@Dario：不是在"可計(jì)算"的形式意義上它不是。圖靈可計(jì)算函數(shù)被定義為函數(shù)f，對(duì)于每個(gè)輸入n，存在停止并輸出f(n)的圖靈機(jī)。它幾乎就是"算法"的同義詞，算法定義的一個(gè)部分是它必須有有限的許多步驟，而無限循環(huán)則不然。

@Tyler：不應(yīng)該是"存在一個(gè)圖靈機(jī)，對(duì)于f域中的每個(gè)n，停止并輸出f(n)"？我不認(rèn)為f允許每個(gè)輸入都有一個(gè)單獨(dú)的圖靈機(jī)。

@Michael是的，你是對(duì)的;我的措辭混亂了。接得好。

@Dario是基于Von-Neumann架構(gòu)的現(xiàn)代計(jì)算機(jī)嗎？如果最后一個(gè)問題的答案是肯定的：你還說Von-Neumann架構(gòu)實(shí)現(xiàn)了圖靈機(jī)模型，但我認(rèn)為現(xiàn)代計(jì)算機(jī)是基于RAM而不是基于圖靈機(jī)模型的？

一般來說，一個(gè)是指馮·諾依曼建筑，與哈佛建筑形成鮮明對(duì)比。前者具有以相同方式存儲(chǔ)的代碼和數(shù)據(jù)，而后者具有用于代碼和數(shù)據(jù)的單獨(dú)的存儲(chǔ)器和總線路徑。所有現(xiàn)代臺(tái)式電腦都是Von Neumann，大多數(shù)微控制器都是哈佛。兩者都是試圖模仿理論圖靈機(jī)的現(xiàn)實(shí)世界設(shè)計(jì)的例子(這是不可能的，因?yàn)檎嬲膱D靈機(jī)需要無限的存儲(chǔ)器)。

感謝哈佛建筑與圖靈機(jī)的對(duì)比

@Santhosh：也許這只是一個(gè)錯(cuò)字，但我沒有提出任何這樣的對(duì)比。正如我在回答中所說，Von Neumann和Hardvard架構(gòu)都是圖靈機(jī)器。它們之間的對(duì)比是它們的內(nèi)存布局。

我不知道圖靈機(jī)和馮諾伊曼架構(gòu)之間有什么歷史關(guān)系。然而，我確信馮·諾伊曼在開發(fā)馮·諾伊曼建筑時(shí)意識(shí)到了圖靈機(jī)。

然而，就計(jì)算能力而言，圖靈機(jī)和馮·諾伊曼機(jī)器是等價(jià)的。任何一方都可以模仿另一方(IIRC，在圖靈機(jī)上模擬von Neuman程序是O(n ^ 6)操作)。以lambda演算形式的函數(shù)式編程也是等價(jià)的。實(shí)際上，至少與圖靈機(jī)一樣強(qiáng)大的所有已知計(jì)算框架都是等效的：

圖靈機(jī)

Lambda演算(函數(shù)式編程)

馮諾伊曼機(jī)器

部分遞歸函數(shù)

可以使用任何這些模型計(jì)算的函數(shù)集沒有區(qū)別。

函數(shù)式編程源自lambda演算，因此它不直接映射到Turing或von Nemuan機(jī)器。他們中的任何一個(gè)都可以通過仿真運(yùn)行功能程序，hoewver。我認(rèn)為圖靈機(jī)的映射可能比馮諾伊曼機(jī)器的映射更繁瑣，所以我對(duì)第三個(gè)問題的回答是"不，實(shí)際上它更糟糕"。

為O(n ^ 6)？對(duì)于什么？運(yùn)行時(shí)不依賴于程序的細(xì)節(jié)嗎？

圖靈模型定義了計(jì)算能力而沒有深入實(shí)現(xiàn)，沒有人會(huì)創(chuàng)建看起來像圖靈機(jī)的計(jì)算機(jī)。 (愛好者除外http://www.youtube.com/watch?v=E3keLeMwfHY)。

圖靈模型不是架構(gòu)。

馮·諾伊曼是如何建造計(jì)算機(jī)的指導(dǎo)。它沒有說明計(jì)算能力。根據(jù)指令集，生產(chǎn)的計(jì)算機(jī)可能是也可能不是圖靈完成(手段可以解決與圖靈機(jī)相同的任務(wù))

函數(shù)編程(lambda演算)是圖靈完成的另一種計(jì)算模型，但不能原生地適用于馮·諾依曼架構(gòu)。

圖靈"模型"根本不是建筑模型。這只是一個(gè)不存在的機(jī)器，圖靈假設(shè)它可以作為他證明決策問題的工具。

總結(jié)

以上是生活随笔為你收集整理的计算机能模拟图灵机吗,关于计算机科学：图灵机与冯诺依曼机器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。