brainfuckプログラムで無限ループを検出

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

質問

私は、MATLABスクリプト言語で簡単な brainfuck のインタプリタを書かれています。ランダム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で行わ-'sは、しかし、-'sの数が多いので、無限ループを検出しないと言うでしょう。
誰もがBFのループの任意の数の任意のネスト与えられ、無限ループを検出するための良いアルゴリズムを考えることができますか？

編集：私は、停止問題は、一般的に解決不可能であることを知っていますが、私は、特殊なケースの例外が存在していなかったかどうかわかりませんでした。同様に、多分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
役に立ちましたか？

解決

私は線形遺伝的プログラミングを使用する場合は、

、私はただ一つのプログラムがその一生の間に行うことを許可された命令の数の上限を使用していました。私は本当にとにかく停止問題を解決することはできません、と計算に時間がかかりすぎるのプログラムは、とにかく多くの時間を得ることの価値がありません。

：私は、これは2つの方法で賢明だと思います。

他のヒント

アラン・チューリングはあなたと言葉を持っているしたいと思います。

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

あなたがこのプログラムが無限ループで実行するかどうかを検出することができるプログラムを書いたとしましょう。 （任意の言語がbrainfuckをエミュレートすることができ、brainfuckは、任意の言語をエミュレートすることができるので、これは以下の証明の前提条件ではありませんが）のは、このプログラムはbrainfuckプログラムを解析するためにbrainfuckで書かれたことを簡単にするために言ってみましょう。

さて、あなたが新しいプログラムを作るチェッカープログラムを拡張しましょう。この新しいプログラムは、その入力が無限にループしたときにすぐに出て、その入力がある時点で終了したときに永遠にループします。

あなた自身に入力この新しいプログラムをした場合、結果はどうなりますか？

実行すると、このプログラムは永遠にループする場合は、入力として自分自身を実行すると、

、その後、独自の定義によって、それはすぐに終了する必要があります。およびその逆。その存在そのものが矛盾することを意味するのでチェッカープログラムは、おそらく、存在しないことができます。

は、前述したように、あなたは基本的に有名な停止問題を修正再表示されます。 http://en.wikipedia.org/wiki/Halting_problemする

エド。私は上記の反証は自分ではなく、基本的にアラン・チューリングが1936年に戻った有名な反証であることを明らかにしたい。

BF状態が文字の単一のアレイである。

私があなただったら、

、私は、「]」すべての上BFインタプリタ状態のハッシュを取る（または一度ランド（1、100）「]」S *の）とハッシュのセットが一意であることを主張するだろう。

私は特定のハッシュを参照して第二の（またはそれ以上）の時間は、私はさておき、全体の状態を保存します。

私は特定のハッシュを参照して第三（またはそれ以上）の時間は、私が保存されて1（S）への全体の状態を比較し、一致があるのならば、私は辞めます。

すべての入力コマンドに（「」、IIRC）私は私の保存された状態とハッシュのリストをリセットします。

最適化だけ感動した状態の一部をハッシュすることです。

私は停止問題を解決していない - 私は無限ループにを検出していますのプログラム

を実行中。

*ランドは、ループ期間のチェックを独立させることです。

無限ループを検出することはできないが、プログラムがあまりにも多くの時間がかかっている場合は、検出することができます。

カウンタをインクリメントすることにより、あなたが実行するたびにコマンド（例えば<、>、+、-）のタイムアウトを実装します。カウンタは、あなたが観察によって設定されたいくつかの大規模な数に達すると、あなたはそれがあなたのプログラムを実行するのに非常に長い時間がかかると言うことができます。あなたの目的のために、「非常に長い」と無限の良い十分な近似である。

すでに述べたように、

これは停止問題です。 しかし、あなたの場合にソリューションがあるかもしれません：停止問題が考慮され、無制限のメモリを持つチューリングマシン、についてです。

。

あなたはメモリの上限を（例えば、あなたが10個の以上のメモリセルを使用していけない知っている）持っていることを知っている場合は、あなたのプログラムの開発を実行し、それを停止することができます。アイデアは（あなたが1つのステップで複数のセルを書きカントとして）計算空間の境界の計算時間ということです。あなたはできるだけ多くの手順を実行した後、あなたは別のメモリ構成を持つことができるよう、あなたは破ることができます。例えば。あなたは256回の条件で3個の細胞を、持っている場合、あなたは、せいぜい3 ^ 256個の異なる状態を持つことができ、そのため、あなたは、多くのステップを実行した後に停止することができます。しかし、注意してください、命令ポインタやレジスタなどの暗黙の細胞が、あります。あなたはすべての状態の設定を保存し、できるだけ早くあなたがすでに持っていた、あなたはinfiteループを持っているものを、検出している場合は、それも短いん。このアプローチは、実行時に間違いなくはるかに優れているが、そのためには、（ここでは設定をハッシュするために適しているかもしれません）かなり多くのスペースを必要とします。

このしかし、1000年の細胞BFマシンのような限られたマシンでも、停止を検出しようとすると、まだ合理的ではない、停止問題ではありません。

このプログラムを考えてみます：

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

それだけで1000個の細胞のために約10 ^ 300年かかるメモリの全体をいっぱいにするまで、このプログラムは繰り返しません。

私の頭の上オフは（と私は間違っている可能性が）、私は実際にプログラム自体を実行せずにプログラムが無限ループを持っているかどうかを検出することは困難で少しと思うだろう。

プログラムの部分の条件付き実行は、プログラムの実行状態に依存するように、実際にプログラムを実行することなく、プログラムの特定の状態を知ることは困難であろう。

あなたがいない場合は、が必要の無限ループでプログラムが実行されることを、あなたは「命令が実行され、」カウンターを持ってみてください、とだけ命令の有限数を実行する可能性があります。この方法では、プログラムが無限ループを持っている場合は、インタプリタが無限ループでスタックしているプログラムを終了することができます。

私の記憶が正しければ、

、停止問題の証拠は、自己参照を含んだいくつかの極端な場合のためにだけ本当でした。しかし、それはあなたが無限ループ検出器を作ることができない理由の具体例を示すために、まだ些細なのです。

フェルマーの最終定理を考えてみましょう。これは、すべての番号（または、この場合は3つの数字）を反復処理するプログラムを作成するのは簡単だし、それは定理に反例ですか否かを検出します。それが停止した場合、それ以外の場合は継続します。

あなたが無限ループ検出器を持っている場合、この定理を証明し、多くの他の多くのことができるはずですので、（彼らは反例を探しに減少させることができるならば、おそらく他のすべて、。）

一般的には、数字を反復し、一部だけの条件の下で停止する必要任意のプログラムは、その条件が今まで会っできるかどうかを証明するために、一般的な定理証明を必要とします。そして、それがループの最も単純なケースがされています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top