不可计算数的意义？

[AnonymityFreedom]

计算机连1/3都不能表达，更别提pi了

你说的是大众常见的编程语言。 很多代数符号系统早就已经能表示你说的问题了。

[forecasting]

关于Turing Machine等等在葵花宝典那个版有一个系列，因为突然没那么大兴趣了，就没再写下去。看机会吧。
viewtopic.php?t=627134

先占位，兴致来了再写。
先上定义，讨厌的定义，可以浏览一下或者跳过，等把相关的内容都说清楚了再回来看。第三个是个动态图示的材料，直观多了：
https://plato.stanford.edu/entries/turing-machine/

https://en.wikipedia.org/wiki/Turing_ma ... ne%20model.

动态图示，直观
https://turingmachine.io/

[forecasting]

可计算数是，给定一个位数n，总有Turing Machine在有限的时间内给出这n位数字，如1/7，自然数底e，圆周率π都有这样的特点，所以都是可计算数。
可计算数包括，所有的自然数，所有非自然数的有理数，所有非有理数的代数数，部分超越数如e等。换言之不可计算数都是超越数，但超越数未必是不可计算数，不可计算的超越数有不可数无限个。

[forecasting]

人脑子想出来的东西真是非常amazing!
有的数是数
有的数是程序
有的数是问题，而且没有程序可以算它

不可计算数真的存在吗？除了让我们避开他们，还有什么有用的地方吗？有没有问题像求根一样，去虚数那里绕一绕，但是最后出来了实数。

Chaitin‘s constant Ω又叫magic number，如果知道了它，数学命题就都知道了真假。
https://en.wikipedia.org/wiki/Chaitin%27s_constant

还有一个busy beaver的函数或其输出构成的集合，也有类似作用：
https://en.wikipedia.org/wiki/Busy_beaver

Hartmanis-Stearns conjecture和Roth定理应该是相通的，不过现在没人能够证明其相通：

Hartmanis-Stearns conjecture
https://rjlipton.com/2012/06/15/why-the ... till-open/

Roth定理
https://en.wikipedia.org/wiki/Roth%27s_theorem

Tao关于这定理的博客
https://terrytao.wordpress.com/2010/04/ ... s-theorem/

[drifter]

第一次听到群环域时 感觉尼玛之前学的数学都是工程 这玩意才是数学 高屋建瓴 庖丁解牛

[牛河梁]

第一次听到群环域时 感觉尼玛之前学的数学都是工程 这玩意才是数学 高屋建瓴 庖丁解牛

群环域之后就到格，然后就是布尔代数（逻辑），开始进入西爱死了。

以后自动机、图灵机那些现在怕没有什么小年轻懂了。

[牛河梁]

可计算数是，给定一个位数n，总有Turing Machine在有限的时间内给出这n位数字，如1/7，自然数底e，圆周率π都有这样的特点，所以都是可计算数。
可计算数包括，所有的自然数，所有非自然数的有理数，所有非有理数的代数数，部分超越数如e等。换言之不可计算数都是超越数，但超越数未必是不可计算数，不可计算的超越数有不可数无限个。

思维开阔一点。不要总想着计算机（图灵机）只是算数学物理里的数字。可以是任何能用数字表示的东西。

就像楼主说的，数也可以标记程序（过程）。算数也可以看作是定理证明（找程序）。

然后就知道不可计算数（的存在）对你提出的判定定理为真（证明）或假（证伪）有什么意义了。

然后才能明白图灵的博士论文有何意义。

[forecasting]

第一次听到群环域时 感觉尼玛之前学的数学都是工程 这玩意才是数学 高屋建瓴 庖丁解牛

群环域乃至格是经典数学里代数学的内容，图灵机，可计算数，不可计算数，c. e. 集， creative set， simple set， immune set， productive set，基数，序数等等是数理逻辑的内容，叫数学基础，中文里的基础数学就是指的纯数学，跟数学基础不是一回事。格在经典数学的代数学和其他学科比较少用，反倒是在数学基础的数理逻辑常见。

[forecasting]

