超宇宙吧 关注:2,949贴子:42,872

入坑大数入门,感觉自己知识十分匮乏,各种看不懂

只看楼主收藏回复

希望得到各位的指点,目前最主要的几个问题
1.E#表示法里面最后#作了复杂的代数运算后如何处理?
2.为什么一个函数不可计算,它的函数增长率就会快于一切可计算的函数?
3.序数表示那里的对角化没有看懂
现在BEAF和鸟之记号正在艰难地继续看,希望有热心的吧友回答一下这些问题233


IP属地:广东来自Android客户端1楼2017-07-08 16:05回复
    对于①可以看这个http://zh.googology.wikia.com/wiki/%E8%B6%85E%E7%AC%A6%E8%99%9F ,对于②可以看这个第二部分https://www.zhihu.com/question/53024250/answer/133198972,里面明确提到不可计算则为没有算法能达到!至于③对角化是两者构成一一对应关系,数学上称为同型,不能够成对应则一方内涵于另一方。


    IP属地:广东来自Android客户端2楼2017-07-08 20:02
    回复
      2025-09-04 02:22:27
      广告
      不感兴趣
      开通SVIP免广告
      好吧第三问更清晰地了解看这个,我们不能坐井观天


      IP属地:广东来自Android客户端3楼2017-07-08 20:08
      回复
        IP属地:广东来自Android客户端4楼2017-07-08 20:08
        收起回复
          怎么没人了(⊙o⊙)…


          IP属地:广东来自Android客户端5楼2017-07-12 12:46
          收起回复
            这个《大数入门》的错漏太多了,所以初学者才会有某些疑问。
            先说2.
            不可计算函数的增长率不一定快于一切可计算的函数。有的不可计算函数,增长率快于一切可计算的函数,比如Σ函数;有的不可计算函数,增长率并不快,比如Σ函数的一种逆——“写入n个格子所需的2色图灵机的最小状态数”函数。
            再说1.
            E# 记号的表述是有问题的。按照《大数入门》里的表述,在#^^# 之后就会出现这样的问题:
            a^^(b+1) = a^(a^^b),所以按照这个定义,Ea#^^(#+1)b 应该展开成Ea#^(#^^#)b ,然后就是Ea#^(#^^b)a ,大概只有Ea#^^#(b+1) 这么点增长率,比Ea#^^#*#b 还弱,没有太大的提升。
            其根本原因在于,像# 、ω、X这样的符号,它们的威力在于它们展开时的数值能够随着表达式中的底数的增大而增大。这次ω展开成2,下次可以展开成8,下下次可以展开成比Graham数还大的数,诸如此类(如果你知道Goodstein序列,你会对此有一点体会)。如果把ω、X这样的符号套进超运算里面,因为a{c}b = a{c-1}(a{c}(b-1)),接着立刻就得展开a{c}(b-1)。照这样不断地递归下去,b总是会下降到所有的ω都被展开的程度;更重要的是,这些下降的过程是连续进行的,不等待底数的增加就进行,就会导致所有的ω都展开成同一个数,从而失去了它原有的威力。
            E# 记号的真正定义,采用了一个复杂的算符:">"算符。按照真正的定义,#^^## 会展开成#^^#>#^^#>…#^^#>#^^# ,其中#^^#># 又能展开成((…(#^^#)^^#…)^^#)^^# ,这样中间的(#^^#) 就得很久以后才会被再次展开,从而下一次展开的时候能被更大的数替代。
            顺带一提,基于同样的缘由,BEAF在n^^n&n以后就无法继续定义下去了。不建议阅读。
            最后说3.
            对角化并非序数的专利,而是几乎所有大数记号之中都会自然而然出现的一种方式。
            就拿fast-growing hierarchy(就是《大数入门》里用到序数的那个记号)来说好了。f_0(n) = n+1,f_1(n) = 2n,f_2(n) = n×2^n,它们的函数名分别为f_0、f_1、f_2。
            f_n(n)可以超越一切f_k(n)(其中的k为固定值,n为自变量)。不论k取多少,自变量n总是会有超过k的时候,那时便有f_n(n) > f_k(n)。这一点和Cantor最初在对角论证法中的说明有些类似,因而得名。
            但是,f_n可不能作为一个函数的记号,因为这里面还有n这个自变量。可是无论把这个字母“n”换成什么数字,都会落入f_k(n)那样的境地。于是,我们需要一个新的记号去表示能够随时随地转化成“任意大的”n的东西。这个记号在fast-growing hierarchy里是ω,在E# 记号里是# ,在BEAF里则是X。


            IP属地:北京6楼2017-07-14 09:10
            收起回复
              大佬还在看大数入门么,一起学习下,多谢


              IP属地:上海7楼2017-12-10 16:28
              回复
                赶紧跳坑,确实个大坑,逻辑陷阱


                来自Android客户端9楼2018-04-19 19:16
                收起回复
                  2025-09-04 02:16:27
                  广告
                  不感兴趣
                  开通SVIP免广告
                  大数入门在哪里买啊


                  来自手机贴吧11楼2019-07-30 19:12
                  收起回复
                    楼主,你还在研究大数吗?


                    IP属地:四川来自Android客户端12楼2019-08-28 21:21
                    收起回复
                      大数入门这本书有出处吗?论文需要引用,急!


                      来自Android客户端13楼2019-09-09 09:26
                      收起回复
                        超阶乘数阵的增长率远远大于鸟数阵。


                        IP属地:四川来自Android客户端14楼2019-09-20 22:05
                        回复


                          IP属地:四川来自Android客户端15楼2019-09-20 22:11
                          回复


                            IP属地:四川来自Android客户端16楼2019-09-20 22:11
                            收起回复