圖靈機正式面世80年︰「離地」研究為人類帶來了電腦

我們想讓你知道的是
80年前,圖靈發表〈論可計算數及其在判定問題上的一個應用〉,對電腦發展影響深遠。
1936年11月30日出版的《倫敦數學學會會刊》(Proceedings of the London Mathematical Society),有一篇標題看來平平無奇的文章︰〈論可計算數及其在判定問題上的一個應用〉(On computable numbers, with an application to the Entscheidungsproblem),作者是圖靈(Alan Turing)。
2012年,圖靈誕生100周年,學界將該年訂為「圖靈年」,舉辦活動以紀念其重大貢獻。2014年電影《模仿遊戲》亦講述了圖靈於二戰時協助破解德軍密碼的故事(雖然忽略了波蘭數學家的貢獻),相信不少人對圖靈的名字、貢獻及其因同性戀傾向被迫害的經歷略有所聞。
圖靈的眾多貢獻當中,最為重要的正是1936年這份論文,因為在文中他首次提出「圖靈機」這個概念——文中他稱為a-機器,a代表「自動」(automatic)——為現代電腦、電腦科學及計算理論奠下數學基礎。
當然,除圖靈以外,他之前及之後均有不少人對電腦發展貢獻良多。不過今日——〈論可計算數〉第一部份發表80周年(第二部份於同年12月23日發表),讓我們先看一看他的「圖靈機」為何如此重要。
數學基礎
一切源自一個貌似非常「離地」、與現實毫不相干的問題︰我們如何確定數學知識可靠?
19世紀,數學發展越來越抽象,因此亦出現了各種公理系統——公理是指被視作「不證自明」的命題,數學家以公理為基礙,再用邏輯推論出不同數學定理。但到了20世紀初,有批數學家(以及關心數學的哲學家)開始擔心數學知識不夠穩固,他們想確保由特定公理出發,不會推論出矛盾——假如有矛盾的話,數學就完了。
他們不是杞人憂天,當時集合論中出現了數個悖論,或會導致數學出現矛盾。幸運的話,有些悖論可以透過引入新概念去解決,例如自數學界出現「極限」的嚴格定義後,甚少人會認為「亞基里斯永遠無法追上烏龜」的芝諾悖論是個問題。
那個時候這批數學家大概分成三派,其中一派是數學家希爾伯特(David Hilbert)主導的「形式主義」。簡略來說,形式主義者希望藉由把數學還原成純粹符號的形式系統,再用(有限制的)數學去證明這個系統不會出現「0=1」之類的矛盾句,從而確保數學不會產生矛盾。
羅素(Bertrand Russell)及懷海德(Alfred Whitehead)三大冊《數學原理》(Principia Mathematica),則是從邏輯主義出發,嘗試以邏輯公理推導出整個數學系統——他們想的是,既然邏輯不可能自相矛盾,只要證明數學是由邏輯延伸出來,就可以確保數學一致。
兩人終告失敗(原因並非本文重點),不過書中改良自弗雷格(Gottlob Frege)的邏輯系統,促進了數理邏輯發展。其後邏輯學家整理出一套現稱為「一階邏輯」的系統,包含若干邏輯公理和推導規則,由此出發可以推導出不少已知的邏輯定理,是個很好用的系統。
判定問題
回到希爾伯特,他想完全將數學化約成一個僅有符號的形式系統(這方面羅素及懷海德貢獻了不少),只要按照規則,完全不懂數學、不知道符號意義的人也可以推演出「數學定理」,這樣就可以撇除人為錯誤(例如受直覺誤導)。
他又希望找到一套清晰的判定程序,去確認如何判斷一個邏輯公式是否屬於邏輯系統的定理,假如成功,下一個目標自然是判斷數學命題是否數學定理——這樣數學家就不用再苦苦思索那些懸而未決的數學猜想,只要一起運行這個「判定程序」,就可以獲得答案,簡單直接。
不過,希爾伯特於1928年提出的這個「判定問題」(Entscheidungsproblem),在1935至1936年期間,分別由數學家丘奇(Alonzo Church)及圖靈獨立得出答案︰不可能。
要解決判定問題,首先需要釐清一個概念︰何謂「清晰的判定程序」?當然,有一些條件非常明顯,例如程序必須是有限的——僅包含有限條規則、能夠在有限時間完成。程序當中的規則也必須極之簡單,以符合希爾伯特的要求。
舉個例,假如我要教一位小學生判定一個數字以否質數,可以利用他懂得「整數」、「除數」、「餘數」和「比較大小」等概念,去讓他按照程序執行,然後他就會發現7是質數、8不是質數、9不是質數…
但希爾伯特所要求的還要更少——執行規則的人只能夠辨認符號(不會把不同的符號混淆)、抄寫符號、按照規則把符號串轉換等,甚至不懂「加減乘除」等基本數學運算,也不會知道數學符號的意思。
圖靈機
終於回到圖靈的論文,在〈論可計算數〉中他設想以下一部機器,包含以下部份︰
- 一條紙帶,這條紙帶分成一格一格的(好吧聽起來的確有點像廁紙),每格可以印一個符號。第一格的編號為0,然後是1、2、3…沒有盡頭,以 ◻ 表示空格。
- 可以在紙帶上左右移動的讀寫頭,它每次能夠讀取所處位置那一格的內容(同一時間只可讀取一格),亦可以改變其內容——改寫其他符號或變成空格。
- 會存在機器目前狀態(state)的狀態暫存器,每部機器的可能狀態數目有限,其中一個稱為「開始狀態」,就是機器一開始時所處的狀態。
- 儲存所有規則的指令集,機器會根據其目前狀態以及讀寫頭當時讀取的方格內容來執行指令,進行下一步動作。
上述4個部份當中,決定機器如何運作的是指令集及狀態。為方便說明,以下機器的狀態以顏色表示,而符號只有0、1及◻(空格)。圖靈把指令限制在這個形式︰
- 當處於A狀態並讀取到符號X時,寫入符號Y,移動讀寫頭,並轉至B狀態。
以下是一些例子︰
- 當處於紅色狀態並讀取到符號0時,寫入符號1,讀寫頭左移一格,並轉至藍色狀態。
- 當處於黃色狀態並讀取到符號1時,寫入符號1(即維持原狀),讀寫頭留在原處,並維持在紅色狀態。
- 當處於藍色狀態並讀取到符號0時,清除符號(變成空格◻),讀寫頭右移一格,並轉至黃色狀態。
如果沒有適用的指令時,這部設想中的機器——後世稱為圖靈機——就會停止運作。

