問題タブ [halting-problem]

(p 入力) が停止するように入力が存在するかどうかを判断できるプログラム (may-halt? p) はありますか?

簡単な対角化を試みましたが、(may-halt? diag-may-halt) が true でなければならないということしかわかりません。プログラムが存在するかどうかを証明するのには役立ちません。

そのようなプログラムは存在しますか？

停止問題は、入力とプログラムが与えられた場合、プログラムが停止するかどうかを判断できるアルゴリズムがないことを示しています。これにより、この問題は決定不能になります。停止の問題に関する私の誤解は、プログラムに無限ループがあるかどうかをチェックできる別のプログラムを作成できないかということです。ループが停止しないケースをチェックして、それに基づいてプログラムが停止するかどうかを判断できる可能性があることを意味します。この問題に対する私の理解のどこが間違っているのか教えてください。

与えられた:

• から までの文字のみを含むchar 文字列の S長さl'a''z'
• ordered置換ルールのセットR( の形式X->Y)。ここでx、yは からの 1 文字です'a' to 'z'(たとえば、'a' -> ' e'有効なルールになる可能性がありますが、'ce'->'abc'決して有効なルールにはなりません)。

のルールrが にR適用されると、ルールがの置換を引き起こす場合、が呼び出されると、ルールのと等しいSすべての文字が のの文字に置き換えられます。Sleft siderright siderrSrtriggered rule

フローチャート (アルゴリズム) : (1) のルールを( のルールの順序に従って)に
交互に適用します。 (2) While : 繰り返し (1) (3) 終了allRRS
(there exists any 'triggered rule' DURING (1) )

質問は次のとおりです。特定の文字列 S とセット R を使用して、アルゴリズムが終了するかどうかを判断する方法はありますか (永久に実行されます)。

例 1 : (手動で実行)

S = 'abcdef' R = { 'a'->'b' , 'b' -> 'c' }
(順序は、各ルールの左から右への出現順序を意味します)

S と R でアルゴリズムを実行した後:
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): (1.1) の間に 2 つの置換があるため、(1) を繰り返します
。 (1.2): 'cccdef'
(2.2): 途中で置換がないため、(3) に進みます。 (1.2)
(3) :
アルゴリズムを終了 => アルゴリズムは指定された S と R で終了します
。

S = 'abcdef'R = { 'a'->'b' , 'b' -> 'a' }
(順序は、各ルールの左から右への出現順序を意味します)

S と R でアルゴリズムを実行した後:
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): (1.1) の間に 2 つの置換があるため、(1) を繰り返します
(1.2): 'abcdef--> 'bbcdef' --> 'abcdef'
(2.2): あるため、(1) を繰り返します。 (1.2) (1.3) の間に 2 つの置換
があります: ...... それは (1.1) 永遠に同じです....
ステップ (3) (終了) には到達しません。
=> アルゴリズムは、指定された S と R で終了しません。

• 私はこれに取り組みましたが、「アルゴリズムが停止した場合」という質問に対する効率的なアルゴリズムは見つかりませんでした。

• 最初に頭に浮かんだアイデアは、入っている "find cycle"文字のことでしtriggered rulesたが、ルールの数が多すぎて、このアイデアが理想的であるとは言えませんでした。

• 2 つ目は、繰り返しの時間を提案すること"threshold"です。しきい値を超えた場合、アルゴリズムは終了しないと結論付けます。

• ("threshold"十分な大きさである限り) ランダムに選択できますが、このアプローチはあまり魅力的ではありません。

• 常に正しい答えが得られるようにするupper boundための ものがあればと考えています。"threshold"そして、26 が 'a' から 'z' までの文字の数である場所を思いつきましたが threshold = 26、それが正しいかどうかを証明することはできません。（一定のステップ数で負のサイクルを決定するベルマンフォードアルゴリズムのようなものだといいのですが..）

• 君はどうでしょう？答えを見つけるのを手伝ってください（これは宿題ではありません）

  読んでくれてありがとう。

私の理解では、十分に単純な機能について、

可能な入力に対して停止するかどうかを知ることができます。

上記の関数が forfalseで終了し、 for true. It's only impossible to solve the halting problem for an arbitrary functionf , as of course you can evaluatehaltingFinder(haltingFinder)` で終了しないことは簡単にわかり、本質的にパラドックスが生じます。

私の理解は正しいですか？

私はアセンブリで独自の BF インタープリターを作成しましたが、現在はアセンブリ コードにコンパイルする BF コンパイラを Java で作成しています。

メモリ セルの配列が範囲外かどうかを検出するちょっとした便利な機能を実装したかったのです。配列の従来の制限は、インデックスを in[0, 30000)にすることでした。それ以外の場合[0, inf)も一般的に使用されます。もう 1 つのオプションは、メモリをラップアラウンドすることです。したがって、最初のケースでは、インデックス 30000 へのアクセスはインデックス 0 へのアクセスを意味する可能性があります。

私のコンパイラでは、この検出は従来のコンパイラのセマンティック分析フェーズで行われるため、構文分析フェーズから AST (抽象構文ツリー) を既に取得しています。

しばらくの間、このための構造を考え出そうとした後、私はDetecting infinite loop inbrainfuck programを見つけました.BFのウィキペディアページと一緒に、メモリ配列としてのBFプログラムが[0, inf)チューリングマシンに似ていることがわかりました.

だから私の質問は、[0, max)と[0, inf)ケースの両方で、メモリポインターがゼロを下回ったかどうか、前者の場合は最大を下回ったかどうかを検出することは可能ですか? 明らかに、チェック中に無限ループに陥ることはありません。また、最大実行時間の設定も避けたいと思います。

おまけの質問: ループ構造[...]がループする回数を検出することは可能ですか?

私は最近、停止問題の矛盾証明に出くわしました。証明では、チューリング マシンにプログラムのコピーと入力のコピーを供給して、そのプログラムが入力で停止するかどうかを判断する必要があります。矛盾の中で、なぜそれはプログラムとしてのプログラムであり、入力でなければならないのですか? 紛らわしく聞こえる場合は申し訳ありません。マシンにプログラムとランダムな入力を与えるだけで、同じ結論に達することができます。

誰でも理由を教えてもらえますか? 私が思いつかなかった特定の理由はありますか？

これは、物を数える Meteor アプリケーションの (関連データを含む) コードの本質です。カウントをリンクして、一方が他方を増加できるようにすることができます。

そのため、Meteor.call('projects.increment',1)が呼び出されると、各カウントが他のカウントにリンクされるため、このコードはクラッシュします。このようなセットアップの検出は、非常に複雑なカウントの配置が存在する可能性があり、リンクが減少したり、ゼロに設定されたり、N カウントごとに動作したりする可能性があるため、かなり困難になる可能性があります。＆c。ただし、この質問をする目的では、それは問題ではありません。

私が考えた 1 つの可能性はcounts.check-links、任意の数のループ (たとえば 5 回) の後に実行を停止するカウンターを追加することです。おそらく、このカウンターの値の改ざんを防ぐには、データベースに格納し、流星法。check-links一連の呼び出しの終了時にリセットする必要があります。

これが最善のアイデアなのか、それともどのように実装するのが良いのかはわかりません。誰か提案があれば知りたいです。