3

FindBugs特定のプログラム/コードベースで無限に終わることのないループを検出できるというツールがあります。

これFindBugsは、コードを分析することで、プログラムが終了するかどうかを検出できることを意味します。停止問題は、次のことを定義する問題です。

任意のコンピュータ プログラムの説明を与えられて、そのプログラムが実行を終了するか、永久に実行し続けるかを決定します。

これは、停止問題が解決されたこと、または停止問題のサブセットが解決されたことを意味するのでしょうか?

4

3 に答える 3

0

分析プログラムと同じ制限で同じプラットフォームのプログラムを分析するプログラムを作成する場合、そのようなアナライザーは存在しません。これは停止問題として知られています。

そうは言っても、停止の問題は、分析プログラムが持つことができるよりもはるかに少ないメモリ消費とコード長を持つプログラムで解決できます。例えば。私は停止することができますか？すべての 2 バイトBrainFuckプログラムの手順は次のとおりです。

;; takes a valid 2 byte BF-program
;; and returns if it will halt
(define (halt? x)
  (cond ((equal? x "[]") #f)
        (else #t)))

より大きな例は、インタープリターを作成し、メモリの状態と pc-location をハッシュすることです。以前の状態が見つかった場合、それは無限ループです。非常に優れたデータ モデルであっても、インタープリターが使用するメモリは、解釈するものよりもかなり大きくなければなりません。

私は実行することで一定の折り畳みプログラムを考えていますが、停止の問題が問題になります。私の考えは、AST の特定のブランチが見られた回数を持ち、カットオフ制限が非常に大きいデータ構造を持つことです。したがって、インタープリターがカットオフよりも多くの分岐にあった場合、それは計算ではなくコンパイルされたプログラムになります。必要なメモリが大幅に少なくなり、プログラムの一部またはすべての部分が確実に戻る (停止する) ことが確立されます。

次のコードを想像してください。

(define (make-list n f)
   (if (zero? n)
       '()
       (cons (f) (make-list (- n 1) f))))

(define (a)
  (b))

(define (b)
  (c))

(define (c)
  (b))

(display (make-list 4 read))
(display (make-list 4 a))

入力がどの順序で取得されるかわからないため、実際にはかなり悪いコードです。コンパイラは最適なものを選択し、次のようになる可能性があります。

(display-const "(")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const ")")
(display (cons (b) (cons (b) (cons (b) (cons (b) '())))) ; gave up on (b)
于 2013-11-19T11:40:35.367 に答える