重溫圖靈原理，感受反證法的力量

演算法已經無所不在，似乎對於每一個可以用精確的數學術語表達的問題，都有相應的演算法。然而，事實並非如此，實際上有些看似簡單的問題永遠無法透過演算法解決

電腦科學家中的先驅艾倫・圖靈，曾在近一個世紀前的一篇論文中證明了這種「不可計算」問題的存在，他提出了啟動現代電腦科學的計算數學模型。

圖靈用一種違反直覺的策略證明了這個突破性的結果：他定義了一個問題，一個拒絕一切試圖解決它的方法的問題。 「像我問你在做什麼，不管你回答什麼我都會說，『我要做的事情和你說的不一樣』。」麻省理工學院研究理論計算機科學的研究生 Rahul Ilango 說。 重寫後的內容： 圖靈以一種違反直覺的策略證明了這個突破性的結果：他定義了一個問題，這個問題拒絕一切試圖解決它的方法。 「像我問你在做什麼，不管你回答什麼我都會說，『我要做的事情和你說的不一樣』。」麻省理工學院研究理論電腦科學的研究生Rahul Ilango表示

#################################### #圖靈的策略是基於一種具有悠久歷史的數學方法，被稱為「對角線證明」。以下是對他證明背後邏輯的簡化說明#########字串#########對角線證明源自於解決一個關於字串問題的巧妙技巧，字串中每個位元的值可以是0 或1。這個問題的描述是：給定一個字串列表，列表中所有字串都一樣長，如何能產生一個不在列表中的新字串呢？ ######重寫後的內容：一個最直接的策略是依序考慮每個可能的字串。假設有五個字串，每個字串都有五位。首先遍歷檢查清單中是否存在00000。如果不存在，問題就解決了；如果存在，請轉到00001並重複這個過程。這種方法很簡單，但對於長字串所產生的長列表來說速度很慢#######對角線證明是一種可行的替代方法，可以逐步建立不存在的字串。從清單中第一個字串的第一位開始，將其反轉，這將成為新字串的第一位。然後反轉第二個字串的第二位，並將其作為新字串的第二位，重複此操作，直到到達列表的末尾。透過反轉位元的操作，可以確保新字串與原始清單中的每個字串至少有一個不同的位置。 （它們還在字串列表中形成一條對角線，因此被稱為對角線證明。）################對角線證明只需要依次檢查列表中每個字串中的一位，所以通常比其他方法快得多，但它真正的威力在於它能很好地駕馭無限長的字串問題。 ######麻省理工學院的理論計算機科學家Ryan Williams 表示：「雖然字串和清單可以是無限的，但對角化方法仍然是有效的。」######喬治·康托爾是第一個利用這種力量的人，他是集合論數學領域的創始人。 1873年，他利用對角線證明了一些無窮大的值比其他的更大。 60年後，圖靈將此版本的對角線證明應用於計算理論#########演算法的限制性#########為了證明存在一類數學問題是無法透過任何演算法解決的，圖靈提出了一個理論。這類問題有明確定義的輸入和輸出，但沒有確定的過程可以將輸入轉換為輸出。圖靈主要關注決策問題，並為了更好地具象化這個模糊的任務。在決策問題中，輸入可以是由0和1組成的任意字串，而輸出則可以是0或1######確定數字是否為素數（只能被1 和它本身整除）是決策問題的一個例子－ 給定一個代表數字的輸入字串，如果該數字是質數，則正確的輸出為1，如果不是素數，則為0。另一個例子是檢查電腦程式的語法錯誤。輸入字串代表不同程式的程式碼—— 所有程式都可以用這種方式表示，因為這就是它們在電腦上儲存和執行的方式—— 規則是如果程式碼包含語法錯誤，則輸出1，如果不包含，則輸出0。 ######只有當演算法為每一個可能的輸入都產生正確的輸出時，它才能說是可以解決該問題 —— 哪怕失敗一次，它就不是解決該問題的通用演算法。通常，人們會先指定一個想解決的問題，然後試著找出一個解決它的演算法。圖靈在尋找無法解決的問題時，顛覆了這個邏輯—— 他想像了一個包含所有可能演算法的無限列表，並使用對角化來構造一個難題，這個難題與列表上的每一個演算法都對立。 ###

