圖靈機與λ演算是等價的，為什麼前者成為了普遍接受的計算機或計算理論的模型？

01-02

希望能從計算機科學的發展歷程的角度說明。

等價只是從可計算性和多項式時間內的可計算性來講的。要論上具體數量級和係數，基本上沒有哪兩個計算模型是完全等價的。

最後實際普遍使用的computation model是Von-neumann模型，都帶著可隨機訪問的內存。很少有真拿一條紙帶左右移動算東西的。Von-neumann能流行，主要是因為這個能用電子元件做出來，而且速度和其他能做出來的model比要快不少。

Turing machine成為了最著名的model（而不是lambda calculus），恐怕是因為它不僅是個model，而且是個machine（拿lego就可以搭出來），因此不僅有理論意義，而且有（雖然微弱的但十分具有啟發性的）現實意義。

被普遍接受的計算機模型是 RASP，因為它能造出來……

考慮到硬體結構、空間複雜度等問題，自然數不會用church encoding表示，遞歸也往往不會真編碼成Y combinator 。雖然有個東西叫De Bruijin Notion，可以把lambda term編碼到形似0101的二進位形式。。

Lisp Machine也是建立在Von-neumann體系結構上的，只不過用專用硬體、指令加速某些操作，比如用List處理器高速完成動態類型檢查，專門的List存儲器實現樹狀的表存儲，把nil之類的常量存到專用寄存器，對某些結構並行求值。。

各種Abstract Computing Machine（CESK、CLS、SECD 等）的提出、

編譯技術（譬如CPS、Defunctionlizing變換、LISP-2 GC）的進步、以及體系結構的發展（內存、微處理器等），使得普通PC上也能準確、高效地實現函數式語言。

從risc的興起和cisc的衰落看得出，技術發展總趨勢是更簡單直接，逆潮流而動的設計都站不住腳。

與 Lambda Calculus 相對應的 Lisp Machine 也不是沒有火過啊，不過那已經是上個世紀的事情了

Lisp Machine 時期最偉大的 Symbolics, Inc.
公司至今仍然健在 .這個公司仍然擁有 Lisp Machine 的全部技術以及古老的符號計算系統 Macsyma，但整個公司只屬於一個人了
(David Schmidt)。無數人希望 Symbolics, Inc. 開放 Lisp Machine 源代碼以促進 Lisp
社區的發展但均告失敗。從 MIT 開源的另一款相對簡單的早期 Lisp Machine: MIT CADR 來看，Lisp Machine
的內部實現極其複雜精巧，至少包括硬體 GC 系統，能夠直接運行 Lisp 元指令的特製處理器以及 Lisp 實現的 Lisp 本身，CLIM
圖形環境以及完整的操作系統。可惜至少到目前為止，除了極少數當年的開發者以外，無人能一窺其全貌。

後來，由於 AI 方面研究的萎縮以及微機普及浪潮的推動，Lisp Machine 這種精巧複雜高貴冷艷的玩意就死掉了

With the onset of the "AI winter" and the early beginnings of the microcomputer revolution
(which would gather steam and sweep away the minicomputer and
workstation manufacturers), cheaper desktop PCs soon were able to run
Lisp programs even faster than Lisp machines, without the use of special
purpose hardware. Their high profit margin hardware business
eliminated, most Lisp Machine manufacturers went out of business by the
early 90s, leaving only software based companies like Lucid Inc.
or hardware manufacturers who switched to software and services to
avoid the crash. Besides Xerox, Symbolics is the only Lisp Machine
company still operating today, selling the Open Genera Lisp Machine software environment as well as the Macsyma computer algebra system.

[1] 商業 Lisp - 冰河的日誌

[2] Lisp machine

因為早期計算機性能不行，沒其他原因。

那個年代的人最關心的就是性能。

fortran，c，都是如此，

這種情況一直延續到java的出現。

希爾伯特最初提出 23 個問題的時候，對計算問題只是大概說了一個「mechanical」，當時誰也說不定「machanical」的形式定義。圖靈的模型無疑更接近「mechanical」的本意。而且後來圖靈從哲學上把圖靈機和人腦做了一些比較，也得到了業界的廣泛認可。這些在圖靈的傳記《Enigma》里專門有描述。特別說了圖靈發現 Church 的論文首先被 reivew，非常沮喪，但是最後評議還是認為圖靈的模型更有創意。

其實呢，lambda演算如果嫌丘奇數太長可以編出類似二進位數的lambda項，如果不想用y組合子的話非遞歸形式的函數也可以寫出來，更大的問題是它根本就不適合作為現實世界的編程語言

