Dedekind分划/分割定义的实数所成集合基数是多少？

[wdong]

有不可计算数，自然也有不可证明定理。计算和证明是一回事。

P vs NP，既不可证明真，也不可证明假，也不可证明独立。和停机问题等价。构造如下。子程序A用来产生字符串，子程序B用来验证这个字符串是否是有效证明。如果证不出来就一直循环。

我不怕闹笑话。诸位尽管笑。

[forecasting]

有不可计算数，自然也有不可证明定理。计算和证明是一回事。

P vs NP，既不可证明真，也不可证明假，也不可证明独立。和停机问题等价。

我不怕闹笑话。诸位尽管笑。

没笑话，就是有点奇怪而已，觉得国内本科/硕士研究生课程是否都不开或者忽略了这些理论课。

NP vs P或者NPC vs P是个开问题，是千禧年问题之一。一般没人认为它像Godel第二不完备定理一样不可证，也没人证明跟停机问题等价，一般都认为它像黎曼猜想，证明或者否证都困难。只是计算复杂性问题的分层或者牵涉计算复杂性的问题都非常困难，几乎没有几个被结结实实解决了的。当然最近几年也有人猜测是不是在现有公理体系内不可证，不过算少数。一般猜测NP ！= P

前几年有人猜测利用电路复杂性理论能证明NP ！= P，可Razborov 和rudich用 自然证明（natural proof）否定这个想法：https://theory.stanford.edu/~liyang/tea ... d-P-NP.pdf
https://mathoverflow.net/questions/1518 ... and-rudich

现在有希望的道路是利用有限模型论。

这些都很难。除非三十岁左右而且方向是计算复杂性理论，不然注意进展就行，了解进展，利用进展。

[forecasting]

Godel第二不完备定理：For each formal system F containing basic arithmetic, it is possible to canonically define a formula Cons(F) expressing the consistency of F. This formula expresses the property that "there does not exist a natural number coding a formal derivation within the system F whose conclusion is a syntactic contradiction." The syntactic contradiction is often taken to be "0=1", in which case Cons(F) states "there is no natural number that codes a derivation of '0=1' from the axioms of F."

第二不完备定理在第一不完备定理后面：https://en.wikipedia.org/wiki/G%C3%B6de ... s_theorems

[wdong]

没笑话，就是有点奇怪而已，觉得国内本科/硕士研究生课程是否都不开或者忽略了这些理论课。

NP vs P或者NPC vs P是个开问题，是千禧年问题之一。一般没人认为它像Godel第二不完备定理一样不可证，也没人证明跟停机问题等价，一般都认为它像黎曼猜想，证明或者否证都困难。只是计算复杂性问题的分层或者牵涉计算复杂性的问题都非常困难，几乎没有几个被结结实实解决了的。当然最近几年也有人猜测是不是在现有公理体系内不可证，不过算少数。一般猜测NP ！= P

前几年有人猜测利用电路复杂性理论能证明NP ！= P，可Razborov 和rudich用 自然证明（natural proof）否定这个想法：https://theory.stanford.edu/~liyang/tea ... d-P-NP.pdf
https://mathoverflow.net/questions/1518 ... and-rudich

现在有希望的道路是利用有限模型论。

这些都很难。除非三十岁左右而且方向是计算复杂性理论，不然注意进展就行，了解进展，利用进展。

这些问题是很小众的问题，管自己叫CS的人20个里都不会有一个想过这些问题。就跟做数学的人一般也不考虑选择公理和连续统假设一样。

学校一般不开这种课，既没人有本事教，也没多少人愿意学。

[Caravel]

因为你做任何工程都超不出这些定理，肯定不会出问题。但是Hinton啊什么Altman啊还有什么李飞飞就出笑话了，比如说什么AGI，什么达到了人类智能。一解释就是大话，假话，觉得真丢人。不仅丢人，还会觉得已经实现了AGI什么human intelligence，就会成为AI研究的绊脚石，甚至弄出什么AI伦理之内的笑话。



不是举不出例子，而是举出例子所付出的代价太大了，简单一说，做了论证，有不可数无限个，你们又觉得不存在。说过了，物理上的强关联系统/体系有意思，多留意，也可以多讨论。这些就好好用功学一下就足够了。

对了，Fileds奖得主Kontsevich也在这些问题上闹笑话。

你确实举不出来例子，只要你能给出有限长度，有明确结果的例子，我都能用图灵机输出，信不信？

[Caravel]

我其实就是想说这个意思。我先确定epsilon，数轴就分成可数份了。

不可计算并不是无穷精度或者可数不可数的问题。而是问题的答案不知道。

停机问题的答案是0或1，不是无理数，也不可计算。我打算找本数读下。

属实，像pi这样的无限不循环小数，如果没有其他数学定义，就是得一个个往外蹦数字来写，需要无限长无规律字符串才能表示，要输出这样的数字，图灵机做不到而已。

不可计算就是你这个数字都确定不下来。

并不是这个数字多神秘，恰恰是过于平凡。

[牛河梁]

老牛谨慎乐观看好AGI。和P = NP证明，或者普遍接受的CS101的PTIME = NPTIME类似。

对任意给定有限的资源（时间），P肯定都小于NP。但一旦资源到了（可数）无穷，P就等于NP。

AGI也类似。人类的知识是有限的。因此是封闭的。只要模型大得足以覆盖人类所有的知识点，读完所有的定理证明paper，就像训练文生图一样，机器就能做得比任何个人更快更好。

一直以来，所谓的Ai不行，原因都有背景common sense缺乏问题。这也是大模型成功的关键。够大才够暴力。

人类专家也一样。如果不知道可数不可数，或热力学定律，照样会闹造永动机这样的笑话。