請設想一個由20個問題組成的新問題，回答者不是從一個具體的概念出發，而是依序對每個問題都想出一個不滿足的例子。當遊戲結束時，回答者已經描述了一個完全由問題對立面所組成的命題

圖靈的對角線證明過程，就是要在無限長的演算法列表中，對每一個演算法都進行思考：「這個演算法能解決我們想要證明是不可計算的問題嗎？」，就好像是一種遊戲比賽。 Williams 表示：「這種方式將原來的問題轉化為一種『無限的問題』。」

為了贏得遊戲，圖靈需要設計一個問題，對於每個演算法給出的答案都是否定的。這意味著需要找出使第一個演算法輸出錯誤答案的特定輸入，另一個使第二個演算法失敗的輸入，以此類推。他發現，這些特殊輸入使用了類似於庫爾特・哥德爾(Kurt Gödel) 在不久前在證明像“這個命題是不可證明的”這樣的自我引用斷言會給數學基礎帶來麻煩時，所使用的技巧。

此處的關鍵在於，每個演算法（或程式）都可以表示為 0 和 1 的字串。這意味著，就像在錯誤檢查程式的例子中一樣，演算法可以將另一個演算法的編碼作為輸入。原則上，演算法甚至可以將自己的編碼作為輸入。

這樣一來，我們可以定義一個不可計算的問題，就像在圖靈證明中所提到的問題一樣：「給定一個表示演算法程式碼的輸入字串，當演算法本身的程式碼當輸入時，如果演算法輸出0，則讓其輸出1，否則輸出0。」每個試圖解決這個問題的演算法都會在至少一個輸入上產生錯誤的輸出，也就是與自己的程式碼對應的輸入。這意味著這個反常的問題無法用任何演算法來解決

證明不了什麼的是反證法

電腦科學家對於對角線證明的使用並沒有到此結束。 1965 年，Juris Hartmanis 和 Richard Stearns 改編了圖靈的論點，以證明並非所有可計算問題是平等的 —— 有些問題本質上比其他問題更難。這結果啟動了計算複雜度理論領域，研究計算問題的難度。

複雜性理論的發展揭示了圖靈對角線證明的限制。在1975年，貝克、吉爾和索洛維證明了複雜性理論中許多未解決的問題無法僅透過對角化來解決。其中最重要的是著名的P/NP問題，該問題簡單來說是關於能否在多項式時間內驗證解的正確性以及是否能在多項式時間內求解的問題

對角線證明的局限性是使其如此強大的高抽像水平的直接結果。圖靈的證明並沒有涉及任何在實踐中可能出現的不可計算的問題 —— 相反，問題往往是抽象的。其他對角線證明同樣遠離現實世界，因此它們無法解決現實世界中的問題。

Williams 說：「對角線證明並不是直接觸碰問題本身，就好像用手套箱做實驗一樣。」

對角線證明的頹敗之勢，表明解決P /NP 問題將是一個漫長的旅程。儘管有局限性，對角線證明仍然是複雜性理論家武器庫中的關鍵工具之一。 2011 年，威廉斯將其與一系列其他技術結合起來，證明了某個受限制的計算模型無法解決一些異常困難的問題 —— 這一結果讓困擾了研究人員 25 年的問題得到解決。雖然這與解決 P/NP 問題相去甚遠，但仍代表著重大進展。

如果你想證明某些事情是不可能的，不要低估否定的力量

原文連結：

需要重寫的內容是：https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/

以上是重溫圖靈原理，感受反證法的力量的詳細內容。更多資訊請關注PHP中文網其他相關文章！