logo标签列表

检测Brainfuck程序中的无限循环

algorithminterpreterinfinite-loophalting-problembrainfuck
25

我用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上执行的"+"和"-"的数量进行天真的检查会导致错误，因为"-"的数量更多，所以无法检测到无限循环。 有人能想出一种好的算法来检测无限循环吗？在bf中嵌套任意数量的循环。
编辑：我知道一般情况下停机问题是无法解决的，但我不确定是否不存在特殊情况的例外。例如，Matlab可能作为超图灵机器能够确定bf程序的停机。我可能错了，但如果是这样，我想知道具体的原因和原因。
第二个编辑：我编写了一个据称为无限循环检测器的东西。它可能会忽略一些边缘情况（或者不太可能逃脱Turing先生的魔爪），但目前似乎对我还有效。用伪代码的形式，它如下：
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
3
Matlab 不能超过图灵机，因为它运行在图灵机（计算机）上。由于状态受限，Aur Saraf详细介绍的快照方法应该可以奏效，尽管最坏情况很糟糕，但BF中许多无限循环应该能够被迅速检测出来。 - Nick Johnson
2
如果指针下的值不是0，那么 "[]" 循环将永无止境。是的，在指针的值只能为“0”的位置使用它将是无用的（例如在程序开头），但这并不一定是错误。 - Skilldrick
超图灵机是什么东西呢？也许你指的是“Stannett, M. 1990. X-Machines and the Halting Problem: Building a Super-Turing Machine. Formal Aspects of Computing, 2, 331-341.”这篇论文吧？ - DrBeco
1
我认为你在句子“递归调用subprog的bfexec函数”出现了问题。如果它发现一个无限循环，它可能会一直运行下去。这个问题被称为停机问题，目前还没有已知的解决方案。 - DrBeco
2
你的算法在 +>+<[>] 循环中如何避免错误停止？进入该循环时，cell[0] = cell[1] = 1，指针为0；因此oldval = 1。在第一次迭代结束时，指针为1，newvalue = cell[1] = 1，而oldval >= newval。然而，在另外一次迭代中，指针为2，cell[2] = 0（假设所有单元格都初始化为0），因此如果程序被允许运行，它将正常终止。 - Griffin
9个回答
77
3
@dancavallaro，笑死我了，我都喷出来了。 - mmcdole
1
除了@NasBanov之外，还可以查看软件救援停滞程序和基于路径的无限循环检测方法。 - Joshua Drake
我已经看到这个误解很多次了...感谢@NasBanov带来的更正。 - mmgp
1
@NasBanov 计算线性有界自动机停机所需的内存大于其本身可用的内存。因此，除非更大的线性有界自动机模拟较小的线性有界自动机，否则仍然无法解决该问题。尽管如此，这个问题仍然不切实际可解。 - Cruncher
@Cruncher，我不明白 - 你在争论什么？BF是一台具有有限内存的确定性机器。问题是关于在另一种语言中实现BF的实际操作，这不是通用机器，并且不受BF虚拟机的限制。需要相对较少的额外内存（~ VM内存）来检测无限循环。因此，是的，OP所询问的是可能的，而dancavallaro回复否定了这种可能性是错误的。 - Nas Banov
27

当我使用线性遗传编程时，我只限制了单个程序在其生命周期内允许执行的指令数量上限。我认为这种做法有两个合理之处：我本来就无法解决停机问题，而且需要太长时间计算的程序根本不值得再花更多时间。

我选择这个作为答案，因为它与我的情况最相关。我认为我已经写了一个无限循环检测器，但可能会错过一些情况（或者更不可能的是，以某种方式逃脱了图灵的掌握）。我将很快在问题中发布那段代码。 - Sundar R
17
“我无法真正解决停机问题”是一个很好的轻描淡写的说法 :) - user3850
你嫉妒了吗？运行程序，如果它停止了，那么它就不是无限的。有问题吗？ - DampeS8N
3
如果它不停止，就永远不会给出答案，因此永远无法解决问题。 - Svante
+1 超时时间可以根据复杂度、行数和相对于应用程序上下文的优先级设置为实时，例如有一些进程正在进行大爆炸模拟，计划在超级计算机上运行几年。 - Khaled.K
15
假设你编写了一个程序，可以检测另一个程序是否会进入无限循环。为了简化问题，我们假设这个程序是用brainfuck编写的，用于分析brainfuck程序（尽管这不是以下证明的前提条件，因为任何语言都可以模拟brainfuck，而brainfuck可以模拟任何语言）。
现在，假设你扩展了检查程序以创建一个新程序。当输入无限循环时，这个新程序立即退出，并且当输入在某一点上退出时，它将永远循环。
如果你将这个新程序输入到自身中，结果会是什么？
如果这个程序在运行时永远循环，那么根据它自己的定义，当以自身作为输入运行时，它应该立即退出。反之亦然。检查程序不可能存在，因为它的存在本身就意味着矛盾。
正如之前提到的，你实际上是在重新阐述著名的停机问题：http://en.wikipedia.org/wiki/Halting_problem 注：我想澄清以上的证明不是我自己的，而是艾伦·图灵在1936年提出的著名证明。
1
如果Brainfuck程序具有无限内存，每个单元格可以存储无限大的数字，或者两者都具备，则该程序是图灵完备的。 - user522860
7