不同圖靈機分別,在於它們擁有不同的可能狀態以及指令集——事實上,我們只需要看一部圖靈機的指令集,就知道它可以有甚麼狀態,因此可以說,圖靈機的指令集(以及一開始時紙帶上的內容)決定了它如何運作。
最新發展:
-
曾因同性戀遭迫害,電腦之父「圖靈」登上英國50英鎊新鈔 3年前
-
奇書面世40年︰《Gödel, Escher, Bach》的知識漫遊 3年前
-
首個世界邏輯日︰連結起20世紀兩大邏輯學家的日期 4年前
-
首個世界邏輯日︰連結起20世紀兩大邏輯學家的日期 4年前
-
被誤用的哥德爾「不完備性」定理 5年前
-
被誤用的哥德爾「不完備性」定理 5年前
-
「這門學科有甚麼用?」 5年前
-
「這門學科有甚麼用?」 5年前
-
人類和AlphaGo對奕,真的像跟跑車比快嗎? 5年前
-
人類和AlphaGo對奕,真的像跟跑車鬥快嗎? 5年前
-
破解納粹密碼的英雄,也因同性戀備受歧視——艾倫圖靈的傳奇一生 5年前
-
數學是一種「發明」還是「發現」? 5年前
-
「圖靈法」正式生效 近5萬同性戀者身後獲平反 5年前
-
邏輯推理就只是心理活動嗎? 邏輯心理主義及胡塞爾的批評 6年前
-
邏輯推理就只是心理活動嗎? 邏輯心理主義及胡塞爾的批評 6年前
-
數學家哈代的金句與「無用」的數學 6年前
Tags:
pCloud 新年優惠方案總整理,趁過年買 10TB 終身雲端空間備份多年檔案與照片

