搞懂「通用圖靈機」的第一站——康托爾的「無限樂園 ...

沒想到1874 年，不到30 歲的德國數學家康托爾(Georg Cantor) 竟然跳出來說：不對，無限大可以當成實體做比較，而且可區分大小，例如實數的集合就比自然數 ... 0145文字分享友善列印0145文明足跡社會群體科學傳播電腦資訊搞懂「通用圖靈機」的第一站——康托爾的「無限樂園」│《電腦簡史》數位時代（十二）張瑞棋・2020/12/07・3891字・閱讀時間約8分鐘・SR值532・七年級＋追蹤本文為系列文章，上一篇請見：現代電腦從此展開——馮紐曼與馮紐曼架構│《電腦簡史》數位時代（十一）數學能不能判定？圖靈機的源起在美國那些電腦先驅著手設計電腦之前，英國劍橋大學有位研究所新生已經發表論文，率先指出通用型電腦的可能性。

這位學生就是後來有「電腦之父」、「人工智慧之父」等美譽，還在二戰期間發明電腦破解德軍密碼的天才——圖靈。

38歲的圖靈。

圖：Wikipedia圖靈撰寫那篇論文的初衷極為特殊，與實際計算毫無關聯。

之前介紹過的那些電腦先驅，若不是因為在就學期間經歷計算之苦，就是工作上遇到瓶頸，才會一頭栽入計算機的研究，希望透過機械化與自動化讓計算更快速、更準確。

但圖靈都沒遇到這些狀況，他也沒想要解決實務上的技術問題。

事實上，他的論文根本無關乎計算，而是要回答一個極為抽象的大哉問：數學是否可以判定？什麼叫可以判定？這與計算機有什麼關係？要說清楚這來龍去脈，也為了搞懂圖靈所設想出來的通用圖靈機是什麼，得先探究另一個數學問題——「無限」。

象徵無限的符號。

圖：Wikipedia無限是什麼？康托爾挑戰數學界千年共識從亞里斯多德以降，無限向來被視為一種潛無限(potentialinfinity)，是進行中的未完成狀態，不能當成實體看待，更不能比較大小，否則就會出現矛盾。

例如伽利略便曾舉出一個悖論：自然數(1、2、3、……)與平方數(1、4、9、……)哪個比較多？照理說自然數當然遠比平方數還多，可是如果用一個蘿蔔一個坑來想的話，每個自然數都有個平方數與之對應(1🡪12、2🡪22、3🡪32、……)，表示有多少自然數，就有多少平方數，兩者一樣多，這不就前後矛盾了嗎？因此伽利略主張等於、大於、小於這些關係不能應用於無限。

數學王子高斯也嚴正表示：「我反對將無限量看成真實的實體來運用，這在數學之中是永遠不被允許的。

無限只是一種說法而已。

」這句話可以說代表了所有數學家的共同看法。

沒想到1874年，不到30歲的德國數學家康托爾(GeorgCantor)竟然跳出來說：不對，無限大可以當成實體做比較，而且可區分大小，例如實數的集合就比自然數的集合大！康托爾當然有所本才敢公然挑戰數學界長久以來的信念，不過他所提出的證明是用集合論的方法，不好解釋，我們改用他後來在1891年提出的「對角線法」來做說明。

這不只是因為這個方法更簡潔易懂，更因為它影響深遠，啟發圖靈解決了判定問題，也才誕生出極具開創意義的「通用圖靈機」。

德國數學家康托爾(GeorgCantor，1845-1918)。

圖：Wikipedia騙肖ㄟ，有理數和自然數一樣多？首先讓我們重溫一下怎麼比較集合的大小。

基本上只要集合所含的元素一樣多，它們就是一樣大，例如A={1,2,3}，B={2,4,6}，兩者的元素都是3個，所以A與B大小相等。