群环域乃至格是经典数学里代数学的内容，图灵机，可计算数，不可计算数，c. e. 集， creative set， simple set， immune set， productive set，基数，序数等等是数理逻辑的内容，叫数学基础，中文里的基础数学就是指的纯数学，跟数学基础不是一回事。格在经典数学的代数学和其他学科比较少用，反倒是在数学基础的数理逻辑常见。

Vladimir Voevodsky开创的Univalent Foundations和Homotopy Type Theory融合经典数学和数理逻辑为一体
For general information on Univalent Foundations and Homotopy Type Theory
see Homotopy Type Theory website and Vladimir Voevodsky’s homepage
https://www.ias.edu/math/sp/univalent/goals

这个项目说了好几次了，没人在意。

[forecasting]

对了，现在的数字计算机乃至不可能实现的量子计算机都是弱图灵机，因为它们的内存外存都是有限的，而图灵机的带长或格子数是无限的。

[forecasting]

理清自己思想，说明白自己意思，教给别人知识或者技术，做研究，一个好办法就是找一个极简的例子，对照这个例子和自己的思想，自己的意思，知识或技术，要研究解决的问题，会省很多力气。

[Caravel]

Chaitin‘s constant Ω又叫magic number，如果知道了它，数学命题就都知道了真假。
https://en.wikipedia.org/wiki/Chaitin%27s_constant

还有一个busy beaver的函数或其输出构成的集合，也有类似作用：
https://en.wikipedia.org/wiki/Busy_beaver

Hartmanis-Stearns conjecture和Roth定理应该是相通的，不过现在没人能够证明其相通：

Hartmanis-Stearns conjecture
https://rjlipton.com/2012/06/15/why-the ... till-open/

Roth定理
https://en.wikipedia.org/wiki/Roth%27s_theorem

Tao关于这定理的博客
https://terrytao.wordpress.com/2010/04/ ... s-theorem/

不可计算数根本不是一个实数的问题，而是一个问题的结果能不能计算。比如那个Chaitin‘s probelm，跟数字有个毛关系。我觉得这个不可计算数就是一个not well defined的概念。@弃婴千枝

[forecasting]

我老愿意打字回复就很够意思了，毫无理由怀疑，算了，不说了。

[红烛歌楼]

搞数学的都是什么神人？净搞一些稀奇古怪的问题。就算没有也要自己个捣鼓出一个，然后解决不了扔给后人，然后后人复难后人也！
1000以内，只有196这个数特别，就是196+691（196颠过来）=887，和再加颠过来的和，887+788=1675……如此重复，至少加10亿次，也加不出回文数。别的数加卜加卜就出现了回文数
比如：864+468=1332，1332+2331=3663回文数

[wdong]

不可计算数根本不是一个实数的问题，而是一个问题的结果能不能计算。比如那个Chaitin‘s probelm，跟数字有个毛关系。我觉得这个不可计算数就是一个not well defined的概念。@弃婴千枝

我倾向于认同你这个说法。Chaitin's problem的答案是一个数。这个problem不可计算求解，其实就是不存在一个把这个问题对应到数上面的映射（其实就是程序）。也就是说这个问题的答案是不是个数都不知道。

我还是稍微做了点research的。我问了chatgpt，这个Chaitin常数是不是一个well-defined number。ChatGPT给出了证明，但是这个证明我觉得是错的。因为Chaitin常数的定义是：

$$
\Sigma = \sum_{p halts} 2^{-|p|}
$$

也就是对于所有可停机的程序$p$求和，|p|是程序的字符串长度。

好了，这个"p halts"本身就是个不可计算的东西。我认为所有依赖"p halts"的证明都不是严格的证明。

If we agree that a well-defined problem is a problem whose answer exists in theory (under the framework of Turing machine). Then "whether p halts" is not a well-defined problem. And the computation of Chaitin constant, depending on "whether p halts", is naturally not a well-defined problem either.

[wdong]

换了种说法。

Given any real number within (0, 1), can you construct a Turing machine whose Chaitin's constant approaches this number within any arbitrary precision?

ChatGPT认为是可以做到的。也就是说构造Chaitin值逼近某个给定常数的图灵机是可计算的。

