什麼是圖靈機?定義

1920 世紀 30 年代,當世界正走向一場新的全球大火時,電腦科學也在不斷進步,在許多情況下,電腦科學的指導是為一些人已經預料到即將到來的戰爭做準備。

正是在這種背景下,英國數學家艾倫·圖靈(後來被認為是現代計算之父之一)發展了他的工作,並於 1936 年提出了現代計算機的基礎假設。

所謂圖靈機是一種能夠按照給定規則處理資料的理論裝置。

規則和資料是分開的;事實上,圖靈設想規則將儲存在某種類型的固定媒體上,而資料將儲存在同一台機器可以根據規則表進行修改的磁帶上。

在這個概念模型中,我們清楚地看到現代電腦的進步:即使用戶級別簡單,也可以輕鬆看出「不可變」應用程式之間的區別(有細微差別,但在這種情況下,讓我們這樣認為) )和數據。,可以按照規則進行更改,這就是編程。

儘管理論上的圖靈機非常簡單,只執行非常基本的操作,例如改變狀態、讀取和寫入,但它能夠執行機械計算機可以使用演算法執行的所有數學計算。

換句話說:如果一個問題可以透過書面演算法來表達,那麼它就可以由圖靈機處理──至少在理論層面。

艾倫·圖靈將其視為一種練習,旨在證明存在電腦無法解決的數學問題。

圖靈設想的資料磁帶是無限的,可以由機器從右到左、從左到右移動,就像舊的盒式磁帶或膠片磁帶一樣,可以隨意倒帶或前進。

規則集也可以理解為一種程式語言,因為它必須具有邏輯且一致的語法。

隨後,其他數學家提出了更複雜的圖靈機版本。

因此,有兩個磁帶的機器、確定性的機器,甚至量子圖靈機,都可以幫助我們,就像它傑出的祖先所做的那樣,為期待已久的量子計算奠定基礎。