問題是無限數列沒有止盡，要怎麼數有幾個？沒關係，同樣用一個蘿蔔一個坑的概念，只要兩個集合的元素彼此一一對應，就代表這兩個集合大小相等。

所以按照這個定義，伽利略悖論就解決了：自然數的集合與平方數的集合一樣大。

那麼自然數與有理數呢？可以用分數表示的數就是有理數，而光在0和1之間就有無限個分數，當然是有理數遠多於自然數啊！等等，且看康托爾怎麼巧妙地列出所有有理數：1/11/2、2/11/3、2/2、3/11/4、2/3、3/2、4/1…………以此類推第一行是分子與分母相加為2的有理數，第二行是分子與分母相加為3的有理數，第三行相加為4、第四行相加為5，……以此類推，便可以列出全部的有理數，一個都不漏。

然後我們再由上往下，一行一行的由左向右依序為每個有理數編號：1、2、3、4、……，如此一來，有理數不就與自然數一一對應了嗎？所以有理數的集合與自然數的集合也是一樣大。

（如果要涵蓋負的有理數，只要依樣放在這個三角形列表的右半部就行了）到目前為止，我們看到自然數、平方數、有理數這些集合，雖然乍看明明大小不同，結果卻證明無限是不分軒輊的。

那麼同樣是無限多的實數，憑什麼就比它們都來得大呢？比無限大還大？康托爾祭出對角線法實數除了有理數，還包括無理數，也就是無法用分數表示的數，例如\(\sqrt{2}\)、π、……等等，所以我們得用小數來列舉實數。

先來看0與1之間的所有實數，也就是純小數。

絕大部分的數字小數點後有無限多位數，所以沒辦法像有理數那樣依序一一列舉，不過沒關係，我們就不按大小順序而是任意列舉，例如：　0.541592653……　0.041719652……　0.862235975……　0.640194231……　0.234178276…………反正我們姑且假設所有純小數都在這張無限長的表格裡了，因此都有個自然數與它對應。

現在對角線法要上場了。

我們從第一行取小數點後第一個位數，第二行取第二位數，以此類推，可以得到一個小數：0.54217……。

然後我們將每個位數都加上1，會得到一個新的小數：0.65328……。

這個新的小數很特別喔，因為它和每一行的數字都有一個位數不符，表示它絕對不在這張表裡面，也就是這個小數沒被自然數對應到，前面假設所有純小數都在這張表並不成立。

你可能會說：那還不簡單，再把這個新的小數加進去這張表就好啦。

可是加了之後，我們仍然可以用剛剛的對角線法，又產生一個不在表中的新數字，因此永遠有自然數對應不到的小數，足以證明小數的集合比自然數還要大。

康托爾把自然數、有理數這類可列舉的數稱為「可數無限」，是最初級的無限，算是第0級。

小數則是「不可數無限」，是第1級無限，比第0級無限還要大（註一）。

就這樣，長達兩千年的普遍信念，一夕之間被康托爾徹底顛覆了，無限不再是無從比較的概念，而是可以明確區辨的實體。

現在你知道什麼是對角線法，已經可以直接到下一站，看看圖靈如何構思出計算機。

不過康托爾還有許多令人驚奇的把戲，何不繼續往下一探究竟，看看自己有多少錯誤的迷思？無限的無限的無限……——冪集合的威力我們已經知道無限有分等級，而純小數的無限等級比自然數或有理數還大。

那有比純小數更大的無限嗎？例如0到100之間的實數？既然實數屬於特殊的不可數無限，不能用前面證明有理數與自然數一樣多的列舉對應方式，那麼範圍更大的實數是不是無限等級就比較大？ 直接宣布答案：不，都一樣大。

即使是從負無限大到正無限大，涵蓋所有實數的集合仍然與0與1之間的純小數一樣大。

怎麼證明？如下圖，我們畫一個直徑為1的半圓，在它下方畫一條代表往兩端無限延伸的直線。

從這條直線上的任一點畫一條線與圓心相連，會與半圓相交於一點。

