检测brainfuck程序无限循环

StackOverflow https://stackoverflow.com/questions/367571

题

我写了一个简单的 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上完成-'s然而，要说-'s的人数较多，所以就无法检测到无限循环。结果 谁能想到一个好的算法来检测无限循环，给高炉循环的任意数目的任意嵌套的？

编辑：我知道，停机问题是无法解决的一般，但我不知道是否有不存在特殊情况例外。像，也许Matlab的还不如一个超级图灵机能够确定BF程序停止运行。我可能是可怕的错误，但如果是这样，我想究竟如何以及为什么知道。

SECOND编辑：我已写了什么我声称是无限循环检测器。它可能会缺少一些边缘情况（以下可能，不知何故逃脱图灵先生的离合器），但似乎为我工作，截至目前。 在伪码的形式，在这里不言而喻：

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年还给。

在BF状态是字符的单个阵列。

如果我是你，我会（在兰特（1或一次，100）“]” S *）乘BF解释器状态对每一个散列“]”和断言散列集合是唯一的。

在第二（或更多）时我看到一定的散列，我保存整个状态一边。

在第三（或更多）时我看到一定的散列，我比较全状态到已保存的一个（多个），并且如果有一个匹配，我退出。

在每个输入命令（“”，这个）重置我保存的状态和散列的列表。

这是优化是唯一散列被触摸状态的一部分。

我还没有解决的停机问题 - 我检测无限循环在运行程序

。

*兰特是使检查独立循环周期的

无限循环不能被检测到，但你可以程序是否花费过多时间检测。

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

如已经提及的，这是停机问题。 但是，在你的情况有可能是一个解决方案：停机问题正在考虑是对图灵机，它具有无限的内存

在的情况下，你知道你有存储器的上限（例如，你知道你不使用超过10的存储单元）中，可以执行你PROGRAMM并停止它。这个想法是，在计算空间边界的计算时间（因为你不能写在一步一个以上的小区）。当你尽可能多的步骤执行，你可以有不同的内存配置，你可以打破。例如。如果你有3个单元，256个条件，你最多可以有3 ^ 256种不同的状态，所以你可以执行许多步骤后停止。但要小心，有隐含的细胞，如指令指针和寄存器。你这样做甚至更短，如果你保存每一个国家的配置和一旦你发现一个，你已经有了，你有一个infite环路。这种方法是在definitly运行时间要好得多，但为此需要更多的空间（在这里它可能适用于散列配置）。

这是不停机问题，然而，它仍不能合理尝试检测在这样的有限的机器甚至停止作为1000细胞BF机。

考虑本程序：

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

此程序将不重复，直到它已填满的存储器中的整个这对于刚刚1000个细胞将需要大约10 ^ 300年。

我的头顶部（我可能是错的），我认为这将是困难的一点点来检测程序是否有一个无限循环，而不实际执行程序本身。

作为程序的各部分的条件执行取决于程序的执行状态，这将是很难知道该程序的特定状态，而无需实际执行程序。

如果你不这样做的需要的与一个无限循环的程序来执行，你可以尝试有一个“指令执行”柜台，只有执行的指令数量有限。这样，如果一个节目确实有无限循环，解释器可以终止其陷入无限循环程序。

如果我没有记错，停机问题的证明是只适用于涉及自我参照某些极端的情况也是一样的。但是它仍然是微不足道的表现，为什么你不能让一个无限循环检测一个实际的例子。

费尔马大定理。它很容易地创建，通过每一个数字（或在这种情况下，3个数字）迭代程序，并检测它是否是一个反例的定理。如果是这样它会暂停，否则它继续。

所以，如果你有一个无限循环检测仪，它应该是能够证明这个定理，和许多其他许多（也许是所有其他人，如果他们可以减少到寻找反例。）

在一般情况下，包括通过数字迭代只有一些条件下停止任何程序，就需要一个一般定理证明，以证明如果条件都不能得到满足。这就是循环有最简单的情况下。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top