algorithm - 在 brainfuck 程序中检测无限循环

Question

我写了一个简单的brainfuck MATLAB 脚本语言的解释器。它被输入随机 bf 程序来执行(作为遗传算法项目的一部分)。我面临的问题是，在相当多的情况下，程序会出现无限循环，因此 GA 会卡在该点。
所以，我需要一种机制来检测无限循环并避免在 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 上对 + 和 - 的数量进行天真的检查会说 - 的数量更多，因此不会检测到无限循环。
如果在 bf 中任意嵌套任意数量的循环，谁能想出一个好的算法来检测无限循环？

编辑:我确实知道停机问题通常无法解决，但我不确定是否不存在特殊情况异常(exception)。就像，也许 Matlab 可以用作 super 图灵机，能够确定 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

Answer 1

Alan Turing 想和你谈谈。

http://en.wikipedia.org/wiki/Halting_problem