這個點對應到直線上的位置一定會落在0與1之間，表示任一實數都會有一個純小數與之對應，所以所有實數的集合與純小數的集合一樣大。

講到這裡，你大概會以為無限就分兩種：自然數、有理數這類可數無限屬於第0級無限，小數、實數這類不可數無限屬於第1級無限。

往上不會有更大的無限，畢竟實數都已經涵蓋所有數字了。

沒想到康托爾就像魔術師從空無一物的帽子變出兔子般，竟然端出了比第1級無限更大的無限：冪集合。

冪是次方的意思。

一個包含n個元素的集合，它的子集合個數為2n，把這些子集合當成元素全部集合在一起，就成為原來那個集合的冪集合。

例如集合A={1,2,3}，那麼A的冪集合就是由空集合、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}，這8個集合為元素所構成的集合。

康托爾於1891年證明無限集合的冪集合是更大的無限（註二），例如自然數的集合是第0級無限，它的冪集合就是第1級無限；同理，實數的冪集合則是第2級無限。

還沒完喔，實數的冪集合又可以組成更大的冪集合（就像上面舉例的A集合，它的冪集合的冪集合就有28=256個元素），而誕生出第3級無限。

你會想這樣不是沒完沒了嗎？沒錯，新的冪集合不斷衍生，無限的等級也越來越大，永無止盡。

康托爾掀起巨浪，自己卻反遭吞噬原本一片渾沌的無限，經康托爾大刀一揮，不但有大小之分，而且宛如侏儸紀公園裡的恐龍，一隻比一隻巨大，更可怕的是完全沒有極限。

不過康托爾革命性的創見並未獲得當時的主流認同，尤其他的老師公開嚴厲批判，不但造成康托爾謀求教職不順，更重創他的心靈。

1884年開始，康托爾數度精神崩潰住院治療。

出院後他曾一度放棄數學，轉而研究歷史與神學，但後來還是「雖千萬人吾往矣」，繼續打破無限的迷思，發明出影響深遠的對角線法。

1900年代初期，康托爾的研究成果終於逐漸獲得肯定，無奈1917年他最後一次進入療養院時，德國因為一次世界大戰戰情吃緊，實施食物配給。

康托爾因此營養不良而健康惡化，隔年就在院內過世，享年73歲。

好了，無限樂園的導覽到此告一段落，下一章我們就要介紹圖靈。

他的悲慘命運不下於康托爾，也是做出了無與倫比的貢獻，最後卻以悲劇結束一生。

註一：康托爾相信並不存在大小介於第0級與第1級之間的無限。

但這至今仍無法證明，因此稱為「連續統假設」。

註二：康托爾就是為此而發明對角線法。

證明方式與前面證明純小數比自然數多的做法類似，先假設冪集合可以與原來的集合完全對應，再證明冪集合中永遠有對應不到的元素，所以冪集合的無限等級又大一級。

我要跟泛科學說「　　　」！參加泛科學網站體驗調查，提供意見還能拿禮卷！利用阿基米德浮力原理，當玻璃小球浮起時測量氣溫～伽利略溫度計交換禮物大賞！QUALY醉愛北極熊酒瓶塞廢材大作戰！科學實驗室EP5—手作神器如虎添翼數學好無聊、不實用，到底為什麼要學數學？給大人玩的理財桌遊，從此航向財富自由！交換禮物首選、推理迷必買！台灣推理作家協會20週年限定週邊相關標籤：圖靈康托爾數位計算機數學無限計算機通用型計算機電腦簡史熱門標籤：量子電腦BNT疫苗珊瑚諾貝爾獎前列腺文章難易度剛好太難所有討論 0登入與大家一起討論張瑞棋423篇文章・ 367位粉絲＋追蹤1987年清華大學工業工程系畢業，1992年取得美國西北大學工業工程碩士。

