1. 有些問題根本不可能通過計算機解決，不管計算機有多強大或人類程式員有多聰明

2. 不可計算問題

2.1. 20世紀30年代末

3. 計算機軟體的可靠性

3.1. 通常的情況

3.2. 糟糕的情況

4. 可以證明不可能

4.1. 可以證明不可能存在一個能偵測所有計算機程式中所有潛在崩潰的自動化軟體檢查器

4.2. 反證法（Proof by Contradiction）

4.3. 實驗前提

5. 發現崩潰的不可能性

5.1. 圖

5.2. 假設名為CanCrash.exe的程式能分析其他程式并判定它們是否會崩潰

5.3. 讓CanCrash.exe崩潰

5.4. 轉換成一個更模糊的程式稱為CrashOnSelf.exe

5.5. 轉換成AntiCrashOnSelf.exe

5.6. 矛盾

6. 停機問題和不可判定性

6.1. 停機問題（The Halting Problem）

6.2. 不可判定問題

6.3. 不可判定性對計算機使用的實際影響

7. 人腦

7.1. 如果你相信人腦在原則上能被計算機模擬，那么人腦就會和計算機受相同的限制

7.2. 從科學觀點來看，人腦和計算機之間似乎沒有什么基本壁壘，因為化學和電子信號在人腦中傳輸的低級細節很好理解

7.3. 多種哲學論據暗示，人腦創造“理智”的物理程序在性質上與計算機能模擬的任何物理系統有所不同

讀改變未來的九大演算法筆記08_并非萬能的演算法

1. 有些問題根本不可能通過計算機解決，不管計算機有多強大或人類程式員有多聰明

2. 不可計算問題

2.1. 20世紀30年代末

2.1.1. 美國人阿隆佐·邱奇

2.1.1.1. Alonzo Church

2.1.1.2. 在計算理論上的突破性作業至今仍是計算機科學許多方面的基礎

2.1.1.3. 單獨發現了不可判定問題的存在

2.1.1.3.1. 比圖靈早幾個月發表了自己的成果

2.1.1.3.2. 邱奇的公式更為抽象，且并未詳盡地提及由機器執行的計算

2.1.2. 英國人阿蘭·圖靈

3. 計算機軟體的可靠性

3.1. 通常的情況

3.1.1. 即便高質量、撰寫良好的軟體都會做些偏離其原有目的的事

3.2. 糟糕的情況

3.2.1. 軟體崩潰，你丟失了正在處理的資料或檔案

4. 可以證明不可能

4.1. 可以證明不可能存在一個能偵測所有計算機程式中所有潛在崩潰的自動化軟體檢查器

4.2. 反證法（Proof by Contradiction）

4.2.1. 假設懷疑某個宣告S為假，但你想確信無疑地證明其為假，你先假設S為真

4.2.2. 你先假設S為真

4.2.3. 通過進行一些推理，你得出某個宣告T也必須為真

4.2.4. 如果已知T為假，就出現了矛盾

4.2.5. 這能證明你的原始假設（S）也必為假

4.2.6. S匯出T，但T為假，因此S為假

4.3. 實驗前提

4.3.1. 任何程式可以將任何檔案作為輸入運行，但輸出結果通常為亂碼，除非輸入檔案本該配合由你選擇運行的程式

4.3.2. 計算機程式作為檔案被存盤在計算機磁盤上，因此一個程式可以用另一個程式作為其輸入檔案運行

4.3.3. 計算機程式能將其自身檔案作為輸入運行

5. 發現崩潰的不可能性

5.1. 圖

5.2. 假設名為CanCrash.exe的程式能分析其他程式并判定它們是否會崩潰

5.2.1. 作為輸入的程式會在某種情況下崩潰，CanCrash.exe就會輸出“yes”并結束

5.2.2. 如果輸入程式永不會崩潰，CanCrash.exe就會輸出“no”并結束

5.3. 讓CanCrash.exe崩潰

5.3.1. 改變后的程式為CanCrashWeird.exe

5.3.1.1. 如果輸入會崩潰，那么CanCrashWeird.exe這個程式也會故意崩潰

5.3.1.2. 如果輸入永不會崩潰，則CanCrashWeird.exe會輸出“no”

5.4. 轉換成一個更模糊的程式稱為CrashOnSelf.exe

5.4.1. 只關注程式在將自身作為輸入時運行的表現

5.4.1.1. 會檢測其輸入程式，如果輸入程式能在自身上運行，則CrashOnSelf.exe會故意崩潰

5.4.1.2. 反之，CrashOnSelf.exe會輸出“no”

5.5. 轉換成AntiCrashOnSelf.exe

5.5.1. 如果其輸入在自身上運行時崩潰，AntiCrashOnSelf.exe就會輸出“yes”

5.5.2. 如果輸入在自身上運行時不崩潰，AntiCrashOnSelf.exe就會故意崩潰

5.6. 矛盾

5.6.1. AntiCrashOnSelf.exe將自己作為輸入運行時會輸出什么？

5.6.1.1. 如果輸入崩潰，AntiCrashOnSelf.exe就會輸出“yes”

5.6.1.2. 因為如果AntiCrashOnSelf.exe已經崩潰，它就不能成功地輸出“yes”并結束

5.6.1.3. 如果輸入不崩潰，則AntiCrashOnSelf.exe應崩潰

5.6.1.4. 排除了AntiCrashOnSelf.exe兩種可能的行為，這也意味著AntiCrashOnSelf.exe一開始就不可能存在

5.6.2. 假設CanCrash.exe存在必為假

6. 停機問題和不可判定性

6.1. 停機問題（The Halting Problem）

6.1.1. 已有計算機程式最終是否會結束或“停止”的問題

6.2. 不可判定問題

6.2.1. 不能通過撰寫計算機程式解決的問題

6.2.2. 你不能撰寫一個名為AlwaysHalts.exe，輸入永遠停止時輸出“yes”，反之輸出“no”的計算機程式

6.3. 不可判定性對計算機使用的實際影響

6.3.1. 不可判定性只關注計算機程式能否生成答案，并不考慮我們需要等答案多久

6.3.2. 許多可判定任務還沒有高效演算法

6.3.2.1. 著名的要數旅行商問題（Traveling Salesman Problem），簡稱為TSP

6.3.2.1.1. 假設你必須飛往很多城市，你應該采用哪種順序訪問城市才能讓飛行費用最少

6.3.2.2. 問題可判定這一事實并不意味著我們可以在實踐中解決它

6.3.3. 大部分時間里都能很好地解決不可判定問題

6.3.3.1. 通常能為不可判定問題找到非常有用的部分解決方案

6.3.3.2. 軟體可靠性提升部分得益于崩潰發現程式的進步

7. 人腦

7.1. 如果你相信人腦在原則上能被計算機模擬，那么人腦就會和計算機受相同的限制

7.1.1. 會存在人腦無法解決的問題——不管這個人腦有多聰明或經過多么良好的訓練

7.2. 從科學觀點來看，人腦和計算機之間似乎沒有什么基本壁壘，因為化學和電子信號在人腦中傳輸的低級細節很好理解

7.3. 多種哲學論據暗示，人腦創造“理智”的物理程序在性質上與計算機能模擬的任何物理系統有所不同