對角線删除法

今日在家看到一篇講圖靈機停機問題的文章，在如何證明停機問題是個悖論命題的時候，用到了對角線删除法，看這種方法的時候感覺似曾相識，終于想起來大學的時候講實數不可列性的時候，也用過這樣的方法。   命題：實數集合是不可列的。 證明思路：隻要證明出來[0,1]是不可列的即可，使用反證法，假設成立，然後構造出來一個反例即可。 證明過程：假設[0,1]是可列的，則[0,1]區間中的任何一個數都可以表示成以下的形式： 0.1 = 0.a11a12a13......a1n 0.2 = 0.a21a22a23......a2n ...... 0.n = 0.an1an2an3.....ann 下面構造一個實數，該實數的aii與上面數的aii均不相同，則從構造過程中可以看出來新構造的數屬于[0,1]，但是不在上述清單内。得證。   這種證明方法針對矩陣型規則問題的證明特别管用，當某個問題可以描述為一個矩陣類型的時候，則可以嘗試構造一個反對角線元素，看看該元素是否能被此規則覆寫住