浮沉科技業近二十載後，退休賦閒在家，當了中年大叔才開始寫作，成為泛科學專欄作者。

著有《科學史上的今天》一書；個人臉書粉絲頁《科學棋談》。

RELATED相關文章研究資料亂到不行？你需要的是「資料管理方案」——淺談什麼是「開放科學」理財投資不嫌「早」？學校沒教的孩童理財課在這裡ft.布萊恩兒童商學院布萊恩老師【科科聊聊EP72】海上救援和逃生演習——和平號順利歸航│環球科學札記(58)一起「南漂」吧！「沙崙智慧綠能科學城」展現未來城市新面貌ft.臺南市政府經濟發展局長陳凱凌【科科聊聊EP73】TRENDING熱門討論即時熱門跟名偵探學習推理—回溯推理與貝氏定理分析（下）111小時前海上救援和逃生演習——和平號順利歸航│環球科學札記(58)111小時前眼皮長出如紫色眼影般的紅疹？——認識「皮肌炎」與肺纖維化111小時前研究資料亂到不行？你需要的是「資料管理方案」——淺談什麼是「開放科學」119小時前核廢料放我家？高階核廢料的危險性與處理方式84天前「恆水創電」聯手比利時Turbulent研發超低落差機組——力拼「微水力發電」扎根台灣！42021/12/15腸道炎會導致憂鬱症？——淺談體內的腸腦軸線，揭露腸道菌的「腦控」機制！42021/12/15人類是96%的大猩猩嗎？——《生命之鑰：一場對生命奧祕的美麗探索》32021/12/05123文字分享友善列印123文明足跡活得科學電腦資訊研究資料亂到不行？你需要的是「資料管理方案」——淺談什麼是「開放科學」研究資料寄存所(depositar)・2021/12/22・3081字・閱讀時間約6分鐘＋追蹤組織／研究資料寄存所作者／何明諠什麼是「開放科學」？大體而言，開放科學是關於「有品質、完整、平等與利益共享的科學環境」的一套構想[1]，它希望能移除知識藩籬，激發研究創意。

為了達成這些核心價值，不同的科學社群衍生了不同實務作法，也造就了過往「開放科學」紛雜的內涵。

儘管如此，一般在討論「開放科學」時，仍認為其有幾個核心的關注面向，如開放近用科學成果（如論文）、開放研究資料、研究過程中使用科技工具進行開放協作等。

歐盟、OECD、聯合國等國際組織在近年來亦紛紛制定相關政策、白皮書，並投入經費致力於開放科學的推展。

脈絡不同，資料管理方式也不同「我知道開放科學很好，我也有滿手的資料，但是……」，在資料科學盛行的時代，幾乎所有研究者在處理資料時，都會遭遇各種「但是」的問題：但是資料很亂不知從何著手、但是不曉得要釋出哪些資料、但是沒有心力…。

在這樣的脈落下，中央研究院資訊科學研究所等5個單位，在今年10月7日舉辦了2021研究資料管理工作坊。

工作坊共概分成5個資料管理的主題，分別涉及「生物多樣性」、「多面向資料管理」、「氣候、海洋及空氣資料」、「研究團隊經驗分享」、「個人資料管理」等面向，邀請近20位來自不同領域、單位的講者，分享他們在研究資料管理（ResearchDataManagement,RDM）上的經驗。

圖／2021研究資料管理工作坊在資料管理實務上，各研究單位因資源配置、研究領域、研究方法、研究文化等差異，所遭遇的問題及可能的解方亦各不相同。

聆聽彼此經驗，了解對方解決問題的脈絡，是找尋自身合適的資料管理方式的有效途徑之一。

以本次工作坊為例，我們即觀察到，同是為了提昇資料的利用價值，有的單位選擇將資源優先配置在蒐集更多資料；有的則是積極建立、宣導資料處理的SOP；另外也有強調個別資料集的品質控管與說明。

圖為「台灣生物多樣性網絡」在回應資料價值時，將重點放置於增加資料量的成果圖。

