反证法（归谬法）：先假设命题的否定形式成立，然后再进行推理，引出矛盾。 矛盾：命题P和它的否定形式非P都成。 examples：证明不存在最大的整数、质数是无穷的。
可数（countable/enumerable)：集合的元素是有限的，或者集合中的所有元素都与正整数一一对应（即元素可一一列出）。
可数集合examples： 1)有限集合是可数的； 2)0以上的所有偶数的集合是可数的； 3)所有整数的集合是可数的（正负数交互编号）; 4)所有有理数的集合是可数的； 5)程序（符合编程语言语法的有限字符的排列）的集合是可数的；
不可数集合：元素不能与1以上的整数（1,2,3….）一一对应的集合； 无论采用什么对应规则，总会有遗漏的元素。
不可数集合examples： 1)“所有整数数列（无穷个整数的排列）的集合”是不可数的；[对角论证法，康托尔] 2)“所有实数的集合”…. 3)“所有函数的集合”….
处理无穷集合的“个数”使用一一对应方法，因为一一对应是既无“遗漏”也无“重复”的对应。
不可解问题：”原则上不能用程序来解决的问题“
关于存在不可解问题的讨论： ”输入1以上的整数时，输出一个整数的函数“的集合不可数； 所有程序的集合可数； 二者不能一一对应（函数“个数”比程序“个数”多） 故，在输入1以上的整数时，输出一个整数的函数中，存在无法用程序表达的函数。
对角论证运用不当的例子： “所有能用程序生成的整数数列的集合”是可数的。[图灵] （虽然可以用对角论证法做出一个整数数列不包含在表中，但不能保证此数列是“能用程序生成的”，正如证明“有理数是可数的”一样，不能保证做出的肯定是有理数） 注：有理数是整数和分数的集合，整数也可看做是分母为一的分数。 有理数的小数部分是有限或为无限循环的数。不是有理数的实数称为无理数，即无理数的小数部分是无限不循环的数。
停机问题 程序的行为有两种：Data->Program->1)Result;2)永不结束运行。 程序本质是计算机存储设备上的数据。 “处理程序的程序”examples： 1)compiler（转换程序的程序） 2)source code checker（读取程序的程序） 3)debugger（调试程序的程序） 停机问题（Halting Problem):判断“某程序在给定数据下，是否能在有限时间内结束运行”的问题。
判断程序是否会结束运行的程序HaltChecker： 1)必须准确判断给定的程序会如何运行； 2)还可能需要根据给定的数据模拟程序的运行； 3)它自身必须要在有限时间内结束运行。 根据以上条件，不能通过实际运行 对象程序来进行判断。（因为若是对象程序永不结束，则判断程序也永远得不出判断结果）
停机问题是不可解的，能普遍解决停机问题的程序不存在。[反证法]
SelfLoop(p) { halts=HaltChecker(p,p); if(halts){ while(1>0){ } } }当程序作为数据输入，例如 假设SelfLoop(SelfLoop)会结束 => halts=false =>HaltChecker(SelfLoop,SelfLoop)=false => SelfLoop(SelfLoop)不会结束，矛盾！
