iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 2
0
自我挑戰組

程式追尋之路系列 第 5

#5 通用圖靈機

學電腦的人或多或少都聽過圖靈這個名字,他的偉大之處在於他創造了一台「可以運算」的機器,許多關於電腦的故事都是從這台機器開始的。

一條無限長的紙帶、紙帶讀寫頭、搭配控制讀寫頭的指令、一組操作規則,就可以完成各式各樣的運算。但圖靈還不滿足,他把控制指令和操作規則變成可以寫在紙帶上的資料,這概念就是我們熟知的「程式」。只要我們能把編碼輸入到機器裡,這機器就可以變成任何我們想要的機器,它可以做任何我們想要做的運算,它被稱為「通用圖靈機」。

現代的電腦是通用圖靈機的產物,學術界同一時間還有其他的計算理論,也不約而同地交會在一起。
「Lambda演算」、「遞迴」、「圖靈機」這三者被證明是等價的,意味著他們的運算能力是相等的。同時他們也找到這機器運算能力的上限,「可判定性問題」「停機問題」。對於這類問題的探索,可以了解到機器的運算極限在哪裡?

圖靈機是理論機器,紙帶機的規則還是太抽象,人類還是不好理解。於是 約翰·麥卡錫 教授試著用另外一種更容易理解的方式描述這台機器,他用數學公理系統的方式建構了計算模型,而後被他的學生實作成為現在的 Lisp 語言。

下一段將介紹 Lisp 語言

參考資源:
計算機理論的始祖-圖靈機
通用機器
計算模型的血淚史
圖靈機


上一篇
#4 從無到有打造一台電腦
下一篇
#6 Lisp: 純粹的力量
系列文
程式追尋之路7
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言