圖／柯智仁－讓資料的價值被看見能否鼓勵資料的管理與開放？我們也發現，有關資料即時利用的需求，時常不在研究團隊最初的預期中，且需求亦可能來自團隊內部或外部。

而為了回應需求，有的研究單位選擇投入心力在軟硬體上，打造自動化流程，以應付外部大量的資料索取要求；有的研究單位，則優先建立單位內部的即時資料分享環境，再適度滿足外部需求。

以上各種應對方式間的差異，多半是因各單位在處理同一問題時，身處不同的脈絡所致。

逐漸上軌道的研究工具：資料管理方案在本次工作坊中，亦有關於「資料管理方案」（DataManagementPlan,DMP）的場次。

DMP是一份描述研究資料如何被蒐集、使用、管理、保存、分享等歷程的文件。

通常是在研究開始前撰寫，在研究中隨時修正，藉此研究者能更有效地管理資料。

近年來，DMP已逐漸成為計畫申請者被要求檢附的文件。

目前在網路上也能找到各式的DMP範本，協助研究者撰寫DMP。

例如研究資料寄存所（depositar）翻譯的ScienceEurope研究資料管理指南，就提供了一份DMP的範本。

在工作坊中，科技部永續學門指出，資料管理是開放科學的一部分，因此永續學門自2020年8月開始推動資料管理方案試辦計畫，透過經費補助的方式，鼓勵整合型計畫提出DMP。

本次工作坊亦有兩個參與試辦計畫的研究團隊，分享他們在撰寫及執行DMP的歷程。

在研究資料管理概論這個場次，亦仔細介紹了DMP可能包含的內容。

科技部永續學門自2020年8月開始試辦資料管理方案。

圖／李明旭－永續學門DMP試辦計畫但鑒於DMP在國際上逐漸成為「要求」，亦不乏質疑認為，撰寫DMP可能僅是加重研究者行政負擔；對此，一份2021年4月有關歐盟推行DMP的實證研究指出，超過80%的研究者認為DMP對他們的研究有幫助，這或可有效緩解相關的疑慮。

超過八成的研究者認為DMP帶來了比行政負擔更多的正面效益。

圖／OpenResearchEurope研究資料管理與開放科學2021研究資料管理工作坊的簡報及錄影，已在11月中悉數公開在工作坊網站。

而工作坊後不久，在2021年11月底，我們見到聯合國教科文組織（UNESCO）通過了一份開放科學建議書（UNESCORecommendationonOpenScience）。

這份文件共獲得193個與會國支持。

UNESCO表示，與會國們的共同支持，使向來意義紛雜的「開放科學」首次取得了全球性的定義。

聯合國教科文組織於2021年11月底通過的開放科學建議書。

圖／UNESCOUNESCO針對開放科學的定義與說明很長（參見建議書第7頁至第16頁），我們無意在最後的篇幅中細說。

但很清楚的一點是，「開放研究資料」（openresearchdata）是構成UNESCO「開放科學」定義的一部分。

身為國際社群的一員，台灣有許多的跨國研究計畫，過去兩年的防疫，亦受益於國際的開放研究資料許多（如使用GISAID資料庫進行研究）。

國內研究社群與開放研究資料或開放科學的國際標準接軌，既是必須，亦是互惠，而研究資料管理將是達成此目標不可免的基本功。

在「開放科學」取得重大國際進展的此時，再次回顧本次工作坊的內容，應是一件更饒富意義的事。

開放科學建議書：開放科學的定義–包含「開放研究資料」。