無類型的lambda演算非常不安全 http://www.zhihu.com/question/23434097/answer/91663833，而引入類型之後又變得非常繁瑣不便，比如在簡單類型lambda演算里if語句和cons的參數必須是同一類型。據說有時寫haskell明明都是對的可是就是編譯不過，就是hm類型論搞的鬼

不管是在cl還是scheme，都認為eval is evil，而lambda演算恰恰就是一種時時刻刻都在eval沒有eval就沒法計算的語言，所以那些說編程語言和lambda演算更像的可以歇著去了，要是讓丘奇知道有人說這一堆知道80年代才能真正返回一個函數而且到現在還有人問怎麼把lambda表達式寫成遞歸的破爛東西更像lambda演算的話，估計他老人家得氣得活過來

圖靈機模型由紙帶和讀寫頭構成，圖靈使用這台想像的機器編出來一個程序，這個程序能模擬任何能在圖靈機上執行的程序，從而證明了，這種模型的通用型：程序可以編碼後先存放到紙帶上面，然後由這圖靈機讀取，然後完全地執行這段代碼，實現代碼的預定目標。

這本身就是存儲式計算機的模型，程序預先裝載，然後執行。

並且操作系統、編譯器都是利用這種存儲式的原理進行設計的。操作系統是控制好其他程序的程序，而編譯器是分析程序代碼的程序（不就是圖靈機嗎）。這使得人們更了解更容易接受存儲式的圖靈機模型。

lambda 更多出現在數學證明的書中，它是一種比存儲式模型「高級」，抽象很多的計算模型。在物理現實中，沒有直接能對應上這種計算模型的材料，也就難以製造並普及這種模型的物理計算機。因此這種模型比起存儲式的，在理論學家之外沒那麼流行。

圖靈機這東西非常的直觀，非常容易被缺乏高深數學知識的工程人員所理解，甚至在圖靈提出圖靈機概念之前，工程師們己經開始用這種東西來解決計算問題了，從廣義上說早期的各種機械計算器，加法器，乘方器什麼的，甚至算盤本質上都是解決特定問題的圖靈機，納粹製造的加密機enigma更是典型的圖靈機。

所以說圖靈機並不是圖靈發明的，他只是把圖靈機的特性抽象出來，並證明這東西和lamda演算是等價的，這實際上非常的有意義。

因為lamda演算是數學家提出的數學模型，它使用嚴格的數學方法，證明能解決所有的可計算問題。但這畢竟是數學家的玩意兒，太抽象，也不容易被工程界實物化。

但是圖靈的證明建立了工程界和數學界的橋樑，工程師們只要按照他們熟悉的方式構造圖靈機就好了，因為它和數學家們整的那套抽象的東西一樣，都能解決可計算問題。

所以圖靈的貢獻在於為工程師們製造圖靈計算機提供了理論依據。其實我覺得沒有圖靈機概念，工程師們還是會用他們熟悉的方式製造出能力越來越強的計算機來，只是沒辦法知道這東西能不能解決所有的可計算問題。

因為伯克利和Sun的人發現RISC架構的硬體更好設計，而後者在工業界的技術領袖地位又導致了這種設計的普及——從而使得硬體更圖靈機化。

我給出一個不是從計算機科學發展歷程的一個答案。

關於計算的討論很多，題主知道圖靈機與λ演算都是計算模型，而且它們等價，其實還有許許多多的計算模型，它們都等價：

圖靈機
λ演算
一階邏輯
時序邏輯MPTL
動態邏輯
petri網
進程代數
遞歸可枚舉語言

這些計算模型都是相互關聯有所側重的，比如說圖靈機能接受的語言是遞歸可枚舉語言，一階邏輯的歸約是λ演算，一階邏輯的擴充是時序邏輯、動態邏輯，進程代數關心遷移而圖靈機關心狀態。

這些計算模型能力都等價，它們從不同的視角去看待計算這件事情，面對著不同的問題，採用不同的計算模型效果是不一樣的。在有些問題裡面，用圖靈機就表達不清楚，但是用遞歸可枚舉語言就能很好地解釋。圖靈機需要知道系統內部狀態，而進程代數只需要關心交互過程。動態邏輯和petri網能給出計算的全局狀態，而時序邏輯、圖靈機、進程代數則「只見樹木不見森林」。

最後，我只能說，針對合適的問題，有合適的模型。「普遍接受」是因為見過的問題少了。

題主耍流氓。

圖靈機與λ演算是等價的，但除了BrainFuck以外的別的現代編程語言都更接近λ演算。