在brainfuck程序中检测无限循环
我用MATLAB脚本语言编写了一个简单的brainfuck解释器。 它是随机提供的程序来执行（作为遗传算法项目的一部分）。 我面对的问题是，程序在相当数量的情况下变成了无限循环，因此遗传算法陷入了困境。
所以，我需要一种机制来检测无限循环并避免在bf中执行该代码。
一个明显的（微不足道的）案例是我有
[]
我可以检测到这一点，并拒绝运行该程序。
对于非平凡的情况，我发现基本思想是：确定循环的一次迭代如何改变当前单元格。 如果变化是负的，我们最终会达到0，所以这是一个有限循环。 否则，如果变化是非负的，那是一个无限循环。
在单循环的情况下实现这一点很简单，但是嵌套循环变得非常复杂。 例如（以下（1）中指的是单元格1的内容等）
++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[ While( (1) is non zero)
-- Decrease (1) by 2
>[ While( (2) is non zero)
- Decrement (2)
<+ Increment (1)
>]
(2) would be 0 at this point
+++ Increase (2) by 3 making (2) = 3
<] (1) was decreased by 2 and then increased by 3, so net effect is increment
因此代码可以继续运行。 然而，对单元格1中完成的+和 - 的数量进行天真的检查会发现-s的数量更多，因此不会检测到无限循环。
任何人都可以想到一个好的算法来检测无限循环，给出任意数量的循环在bf中的任意嵌套？
编辑：我知道停止问题一般无法解决，但我不确定是否不存在特殊情况例外。 就像，也许Matlab可能作为一个超级图灵机器能够确定停止bf程序。 我可能是可怕的错误，但如果是这样，我想知道如何以及为什么。
第二次编辑：我写了我所谓的无限循环检测器。 它可能会错过一些边缘案例（或者不太可能，以某种方式从图灵的魔掌中逃脱），但似乎现在对我很有用。 在伪代码形式中，这里是：
subroutine bfexec(bfprogram)
begin
Looping through the bfprogram,
If(current character is '[')
Find the corresponding ']'
Store the code between the two brackets in, say, 'subprog'
Save the value of the current cell in oldval
Call bfexec recursively with subprog
Save the value of the current cell in newval
If(newval >= oldval)
Raise an 'infinite loop' error and exit
EndIf
/* Do other character's processings */
EndIf
EndLoop
end
当我使用线性遗传程序设计时，我只使用了单个程序在其生命周期中允许执行的指令数量的上限。 我认为这在两方面是明智的：无论如何，我无法真正解决暂停问题，计算时间过长的程序无论如何都不值得花更多时间。
艾伦图灵想和你说一句话。
http://en.wikipedia.org/wiki/Halting_problem
假设您编写了一个程序，可以检测该程序是否会以无限循环运行。 比方说，为了简单起见，这个程序是用brainfuck来分析brainfuck程序的（虽然这不是以下证明的先决条件，因为任何语言都可以模拟brainfuck和brainfuck可以模拟任何语言）。
现在让我们假设你延长检查程序来创建一个新程序。 当它的输入无限循环时，这个新程序会立即退出，并且当它的输入在某个点退出时会永久循环。
如果你自己输入这个新程序，结果会是什么？
如果这个程序在运行时永远循环，那么通过它自己的定义，它应该在以自己作为输入运行时立即退出。 反之亦然。 检查程序不可能存在，因为它的存在意味着矛盾。
如前所述，您基本上重述了着名的停止问题：http://en.wikipedia.org/wiki/Halting_problem
埃德。 我想清楚表明，上述反对并不是我自己的，但实质上是1936年艾伦图灵提出的着名反对意见。
链接地址: http://www.djcxy.com/p/67863.html