1.哥德尔不完备性定理
第一不完备性定理
任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明也不能被否定。
第二不完备性定理
如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。
2.我们可以这样理解，我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误
3.首先，判定一个程序是否会停机，是指：对于其的任意一个输入，可判定其是否停机。那么假定这样的图灵机存在，设为H。其工作过程不妨设为：若对于任意一个程序M可停机则输出1，反之输出0（由于其是可判定的）。那么可以构造另一程序D，其工作过程为：以H输出为输入，若输入为1则不停机，反之停机。
由于H可判定所有程序，那么其也可判定D，若其判定D输入1时不停机，则其输出0，而由于D的定义知它是可停机的，反之亦然。故停机问题无算法解。
4.图灵机是理论模型，是对人计算过程的模拟；而冯诺依曼计算机则是图灵
机的工程化实现，程序就是图灵机中的纸带。目前的可编程计算机都是图灵-冯诺依曼 计算机。
1.哥德尔不完备性定理
第一不完备性定理
任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明也不能被否定。
第二不完备性定理
如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。
2.我们可以这样理解，我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误
3.首先，判定一个程序是否会停机，是指：对于其的任意一个输入，可判定其是否停机。那么假定这样的图灵机存在，设为H。其工作过程不妨设为：若对于任意一个程序M可停机则输出1，反之输出0（由于其是可判定的）。那么可以构造另一程序D，其工作过程为：以H输出为输入，若输入为1则不停机，反之停机。
由于H可判定所有程序，那么其也可判定D，若其判定D输入1时不停机，则其输出0，而由于D的定义知它是可停机的，反之亦然。故停机问题无算法解。
4.图灵机是理论模型，是对人计算过程的模拟；而冯诺依曼计算机则是图灵
机的工程化实现，程序就是图灵机中的纸带。目前的可编程计算机都是图灵-冯诺依曼 计算机。