24

我用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 中任意数量的循环的任意嵌套，谁能想到一个检测无限循环的好算法？

编辑：我确实知道停止问题通常是无法解决的，但我不确定是否不存在特殊情况例外。就像，也许 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
4

9 回答 9

75

艾伦·图灵想和你谈谈。

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

于 2008-12-15T05:52:01.787 回答
26

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

于 2008-12-15T10:21:26.080 回答
14

假设您确实编写了一个程序，可以检测该程序是否会在无限循环中运行。为简单起见，假设这个程序是用brainfuck 编写的，用于分析brainfuck 程序（尽管这不是以下证明的前提，因为任何语言都可以模拟brainfuck，而brainfuck 可以模拟任何语言）。

现在假设您扩展检查程序以创建一个新程序。这个新程序在其输入无限循环时立即退出，并在其输入在某个时刻退出时永远循环。

如果你把这个新程序输入到自己里面，结果会是什么？

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

如前所述，您实际上是在重申著名的停止问题： http ://en.wikipedia.org/wiki/Halting_problem

埃德。我想澄清一下，上述反证不是我自己的，而本质上是艾伦·图灵在 1936 年给出的著名反证。

于 2008-12-15T06:04:31.373 回答
7

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

如果我是你，我会在每个“]”（或一次在 rand(1, 100)“]”s* 中）对 bf 解释器状态进行哈希处理，并断言哈希集是唯一的。

第二次（或更多次）我看到某个哈希值时，我将整个状态放在一边。

第三次（或更多）我看到某个哈希值时，我将整个状态与保存的状态进行比较，如果匹配，我退出。

在每个输入命令（'.'，IIRC）上，我都会重置我保存的状态和哈希列表。

一种优化是只对被触及的状态部分进行哈希处理。

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

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

于 2008-12-15T08:36:51.377 回答
4

无法检测到无限循环，但您可以检测程序是否占用了太多时间。

每次运行命令（例如，、、、）时，通过递增计数器<来实现>超时。当计数器达到您通过观察设置的某个大数字时，您可以说执行程序需要很长时间。出于您的目的，“非常长”和无限是一个足够好的近似值。+-

于 2008-12-15T08:22:03.263 回答
3

如前所述，这是停机问题。但在您的情况下，可能有一个解决方案：正在考虑的停机问题是关于具有无限内存的图灵机。

如果你知道你有一个内存上限（例如你知道你不使用超过 10 个内存单元），你可以执行你的程序并停止它。这个想法是计算空间限制了计算时间（因为您不能一次编写多个单元格）。在您执行尽可能多的步骤后，您可以拥有不同的内存配置，您可以中断。例如，如果您有 3 个单元格，有 256 个条件，则最多可以有 3^256 个不同的状态，因此您可以在执行那么多步骤后停止。但要小心，有隐含的单元格，比如指令指针和寄存器。如果您保存每个状态配置，并且一旦检测到您已经拥有的状态配置，那么您会做得更短，您将拥有一个无限循环。这种方法在运行时肯定要好得多，

于 2008-12-15T06:52:10.917 回答
3

这不是停机问题，但是，即使在像 1000 单元 BF 机器这样有限的机器中，尝试检测停机仍然是不合理的。

考虑这个程序：

+[->[>]+<[-<]+]

这个程序不会重复，直到它填满整个内存，仅 1000 个单元将需要大约 10^300 年。

于 2013-11-04T17:03:24.720 回答
2

如果我没记错的话，停止问题的证明只适用于一些涉及自我引用的极端情况。然而，展示一个为什么你不能制作无限循环检测器的实际例子仍然是微不足道的。

考虑费马大定理。很容易创建一个遍历每个数字（或在本例中为 3 个数字）的程序，并检测它是否是定理的反例。如果是，则停止，否则继续。

因此，如果您有一个无限循环检测器，它应该能够证明这个定理，以及许多其他定理（也许所有其他定理，如果它们可以简化为寻找反例。）

通常，任何涉及迭代数字并仅在某些条件下停止的程序都需要通用定理证明器来证明是否可以满足该条件。这是最简单的循环情况。

于 2015-03-10T10:25:07.470 回答
1

在我的脑海中（我可能是错的），我认为在不实际执行程序本身的情况下检测程序是否具有无限循环会有点困难。

由于程序部分的条件执行取决于程序的执行状态，如果不实际执行程序，将很难知道程序的特定状态。

如果您不需要执行具有无限循环的程序，您可以尝试使用“执行指令”计数器，并且只执行有限数量的指令。这样，如果程序确实存在无限循环，解释器可以终止陷入无限循环的程序。

于 2008-12-15T05:57:45.300 回答