豆瓣
扫码直接下载
读过 用数学的语言看世界
[开始证明]使用反证法,假设“存在能判定停止的程序”。所以在输入别的程序P时,这个程序会提醒我们P是否会停止。如果存在能判定停止的程序,那么就可以创建新程序,即当输入P时, (1)如果判定P会停止,那么继续运行。 (2)如果判定P不会停止,那么停止运行。 虽然有点奇怪,不过只要存在能判定停止的程序,就可以创建上述新程序。 那么如果把这个程序本身输入该程序内又会怎么样呢?如果判定结果是该程序会停止,那么必须按照(1)继续运行。但是继续运行的话,那么必须按照(2)停止。因为二者相互矛盾,所以不可能创建这样的程序。[结束证明]” [开始证明]假设第一不完备性定理不正确。那么,所有对于自然数的命题都能被证明或者被否定。图灵机处理的对象是写入磁带的符号,因此程序是否停止这个问题可以解释为处理自然数的命题。那么,可以证明或者否定命题“程序会停止”。因此如果这个步骤替换成程序的话,相当于能创建判定停止的程序。因为不存在能判定停止的程序,所以该命题自相矛盾。由于矛盾是从“第一不完备性定理不正确”的假设中推导而出,因此证明了该定理。[结束证明]引自 第5 章 无限世界与不完备性定理第一不完备性定理:任意一个包含自然数及其算术运算在内的公理中,当这个公理无矛盾时,对于自然数都存在一个命题,它在这个公理中既不能被证明也不能被否定。 第二不完备性定理:任意一个包含自然数及其算术运算在内的公理中,当这个公理无矛盾时,它的无矛盾性不可能在这个公理系统内得到证明。 证明某个公理系统的无矛盾性需要思考更大的公理系统。如果存在更大的公理系统,能够证明某个公理系统无矛盾性的话,可以说这个更大的公理系统比原来的公理系统更“强”。一般情况下很难判定两个给定的公理系统是否属于相同级别。但是,如果是两个满足不完备性定理条件的公理系统,并且使用其中一个公理系统可以证明另一个公理系统的无矛盾性的话,说明其中存在“强弱”关系,从而表明这两个公理系统并不属于相同级别。不完备性定理还有上述作用。。不完备性定理是对于自然数体系的见解,拥有完备且无矛盾的公理系统。例如,实数的加法运算和乘法运算中不存在矛盾。不过在实数的范围中,如果要给作为其中部分集合的自然数下定义的话,在这个理论之内无法证明自身不存在矛盾。所以,不完备性定理是对于包含自然数在内的理论的限定性见解。我们有时会听到类似“哥德尔定理表明了我们的知识是不确定的”的说法,其实这个定理并不具有这种普遍性的意义。引自 第5 章 无限世界与不完备性定理
> 你🥐蝶的所有笔记(56篇)
但是,如果使用这个方法判定300位数是否是素数,因为10^300的平方根是10^150,所以必须一一...
1596年出生的勒内·笛卡儿被誉为近代理性主义的创始人,他给欧几里得的平面几何带来巨大的变...
表示其中内容是对原文的摘抄