作者 LoveSports (我要當一個渣攻)標題 [問卦] 請問要讀什麼書才看得懂這篇時間 Fri Sep 12 20:53:04 2025
請問各位鄉民
以下這篇是某本書的內容 我看了覺得頭有點痛
想請問如果想看得懂這篇要看什麼書？
該不會高中數學有學好的人基本上就看得懂？
先感謝願意指點的鄉民
=======================================
哥德爾、圖靈、馮· 諾伊曼
在此，讓我們介紹為現代電腦科學的發展做出貢獻的三位數學家。他們的功績，至今仍然
是研究人員與學生們頭痛的根源。這三位是：庫爾特· 哥德爾（1906-1978）、艾倫· 圖
靈（1912-1954）、約翰· 馮· 諾伊曼（1903-1957）。
1931年，哥德爾發表的論文給世界帶來了衝擊（其影響至今仍能感受到）。在那之前，數
學家們普遍傾向於認為數學是完美且沒有矛盾的。然而，哥德爾挑戰了這個信念。他證明
了，一個完全且無矛盾的數學體系是不可能存在的。④ 這意味著，一個能夠證明所有真
理的數學體系，是不可能存在的。
舉例來說，讓我們思考一下「我正在說謊」這個命題。請試著思考一下，當說出這句話的
自己本身被包含在這個命題中時，會產生怎樣的矛盾。哥德爾所做的事情，正是如此。他
思考出了一種讓命題可以指涉到該命題自身的機制，並運用它來表示數學體系的不完備性
。
艾倫· 圖靈深受哥德爾證明的啟發，並開始思考那對電腦來說究竟意味著什麼。1937年，
圖靈成功地完成了兩項證明。這兩者都是對電腦科學產生巨大影響的功績。
其中一項證明是：我們不可能創造出一個「通用的電腦程式」，用來判斷任何一個演算法
最終是否會停止——也就是說，計算會不會結束。
這個問題被稱為「停止性問題 (Halting Problem)」，雖然它聽起來可能像是一個特殊問
題，但卻是無處不在的。舉例來說，就算你將防毒軟體安裝到電腦中，想要確認某個程式
會不會對電腦造成不良影響，也會因為停止性問題的存在而不得不放棄。
（譯註：這句話的意思是，想透過執行程式來事先確認電腦不會產生「不具合」（錯誤、
故障），但根據停止性問題的應用，完美的預先檢查是不可能的，這一點已被證明。）
這件事，圖靈在1937年就已經預見到了。
順帶一提，「證明一個演算法會不會結束是不可能的」這項證明，其實非常巧妙，而且完
全是哥德爾思想的延伸。
假設，我們有一個名叫「WILL_HALT」的程式。它可以判定任何一個演算法是否會結束。
然後，我們用它來創造出下面這樣一個小小的電腦程式：
INGAS_ALGORITHM:
If INGAS_ALGORITHM will finish:
Excute this command always
Inga的演算法:
如果Inga的演算法會結束的話:
就永遠執行這個指令
對於 INGAS_ALGORITHM，WILL_HALT 的立場會是怎麼樣的呢？ 如果 INGAS_ALGORITHM 會
結束的話，那麼 INGAS_ALGORITHM 就會永遠地重複下去。也就是說，它實際上是無法結
束的。
看來是陷入自我矛盾了呢（是不是開始頭痛了？）。
因此，像是 WILL_HALT 這樣的程式是不可能存在的。
〔譯註：作者的說明以簡潔易懂為優先。圖靈本人是使用與此稍微不同的、被稱為「對角
線論證法」的論述來進行嚴密證明的。〕
========================================
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 95.173.204.69 (日本)
※ 作者: LoveSports 2025-09-12 20:53:04
※ 文章代碼(AID): #1en1Up6W (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1757681587.A.1A0.html
→ a27588679: 太長 我的耐心只有28個字1F 180.177.33.135 台灣 09/12 20:53
→ greensaru: 我只有廿個字2F 101.10.143.187 台灣 09/12 20:53
→ s999132: 直接告訴我誰要肛誰好嗎3F 36.236.33.6 台灣 09/12 20:54
※ 編輯: LoveSports (95.173.204.69 日本), 09/12/2025 20:55:06
推 GN02209611: 我耐心只有20公分4F 49.218.94.193 台灣 09/12 20:56
推 StylishTrade: 好無聊 故意搞一個矛盾的程式
圖靈在耍寶嗎5F 111.250.158.2 台灣 09/12 20:59
我不知道為什麼他們要做這種事 好像在刁難程式
噓 leviliebe: 識字就能讀懂 光看內容就知道是一般科普書 本來就是設計給一般讀者閱讀的
再說這內容跟高中數學也沒關係 比較接近邏輯或語言哲學的範疇7F 39.9.40.30 台灣 09/12 21:03
好吧 我再重看幾次好了
謝謝各位回答
※ 編輯: LoveSports (95.173.204.69 日本), 09/12/2025 21:09:41
噓 leviliebe: 這本書如有引注 就去看它的參考書目11F 39.9.40.30 台灣 09/12 21:08
→ tuhiceut: 康托法就這樣被作者吃了喔=.=12F 36.229.110.55 台灣 09/12 21:10
是指譯註提到的對角線論證法嗎？
可能怕讀者看不懂吧
他光是寫簡潔易懂版我就頭痛了
※ 編輯: LoveSports (95.173.204.69 日本), 09/12/2025 21:12:20
推 luciffar: 停機問題（英語：halting problem）
https://tinyurl.com/24o4t5f6
希望你不會越看頭越痛 XDDD
理髮師悖論：村子裡有個理髮師，這個理髮師有條原則是，只要村子裡有人不自己刮鬍子，理髮師就給這個人刮鬍子。如果這個人自己刮鬍子，理髮師就不給這個人刮鬍子。無法回答的問題是，理髮師會自己刮鬍子嗎？
停機問題：你不能寫一個程式總是判斷其他程式會不會停，因為可以構造自指程式造成矛盾 → 這就是計算世界的悖論。13F 59.126.87.93 台灣 09/12 21:18
停機問題 - 維基百科，自由的百科全書
停機問題（英語：halting problem）是邏輯數學中可計算性理論的一個問題。通俗地說，停機問題就是判斷任意一個程式是否能在有限的時間之內結束執行的問題。該問題等價於如下的判定問題：是否存在一個程式P，對於任意輸入的程式w，能夠判斷w會在有限時間內結束或者無窮迴圈。
--