必然停机语言生成的数的增长率最高是多少?
葛立恒数吧
全部回复
仅看楼主
level 6
比如只允许for 静态数量循环,内部即使改变循环变量,也不改变循环次数的语言。
a=4
for a
for a
a=a*a
第一次,执行4平方4次,得到4^8。
第二次,将这个数平方这个数次,得到(4^8)^(2*4^8)
如此执行四次。
增加行数,至少能到ω。
似乎没有比不停的for 更好的程序。
接下来引入函数,但是不能递归,引入数组。
或者引入生成程序的程序,
print "for "
print "a"
甚至print "print"
结果输出一个程序,然后运行这个程序,直到不可运行/常数
2026年01月31日 15点01分 1
level 1
CKO=ω_1^CK。因为程序不能模拟自身,有限行代码生成函数的最高增长率就是CKO。
2026年02月02日 12点02分 2
level 7
和语言的定义密切相关,停机次数等于该语言所能描述的最高递归序数,有点类似证明论序数
2026年02月08日 09点02分 3
例如普通嵌套循环是ω^ω 多变量嵌套循环是e0 允许对一个停机函数运算生成另一个更高的停机函数,差不多是SHO
2026年02月08日 09点02分
1