我写了一个简单的脑残 http://en.wikipedia.org/wiki/BrainfuckMATLAB 脚本语言的解释器。它被输入随机的 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