[forecasting]

搞数学的都是什么神人？净搞一些稀奇古怪的问题。就算没有也要自己个捣鼓出一个，然后解决不了扔给后人，然后后人复难后人也！
1000以内，只有196这个数特别，就是196+691（196颠过来）=887，和再加颠过来的和，887+788=1675……如此重复，至少加10亿次，也加不出回文数。别的数加卜加卜就出现了回文数
比如：864+468=1332，1332+2331=3663回文数

为了人类心智的荣耀。

不是回答题主主题相关的东西，就是为了解释数学家为啥无事生非。就像下棋打扑克，真是没事找事。

[tfusion]

太阳底下没有新鲜事。你这个问题（哲学上）撕了几千年了。至今仍然是一个妥协，互有胜负。

首先，需要规范化一下表述。你说的不可计算数（通常）指不可在可数步骤里通过可数前提（公理）算/推导出来的数。这样的数当然存在。而且有现实（物理）意义（并引出数学大问题）。

因为以前和弃婴提起过，弃婴一直都没懂的样子。所以这里再码一些字。

物理定律里隐含假设了物理量是连续的（老牛简称之为实空间，包括多维实空间，包括虚数空间）。

问题在于，这个隐含只是一个信仰。无法用物理实验证明。无论怎么设计物理实验，无论做多少次物理实验。

每一个物理实验，每一次物理实验，都等效于一次计算。建立了输入到输出的一个映射。试验次数是可数的，因此输出结果集也是可数的。可数集显然比物理定律希望的实空间要小。

如果我们能做（可数）无限种不同物理实验，每种做（可数）无限次物理，但时间有限的实验，结论仍然一样（通用图灵机），存在不能被实验覆盖的结果（不可计算数）。

在这里，有的数是输入，有的数是输出，有的数是程序（如第几号物理实验，第几次实验）。多说一句，因为实验只有可数次，哪怕输入是实空间，物理实验也只覆盖了比实空间小可数可能的输入集。

因此，物理定律的实空间不能被物理实验所证实。类似于哥德尔定理（存在不能被证明或证伪的定理）。

这也是当前所谓量子计算的嗨过头的原因所在。因为如果量子计算结果是可数的，量子计算只是一种加速。也是老牛为什么基于多粒子上的虚拟粒子量子计算“有希望”的原因所在。

牛妈还是懂一点的

量子计算再怎么搞没有脱离图灵机，只不过变成不确定图灵机，计算能力没有任何增加。

[tfusion]

你就一民科，每天哔哔哔computability

还可计算不可计算，这一概念只停留在turing机上面，turing机需要探讨computability是因为turing机是有限位的数字机不是模拟机，你企图把世界也描述成一个有限位的turing机，实在是可笑的民科

早跟你说了，真实世界需要的限制是self adjoint,也就是说需要用real number而不是computability来描述，real自身包含computable和不computable。

一句话，computability之所以对计算机行业重要是因为turing机是有限位的数字机不是模拟机，你理解不了，我怀疑你估计连计算机专业都没学明白过

弃婴毕竟不是CS科班

去量子力学那边装逼就算了，跑CS也要装逼。难道是无所不知的圣人？

首先，“turing机是有限位的数字机”就是错的。图灵机不是有限位的。现实生活造不出这种图灵机，实际都是有限位的。

所以现实中的计算机严格说来计算能力等同于正规表达式，离图灵机差之甚远。何况“AI”。图灵机上的AGI一点希望都没有。

不是CS科班出身的最好认真学学可计算性。不然凭拍脑袋发言贻笑大方

[tfusion]

所谓不可计算，是不可以用turing机计算，因为turing机是有限字长的数字计算机，你用过计算机就知道，计算机连1/3都不能表达，更别提pi了，这些就是所谓的不可计算数

那么真实世界是不是这样的？你妈，受过教育脑子不抽抽的都知道，这世界圆周率真的是个无理数，根号2真的存在。。。

所谓可计算不可计算，只是turing机造成的问题

你用的计算机根本算不上图灵机。只是个正规机，有限模拟图灵机而已。