我們想讓你知道的是
過年長達 10 天的連假,是個好機會趁著這時候好好整理多年的照片與影片,除了原本的資料保存方式之外,也是應該好好考慮選個可靠的雲端空間來做多重備份。pCloud 這次個人終身方案的檔期剛好可以讓你 2023 年 1 月 20 日購入,整個新年期間都能慢慢整理你的照片、影片與檔案。
轉眼間又要過年,除了整理多年來的影音收藏之外,是不是也該趁著過年檔期入手便宜超值的雲端空間方案?看著日前 iCloud 曾發生嚴重的資安意外,MacRumors 討論區上有用戶在用 Windows 的 iCloud 同步 iPhone 檔案後,發生檔案意外損壞的狀況,並出現陌生人的照片與影片,這告訴我們檔案備份真的要慎選,且最好能做到多重備份才能在意外發生時有挽回的餘地。
資安意外頻傳,多重備份才讓人安心
iCloud 發生的資安問題,讓人擔憂起是否自己的照片也會出現在別人的相簿中,這件事也在MacRumors 討論區上引發討論。
資料保存上比較穩妥的方式就是多重備份,利用多種管道、異地保存自己的檔案,這樣就能確保萬一檔案損壞時,還有備援資料可以使用。就算你現在使用 iCloud、Google Drive 進行單一備份,也不能保證你的檔案不會發生意外,至少選擇 2 種備份方案才是比較安全的保管方式。

經濟與安全可以兼顧,瑞士的雲端服務 pCloud
pCloud 是來自瑞士的雲端服務廠商,2013 年創立至今已有 10 年歷史,全球有 1600 萬用戶使用其服務。它的資料位於重視資訊安全的歐盟與美國,在創立帳號時可選擇資料要存放於歐盟或是美國,相比其他無法選擇的廠商多了選擇性,而且不只是存放地點,pCloud每份資料都會分散 5 份檔案儲存於多個伺服器增加安全性。檔案還會經過 256 位元 AES 加密技術保護,傳輸時使用 TLS/SSL 強化資安。如果需要更安全的保密措施,還可以選配 Crypto 加密服務。
pCloud 也有免費帳號可以使用,註冊後就有 10GB 免費空間能夠試用,不論是要體驗介面操作或是傳輸速度都沒問題。相較於其他訂閱較為單一的雲端服務,pCloud 除了月繳、季繳、年繳之外,還會不定期推出優惠的終身買斷的方案,且費用上不會有額外的設定費或隱藏性支出。若是家庭用戶,還可以選擇家庭方案讓 5 個人一起使用更經濟。





農曆新年 -85% 超優惠終身買斷方案,錯過可能就沒了
雖然現在官網活動還沒開跑,但 pCloud 確定會在農曆新年推出超優惠方案,活動期間為 2023 年 1 月 18 日至 2023 年 1 月 24 日,活動只有短短 5 天要好好把握。這檔農曆新年促銷活動是針對個人終身制方案,500GB、2TB、10TB 個人終身方案都會有優惠價格,500GB 個人終身價折扣後為 139 美元、2TB 個人終身方案折扣價為 279 美元、10TB 個人終身方案折扣價為 890 美元,折扣幅度高達 85%。
pCloud 農曆新年優惠方案:
500GB 個人終身方案:原價 570 美元,優惠價 139 美元。
2TB 個人終身方案:原價 1140 美元,優惠價 279 美元。
10TB 個人終身方案:原價 6000 美元,優惠價 890 美元。

趁著過年好好整理檔案,選個安全可靠的雲端空間更安心
過年長達 10 天的連假,是個好機會趁著這時候好好整理多年的照片與影片,除了原本的資料保存方式之外,也是應該好好考慮選個可靠的雲端空間來做多重備份。pCloud 這次個人終身方案的檔期剛好可以讓你 2023 年 1 月 18 日購入,整個新年期間都能慢慢整理你的照片、影片與檔案。這次方案價格十分優惠,終身買斷不會產生每個月的費用,用越久省越多,如果你需要備份的檔案大且多,可以考慮看看經濟又可靠的 pCloud。pCloud 終身制優惠方案並不是每次都有,因此有需要的朋友就盡快購入,越早使用省越多。
