私は、MATLAB スクリプト言語で単純な頭のおかしいインタープリターを作成しました。(遺伝的アルゴリズム プロジェクトの一部として) 実行するランダムな bf プログラムが与えられます。私が直面している問題は、プログラムにかなりの数のケースで無限ループがあることが判明したため、GA がその時点で動かなくなることです。
したがって、無限ループを検出し、そのコードを bf で実行しないようにするメカニズムが必要です。
明らかな（些細な）ケースの1つは、私が持っている場合です
[]
私はこれを検出し、そのプログラムの実行を拒否できます。
自明ではないケースについては、基本的な考え方は、ループの 1 回の反復で現在のセルがどのように変化するかを判断することであることがわかりました。変化が負の場合、最終的に 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 プログラムの停止を判断できるスーパー チューリング マシンとして機能するかもしれません。私はひどく間違っているかもしれませんが、もしそうなら、その方法と理由を正確に知りたいです.
2 番目の編集: 無限ループ検出器であると主張するものを書きました。おそらくいくつかのエッジケースを見逃しています（または、おそらくチューリング氏のクラッチから逃れる可能性は低いです）が、今のところ私にとってはうまくいくようです。疑似コード形式では、次のようになります。
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