圖／UNESCO註釋：Whytheworldneedstoembraceopenscience?https://www.weforum.org/agenda/2021/10/why-open-science-is-the-cornerstone-of-sustainable-development/參考文獻：ScienceEurope/研究資料寄存所（depositar）.（2021）.ScienceEurope研究資料管理指南|RDMGuidesfromScienceEurope（Version2021-07-20T01:56:13.956317）[Dataset].Retrievedfromhttps://data.depositar.io/dataset/se_rdm_guidesSpichtinger,D.（2021）.DataManagementPlansinHorizon2020:whatbeneficiariesthinkandwhatwecanlearnfromtheirexperience.OpenResearchEurope2021,1-42.https://doi.org/10.12688/openreseurope.13342.1UNESCO（2021）.UNESCORecommendationonOpenScience.https://unesdoc.unesco.org/ark:/48223/pf0000379949.locale=en2021研究資料管理工作坊。

http://odw.tw/2021/王家薰（2021）。

研究資料管理概論。

https://m.odw.tw/u/odw/m/rdmw2021-4-3-p/李明旭（2021）。

永續學門DMP試辦計畫。

https://m.odw.tw/u/odw/m/rdmw2021-2-2-p/柯智仁（2021）。

讓資料的價值被看見能否鼓勵資料的管理與開放？https://m.odw.tw/u/odw/m/rdmw2021-1-1-p/劉子明（2021）。

以氣候變遷資料服務為導向的資料管理計畫。

https://m.odw.tw/u/odw/m/rdmw2021-3-1-p/劉璟儀（2021）。

資料管理是否能有SOP－TaiBIF資料庫管理者的視角。

https://m.odw.tw/u/odw/m/rdmw2021-1-2-p/我要跟泛科學說「　　　」！參加泛科學網站體驗調查，提供意見還能拿禮卷！利用阿基米德浮力原理，當玻璃小球浮起時測量氣溫～伽利略溫度計交換禮物大賞！QUALY醉愛北極熊酒瓶塞廢材大作戰！科學實驗室EP5—手作神器如虎添翼數學好無聊、不實用，到底為什麼要學數學？給大人玩的理財桌遊，從此航向財富自由！交換禮物首選、推理迷必買！台灣推理作家協會20週年限定週邊相關標籤：depositar中研院研究資料研究資料寄存所資料管理資料管理方案資料處理資訊科學開放科學熱門標籤：量子電腦BNT疫苗珊瑚諾貝爾獎前列腺所有討論 1登入與大家一起討論#1狐禪2021/12/23回覆這管理包括偵錯及除錯嗎？盡信資料不如無資料，對吧。

研究資料寄存所(depositar)25篇文章・ 6位粉絲＋追蹤研究資料寄存所(depositar)是由研究人員建立的線上資料儲存庫。

所有人都能使用這個平台，自由地儲存、尋找、再次使用研究資料。

RELATED相關文章研究資料亂到不行？你需要的是「資料管理方案」——淺談什麼是「開放科學」理財投資不嫌「早」？學校沒教的孩童理財課在這裡ft.布萊恩兒童商學院布萊恩老師【科科聊聊EP72】海上救援和逃生演習——和平號順利歸航│環球科學札記(58)一起「南漂」吧！「沙崙智慧綠能科學城」展現未來城市新面貌ft.臺南市政府經濟發展局長陳凱凌【科科聊聊EP73】TRENDING熱門討論即時熱門跟名偵探學習推理—回溯推理與貝氏定理分析（下）111小時前海上救援和逃生演習——和平號順利歸航│環球科學札記(58)111小時前眼皮長出如紫色眼影般的紅疹？——認識「皮肌炎」與肺纖維化111小時前研究資料亂到不行？你需要的是「資料管理方案」——淺談什麼是「開放科學」119小時前核廢料放我家？高階核廢料的危險性與處理方式84天前「恆水創電」聯手比利時Turbulent研發超低落差機組——力拼「微水力發電」扎根台灣！42021/12/15腸道炎會導致憂鬱症？——淺談體內的腸腦軸線，揭露腸道菌的「腦控」機制！42021/12/15人類是96%的大猩猩嗎？——《生命之鑰：一場對生命奧祕的美麗探索》32021/12/05