新未名空间

弃婴千枝 写了： 2025年 2月 23日 12:58 计算机连1/3都不能表达，更别提pi了

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

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

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

wdong 写了： 2025年 2月 21日 06:58 人脑子想出来的东西真是非常amazing!
有的数是数
有的数是程序
有的数是问题，而且没有程序可以算它

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

drifter 写了： 2025年 2月 23日 18:38 第一次听到群环域时 感觉尼玛之前学的数学都是工程 这玩意才是数学 高屋建瓴 庖丁解牛

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

drifter 写了： 2025年 2月 23日 18:38 第一次听到群环域时 感觉尼玛之前学的数学都是工程 这玩意才是数学 高屋建瓴 庖丁解牛

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

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

forecasting 写了： 2025年 2月 23日 18:35 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/

Caravel 写了： 2025年 2月 23日 22:31 不可计算数根本不是一个实数的问题，而是一个问题的结果能不能计算。比如那个Chaitin‘s probelm，跟数字有个毛关系。我觉得这个不可计算数就是一个not well defined的概念。@弃婴千枝

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

牛河梁 写了： 2025年 2月 22日 14:06 太阳底下没有新鲜事。你这个问题（哲学上）撕了几千年了。至今仍然是一个妥协，互有胜负。

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

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

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

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

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

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

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

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

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

弃婴千枝 写了： 2025年 2月 23日 12:06 你就一民科，每天哔哔哔computability

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

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

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

弃婴千枝 写了： 2025年 2月 23日 12:58 所谓不可计算，是不可以用turing机计算，因为turing机是有限字长的数字计算机，你用过计算机就知道，计算机连1/3都不能表达，更别提pi了，这些就是所谓的不可计算数

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

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