写出尽可能长的循环

Question

最近我在技术讨论中被问到了这个问题.考虑到运行它的机器/体系结构,可以在计算科学中编写的最长循环是什么？这个循环必须尽可能长,但不是无限循环,不应该最终崩溃程序(递归等...)

老实说,我不知道如何解决这个问题,所以我问他是否真的有可能.他说使用一些计算机科学概念,你可以得出一个假设的数字,这个数字可能不实用,但它仍然不会是无限的.

这里有人; 知道如何分析/攻击这个问题.

PS为可以存储最高数值的类型选择某个最高限制显然不是答案.

提前致谢,

Answer 1

你正在进入图灵机领域.

简单地说(让我们留在确定性字段中......)您的计算机/机器可以处于算法期间传递的有限数量的状态中.每个州都是独一无二的,只会发生一次,否则你会因为定义而无限循环.喜欢"goto".我们可以删除这个限制,但它没有多大意义,因为可以找到一个简单的算法,它总是比其他所有可能的算法都有一个循环运行.

所以它取决于机器可能的状态,你可以天真地翻译"它的公羊".

所以现在的问题是:什么是可以在X几个状态的机器上最长的循环？和维基百科给出了答案

Answer 2

请阅读Busy Beaver问题.