在Brainfuck程序中检测无限循环 [英] Detecting infinite loop in brainfuck program

问题描述

我已经用MATLAB脚本语言编写了一个简单的 brainfuck 解释器。它被馈送给随机的bf程序以执行（作为遗传算法项目的一部分）。我面临的问题是，程序在相当多的情况下都出现了无限循环，因此GA陷入了困境。

因此，我需要一种机制来检测无限循环并避免在bf中执行该代码。

一个明显的（琐碎的）情况是当我有

I have written a simple brainfuck interpreter in MATLAB script language. It is fed random bf programs to execute (as part of a genetic algorithm project). The problem I face is, the program turns out to have an infinite loop in a sizeable number of cases, and hence the GA gets stuck at the point.
So, I need a mechanism to detect infinite loops and avoid executing that code in bf.
One obvious (trivial) case is when I have

[]

我可以检测到并拒绝运行该程序。

对于简单的情况，我发现基本思想是：确定循环的一次迭代如何更改当前单元格。如果变化为负，则最终我们将达到0，所以这是一个有限循环。否则，如果更改为非负数，则为无限循环。

对于单循环，实现起来很容易，但是对于嵌套循环，则变得非常复杂。例如，（在下面的（1）中是指单元格1的内容，等等。）

I can detect this and refuse to run that program.
For the non-trivial cases, I figured out that the basic idea is: to determine how one iteration of the loop changes the current cell. If the change is negative, we're eventually going to reach 0, so it's a finite loop. Otherwise, if the change is non-negative, it's an infinite loop.
Implementing this is easy for the case of a single loop, but with nested loops it becomes very complicated. For example, (in what follows (1) refers to contents of cell 1, etc. )

++++ 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中任意数量的循环的任意嵌套，一种检测无限循环的好算法的方法？

and hence the code runs on and on. A naive check of the number of +'s and -'s done on cell 1, however, would say the number of -'s is more, so would not detect the infinite loop.
Can anyone think of a good algorithm to detect infinite loops, given arbitrary nesting of arbitrary number of loops in bf?

编辑：我确实知道暂停问题通常无法解决，但是我不确定是否不存在特殊情况例外。就像，Matlab也许可以充当能够确定bf程序暂停的超级图灵机。我可能错得很厉害，但是如果是这样，我想确切地知道如何以及为什么。

I do know that the halting problem is unsolvable in general, but I was not sure whether there did not exist special case exceptions. Like, maybe Matlab might function as a Super Turing machine able to determine the halting of the bf program. I might be horribly wrong, but if so, I would like to know exactly how and why.

第二编辑：我写了我声称是无限循环检测器的东西。它可能错过了一些极端情况（或者不太可能以某种方式逃脱了图灵先生的魔掌），但是到目前为止似乎对我来说还是有用的。
以伪代码形式出现：

SECOND I have written what I purport to be infinite loop detector. It probably misses some edge cases (or less probably, somehow escapes Mr. Turing's clutches), but seems to work for me as of now. In pseudocode form, here it goes:

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

推荐答案

当我使用线性遗传编程时，我只是为允许单个程序的指令数使用上限在其一生中要做。我认为这在两个方面是明智的：无论如何我都无法真正解决停顿问题，而计算时间太长的程序也不值得花更多时间。

When I used linear genetic programming, I just used an upper bound for the number of instructions a single program was allowed to do in its lifetime. I think that this is sensible in two ways: I cannot really solve the halting problem anyway, and programs that take too long to compute are not worthy of getting more time anyway.

这篇关于在Brainfuck程序中检测无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！