在brainfuck程序中检测无限循环

我用MATLAB脚本语言编写了一个简单的brainfuck解释器.它被随机的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上的+和 - 的完成次数的天真检查会说-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

dancavallaro.. 73

阿兰图灵想和你谈谈.

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

1> dancavallaro..：

---

阿兰图灵想和你谈谈.

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

---

@dancavallaro,哈哈.让我吐出我的饮料,我笑得很厉害.

2> Svante..：

---

当我使用线性遗传编程时,我只使用了一个程序在其生命周期中允许执行的指令数的上限.我认为这在两个方面是明智的:无论如何我无法真正解决停顿问题,而且计算时间太长的程序无论如何都不值得花更多时间.

---

"无论如何,我无法真正解决停止问题,"这是一个不错的轻描淡写:)

---

DampeS8N:如果它没有停止,它永远不会给出答案,因此永远不会解决问题.

3> shsmurfy..：

---

假设您确实编写了一个程序,可以检测该程序是否会在无限循环中运行.让我们说为了简单起见,这个程序是用brainfuck编写来分析brainfuck程序的(虽然这不是以下证据的前提条件,因为任何语言都可以模仿brainfuck,而brainfuck可以模拟任何语言).

现在让我们说你扩展了检查程序来制作一个新程序.当它的输入无限循环时,这个新程序立即退出,并在其输入在某个时刻退出时永远循环.

如果你自己输入这个新程序,结果会是什么？

如果这个程序在运行时永远循环,那么通过它自己的定义,它应该在以自身作为输入运行时立即退出.反之亦然.检查程序不可能存在,因为它的存在意味着矛盾.

如前所述,您基本上是在重述着名的暂停问题:http: //en.wikipedia.org/wiki/Halting_problem

埃德.我想说清楚,上面的反对不是我自己的,但基本上是1936年阿兰图灵给出的着名的反抗.

4> Aur Saraf..：

---

bf中的状态是单个字符数组.

如果我是你,我会在每个"]"(或一次在兰德(1,100)"]"s*"中获取bf解释器状态的哈希值,并断言哈希集合是唯一的.

第二次(或更多)时间,我看到一个哈希,我把整个国家放在一边.

第三(或更多)时间我看到一个哈希,我将整个状态与保存的一个(s)进行比较,如果有匹配,我就退出了.

在每个输入命令('.',IIRC)上,我重置我保存的状态和哈希列表.

优化是仅对所触摸的状态部分进行哈希处理.

我还没有解决暂停问题 - 我在运行程序时检测到无限循环.

*rand是使检查独立于循环周期

---

如果我退出之前遇到的哈希,我就有机会停止有限的程序.虽然可以说这个机会有多么现实,但我认为如果没有大量的研究,它可以被宣布为太小而无关紧要.