bf中的状态是一个由单个char组成的数组。

如果我是你，我会在每个“]”（或随机出现1到100个“]”*）时对bf解释器状态进行哈希，并断言哈希集合是唯一的。

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

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

在每个输入命令（例如“。”）上，我都会重置我的已保存状态和哈希列表。

优化的方法是仅对触及的状态部分进行哈希。

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

*随机数是为了使检查独立于循环周期。

1
由于BF程序具有有限状态，因此这实际上可以工作（尽管我认为您使它比需要的更复杂 - 只需在每个]上散列状态并在遇到以前遇到的哈希时退出），只要存储是有限的，它最终将检测到任何无限循环。 - Nick Johnson
3
如果我在遇到哈希之前退出，我就有可能在有限的程序上停止。尽管这种机会是否实际存在有争议，但我认为如果没有进行充分的研究就宣称这种可能性微不足道是不合理的。 - Aur Saraf
4

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

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

软件救援停滞程序，一种基于路径的无限循环检测方法。 - Joshua Drake
3
正如先前提到的，这是停机问题。 但在你的情况下可能有解决方案：所考虑的停机问题是关于图灵机的，该机器具有无限的内存。
如果你知道自己的内存上限（例如，你知道你不会使用超过10个内存单元），那么你可以执行你的程序并停止它。这个想法是计算空间限制了计算时间（因为你不能在一步中写入多个单元）。当你执行了尽可能多的步骤后，你就可以停止了，例如，如果你有3个单元，每个单元有256个条件，那么你最多可以有3^256种不同的状态，因此你可以在执行这么多步骤后停止。但要小心，还有隐含的单元，比如指令指针和寄存器。如果你保存每个状态配置，并且一旦检测到一个已经存在的状态，那么你就进入了一个无限循环。这种方法在运行时间上肯定更好，但需要更多的空间（在这里哈希配置可能更合适）。
是的。每个具有256个状态的3个单元格为256256256 = 16777216，对于计算机而言并不算是很大的数字。 - dancavallaro
1
然而，由于brainfuck使用如此简单的结构，即使是最小的程序也可能需要数十到数百个单元。例如，在brainfuck中乘以两个数字需要大约30个单元。任何有趣的brainfuck程序都不适合用这种方式进行分析。 - shsmurfy
1
@shsmurfy - 你如何进行乘法运算？两个单元格的乘法可以使用两个临时单元格完成。 - Chris Lutz
3

这不是停机问题，但即使在一个只有1000个单元的BF机器上，试图检测停机也仍然不合理。

考虑以下程序：

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

这个程序不会重复，直到填满整个内存，即使只有1000个单元，也需要大约10^300年才能完成。

2
如果我没记错的话，停机问题的证明只对涉及自我引用的一些极端情况成立。然而，仍然很容易展示一个实际例子，说明为什么你无法制作一个无限循环检测器。
以Fermat's Last Theorem为例。可以轻松地创建一个程序，遍历每个数字（或在这种情况下是3个数字），并检测它是否是该定理的反例。如果是，则停止，否则继续执行。
因此，如果你有一个无限循环检测器，它应该能够证明这个定理，以及许多其他定理（如果它们可以被简化为搜索反例的话，也许所有其他定理都可以）。
一般来说，任何涉及遍历数字并仅在某些条件下停止的程序，都需要一个通用的定理证明器来证明该条件是否可能被满足。这是最简单的循环情况。
这是一个非常有见地的答案，我不确定为什么它没有得到赞同。 - bitconfused
你对FLT的推理是错误的。即使我们为普通计算机（而不是无限TM）拥有无限循环检测器，我们也无法解决FLT，因为反例可能太大而无法适应内存或磁盘！一般来说，停机问题只对无限机器是不可判定的。我们可以编写一个算法来解决像我们这样具有有限内存的计算机的停机问题，它将在某个有限时间内终止。 - xrisk
1

就我个人而言（可能有误），我认为在不实际执行程序的情况下检测程序是否存在无限循环会有一定难度。

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

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接