我这个数,有TREE(3)大么?

我这个数,有TREE(3)大么?

BF语言的运行过程我没有看得很明白,没有C++之类的普通代码好懂。但既然BF是图灵完备的语言,那你的A(x)就是一个类似忙碌海狸函数的东西,也就是增长率会超过所有可计算函数。TREE函数仍然是可计算的,所以增长率必然远低于A(x)。

你后面的B函数如果以A(x)为f(x),相当于给图灵机增加了一个谕示机,就可以计算图灵机更高的问题,所以增长率应该比忙碌海狸函数更高。单纯的套娃在这个阶段来说,增长率基本上没有影响了,因为套娃是递归的过程,只对可计算函数有值得一提的影响。但你把前面的函数作为f(x)输入后面的B函数这是有效的套娃,因为每套一次,就有了一个更强大的谕示机,图灵度就会升一级。

不过这里的增长率高是针对x→∞来说的。对于不太大的x,因为BF这东西太简洁,可能增长率并没有想象的快。虽然S(x)的增长率远大于忙碌海狸函数,更不用说TREE了,但对于特定数值如S(10^100),不是很清楚是否很大。因为乘法这么简单的东西,这种语言就套了几层循环。