24

私は、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
4

9 に答える 9

75

アラン・チューリングはあなたに一言言いたいと思っています。

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

于 2008-12-15T05:52:01.787 に答える
26

線形遺伝的プログラミングを使用したとき、単一のプログラムがその存続期間中に実行できる命令数の上限を使用しただけでした。これは 2 つの点で理にかなっていると思います。いずれにしても停止問題を実際に解決することはできません。また、計算に時間がかかりすぎるプログラムは、いずれにせよ、より多くの時間を費やす価値はありません。

于 2008-12-15T10:21:26.080 に答える
14

このプログラムが無限ループで実行されるかどうかを検出できるプログラムを作成したとしましょう。簡単にするために、このプログラムはbrainfuckプログラムを分析するためにbrainfuckで作成されたとしましょう(ただし、これは次の証明の前提条件ではありません。どの言語でもbrainfuckをエミュレートでき、brainfuckは任意の言語をエミュレートできるためです)。

ここで、チェッカープログラムを拡張して新しいプログラムを作成するとします。この新しいプログラムは、入力が無期限にループするとすぐに終了し、ある時点で入力が終了すると永久にループします。

この新しいプログラムをそれ自体に入力すると、結果はどうなりますか?

このプログラムが実行時に永久にループする場合、それ自体の定義により、それ自体を入力として実行するとすぐに終了するはずです。およびその逆。チェッカープログラムは、その存在自体が矛盾を暗示しているため、存在できない可能性があります。

前に述べたように、あなたは本質的に有名な停止問題を言い換えています:http: //en.wikipedia.org/wiki/Halting_problem

エド。上記の反証は私自身のものではなく、本質的には1936年にアランチューリングが返した有名な反証であることを明確にしておきたいと思います。

于 2008-12-15T06:04:31.373 に答える
7

bf の状態は、単一の文字配列です。

私があなたなら、すべての "]" (または rand(1, 100) "]"s* で 1 回) で bf インタープリター状態のハッシュを取得し、ハッシュのセットが一意であると主張します。

特定のハッシュを 2 回目 (またはそれ以上) 見た場合は、状態全体を保存します。

特定のハッシュを 3 回目 (またはそれ以上) 見たときに、状態全体を保存されたものと比較し、一致する場合は終了します。

すべての入力コマンド ('.'、IIRC) で、保存した状態とハッシュのリストをリセットしました。

最適化は、触れられた状態の部分のみをハッシュすることです。

停止の問題は解決していません。プログラムの実行中に無限ループを検出しています。

*rand は、チェックをループ期間に依存しないようにするためのものです。

于 2008-12-15T08:36:51.377 に答える
4

無限ループは検出できませんが、プログラムに時間がかかりすぎているかどうかは検出できます。

コマンドを実行するたびにカウンターをインクリメントしてタイムアウトを実装します (例: <>+) -。カウンターが、観察によって設定した大きな数値に達すると、プログラムの実行に非常に長い時間がかかると言えます。あなたの目的にとって、「非常に長い」無限は十分な近似です。

于 2008-12-15T08:22:03.263 に答える
3

すでに述べたように、これは停止性問題です。しかし、あなたの場合、解決策があるかもしれません。停止問題は、無制限のメモリを備えたチューリングマシンに関するものであると考えています。

メモリの上限があることがわかっている場合(たとえば、10個を超えるメモリセルを使用しないことがわかっている場合)、プログラムを実行して停止することができます。アイデアは、計算スペースが計算時間を制限するということです(1つのステップで複数のセルを書き込むことはできないため)。さまざまなメモリ構成を持つことができる限り多くのステップを実行した後、中断することができます。たとえば、256個の条件を持つ3つのセルがある場合、最大で3 ^ 256の異なる状態を持つことができるため、その数のステップを実行した後に停止できます。ただし、命令ポインタやレジスタなどの暗黙のセルがあることに注意してください。すべての状態構成を保存し、すでに持っている状態構成を検出するとすぐに、無限ループが発生します。このアプローチは、実行時に間違いなくはるかに優れています。

于 2008-12-15T06:52:10.917 に答える
3

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

このプログラムを考えてみましょう:

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

このプログラムは、わずか 1000 個のセルで約 10^300 年かかるメモリ全体がいっぱいになるまで繰り返されません。

于 2013-11-04T17:03:24.720 に答える
2

私の記憶が正しければ、停止問題の証明は、自己参照を含むいくつかの極端なケースにのみ当てはまりました。ただし、無限ループ検出器を作成できない理由の実用的な例を示すのは簡単です。

フェルマーの最終定理を考えてみましょう。すべての数値 (この場合は 3 つの数値) を反復処理し、それが定理の反例かどうかを検出するプログラムを作成するのは簡単です。そうであれば停止し、そうでなければ続行します。

したがって、無限ループ検出器があれば、この定理と他の多くの定理を証明できるはずです (反例の検索に還元できる場合は、おそらく他のすべての定理です)。

一般に、数値を繰り返し処理し、特定の条件下でのみ停止するプログラムでは、その条件が満たされるかどうかを証明するために一般定理証明者が必要になります。そして、これが最も単純なループのケースです。

于 2015-03-10T10:25:07.470 に答える
1

頭から離れて(そして私は間違っているかもしれませんが)、プログラム自体を実際に実行せずに、プログラムに無限ループがあるかどうかを検出するのは少し難しいと思います。

プログラムの一部の条件付き実行はプログラムの実行状態に依存するため、実際にプログラムを実行せずにプログラムの特定の状態を知ることは困難です。

無限ループのプログラムを実行する必要がない場合は、「命令実行」カウンターを試して、有限数の命令のみを実行することができます。このように、プログラムに無限ループがある場合、インタプリタは無限ループでスタックしているプログラムを終了できます。

于 2008-12-15T05:57:45.300 に答える