写出尽可能长的循环
最近我在一次技术讨论中被问到这个问题。考虑到要运行的机器/体系结构，计算科学中可以编写的最长的可能循环是多少？ 这个循环必须尽可能长，但不是无限循环，并且不应该最终导致程序崩溃（递归等...）
我真的不知道如何解决这个问题，所以我问他这实际上是否可能。他说，使用一些计算机科学概念，你可以得出一个假设的数字，这可能不切实际，但它仍然不会是无限的。
这里有人；知道如何分析/解决这个问题。
PS 为可以存储最高数值的类型选择一些最高限制显然不是一个答案。
提前致谢，
Recently I was asked this question in a technical discussion. What is the longest possible loop that can be written in computational science considering the machine/architecture on which it is to run? This loop has to be as long as possible and yet not an infinite loop and should not end-up crashing the program (Recursion etc...)
I honestly did not know how to attack this problem, so I asked him if is it practically possible. He said using some computer science concepts, you can arrive at a hypothetical number which may not be practical but nevertheless it will still not be infinite.
Anyone here; knows how to analyse / attack this problem.
P.S. Choosing some highest limit for a type that can store the highest numerical value is apparently not an answer.
Thanks in advance,
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您正在进入图灵机领域。
简而言之（让我们留在确定性领域......）您的计算机/机器可以处于算法期间传递的有限数量的状态。每个状态都是唯一的，并且只出现一次，否则根据定义，您将陷入无限循环。就像“转到”。
我们可以消除这个限制，但这没有多大意义，因为这样就可以找到一个简单的算法，它总是比所有其他可能的算法多运行一次循环。
所以这取决于机器可能的状态，你可以天真地将其翻译为“它的内存”。
所以现在的问题是：机器上可以处于 X 种状态的最长可能循环是多少？维基百科给出了答案
You are getting into the field of turing machines.
Simply put (lets stay in the deterministic fields...) your computer/machine can be in a finite number of states that are passed during the algorithm. every state is unique and only occours once, otherwise you would by defnition have an endless loop. like "goto".
we can remove that limitation, but it would not make much sense because then a trivial algorithm can be found that always has one more loop runs than every other possible algorithm.
so it depends on the machines possible states which you could naively translate by "its ram".
so the question now is: whats the longest possible loop on a machine that can be in X several states? and wikipedia gives the answer
请阅读 Busy Beaver 问题。
http://en.wikipedia.org/wiki/Busy_beaver
Please read up on the Busy Beaver problem.
http://en.wikipedia.org/wiki/Busy_beaver
最大可能的有限值？作为一名数学家，我觉得这很荒谬。也许这个问题可以得到更好的解释。
The largest possible finite value? As a mathematician, I find that ridiculous. Perhaps the problem could be explained better.
如果我们谈论的是语言限制，那么，有些语言定义了任意精度的整数（例如 Python 和 Common Lisp），因此只要语言允许，您就可以计算出您喜欢的任何数字。您可以轻松地将其设置为对于任何实际机器来说太大，但这不是语言限制。
就实际机器而言，这取决于可能状态的数量。对于可以分配为计数器的每一位（并且它不必作为一个数据元素，因为制作任意长度的计数器确实很容易），这是两种状态，因此如果您有 8G 可用内存，您可以用它来算一下 2^8G 之类的东西。您当然可以使用文件系统来获得更多计数器空间。
或者，假设您没有使用物理可逆计算，您可以检查翻转一点所需的最小能量，除以可用能量（例如预期的总太阳能输出或其他），并得到一个限制。
指定复杂度的图灵机是有限制的。它上升得相当快。
有太多可能的答案，无法一一提供。
If we're talking about language limitation, well, some languages define arbitrary-precision integers (like Python and Common Lisp), so you could count up to any number you liked as far as the language goes. You could easily set it too large for any actual machine, but that's not a language limitation.
As far as counting on actual machines go, it's a matter of the number of possible states. For each bit you can allocate as a counter (and it doesn't have to be as one data element, since it's real easy to make an arbitrary-length counter), that's two states, so if you had 8G of memory available you could count to something like 2^8G with it. You could of course use the file system for more counter space.
Or, assuming you're not using physically reversible computation, you could check the minimum energy necessary to flip a bit, divide the amount of energy available (like the total expected solar output or whatever), and get a limit.
There is a limit for Turing machines of specified complexity. It goes up pretty fast.
There's too many possible answers to provide one.
如果“长”意味着时间，那么以下有限循环应该是一个不错的选择：
好吧，这个答案并不是很严肃，但实际上我的观点是，在工作面试中提出这个问题是完全没有用的。为什么？根据 S.Lott 的回答，这可能与 Busy Beaver 问题有关，该问题已有近 50 年历史，而且完全不为人知，因为没有人能在实际工作中使用它。
If "long" means time, the following finite loop should be a good bet:
Okay this answer is not really serious, but actually my opinion is that the question is totally useless to ask in a job interview. Why? According to S.Lott's answer, this could be about the Busy Beaver problem which is almost 50 years old and is totally unknown because nobody could make use of it in a real job.