問題タブ [halting-problem]

クラスでは、停止問題、チューリング マシン、縮約などについて学びました。多くのクラスメートは、これらはすべて抽象的で役に立たない概念であり、それらを知っていても意味がないと言っています (つまり、コースが終わったら忘れることができます)。何も失うことはありません）。

理論はなぜ役に立つのか? 日常のコーディングで使用したことがありますか?

現場で停止の問題に個人的に遭遇したのはいつですか? これは、同僚や上司が計算の根本的な限界に違反する解決策を提案したとき、または解決しようとしていた問題が実際には解決できないことに気付いたときです。

私が最近それを思いついたのは、型チェッカーを研究していたときでした。私たちのクラスは、完全な型チェッカー (型エラーなしで実行されるすべてのプログラムを受け入れ、型エラーで実行されるすべてのプログラムを拒否するもの) を書くことは不可能であることに気付きました。 . もう1つは、同じクラスで、型チェック段階でゼロによる除算が発生するかどうかを判断することは不可能であることに気付いたときです。実行時に数値がゼロであるかどうかをチェックすることも停止問題のバージョン。

使用されるほぼすべてのプログラミング言語はチューリング完全であり、これにより言語は計算可能なアルゴリズムを表すことができますが、独自の問題も伴います。私が書いているアルゴリズムはすべて停止することを意図しているため、停止することを保証する言語でそれらを表現できるようにしたいと考えています。

文字列と有限状態マシンの照合に使用される正規表現は、 lexingのときに使用されますが、チューリングが完全ではない、より一般的で幅広い言語があるかどうか疑問に思っています。

編集：明確にする必要があります。「汎用」により、必ずしもすべての停止アルゴリズムをその言語で記述できるようにしたいわけではありません（そのような言語が存在するとは思いません）が、共通のスレッドがあると思われますすべてのアルゴリズムが停止することが保証されている言語を生成するために一般化できる停止証明。

この問題に取り組む別の方法もあります - 理論的に無限のメモリの必要性を排除します。マシンが許可されるメモリの量を制限すると、マシンが存在する状態の数は有限であり、数えることができるため、アルゴリズムが停止するかどうかを判断できます (マシンが以前の状態に移行することを許可しないことによって)。 ）。

私は、MATLAB スクリプト言語で単純な頭のおかしいインタープリターを作成しました。(遺伝的アルゴリズム プロジェクトの一部として) 実行するランダムな bf プログラムが与えられます。私が直面している問題は、プログラムにかなりの数のケースで無限ループがあることが判明したため、GA がその時点で動かなくなることです。
したがって、無限ループを検出し、そのコードを bf で実行しないようにするメカニズムが必要です。
明らかな（些細な）ケースの1つは、私が持っている場合です

私はこれを検出し、そのプログラムの実行を拒否できます。
自明ではないケースについては、基本的な考え方は、ループの 1 回の反復で現在のセルがどのように変化するかを判断することであることがわかりました。変化が負の場合、最終的に 0 に到達するため、有限ループです。それ以外の場合、変化が負でない場合、それは無限ループです。
これを実装するのは、単一のループの場合は簡単ですが、ネストされたループでは非常に複雑になります。例えば ​​(以下の (1) はセル 1 の内容などを指します )

したがって、コードは何度も実行されます。ただし、セル 1 で行われた + と - の数の単純なチェックでは、- の数が多いと判断されるため、無限ループは検出されません。
bf で任意の数のループが任意にネストされている場合、無限ループを検出するための優れたアルゴリズムを考えられる人はいますか?

編集:停止の問題が一般的に解決できないことは知っていますが、特別なケースの例外が存在しないかどうかはわかりませんでした。同様に、Matlab は bf プログラムの停止を判断できるスーパー チューリング マシンとして機能するかもしれません。私はひどく間違っているかもしれませんが、もしそうなら、その方法と理由を正確に知りたいです.

2 番目の編集: 無限ループ検出器であると主張するものを書きました。おそらくいくつかのエッジケースを見逃しています（または、おそらくチューリング氏のクラッチから逃れる可能性は低いです）が、今のところ私にとってはうまくいくようです。疑似コード形式では、次のようになります。

停止問題はチューリング完全言語では解決できず、正規表現のように常に停止する一部の非TC言語では簡単に解決できます。

停止する機能と停止しない機能の両方を備えているが、停止するかどうかを判断できるアルゴリズムを認めている言語があるかどうか疑問に思いました。

Lua 用のオートコンプリート アルゴリズムを作成する方法を見つけようとしていますが、多くのスクリプト言語と同様に静的型システムが欠けているため、バックグラウンド コンパイルが必要だと思いますが、バックグラウンド コンパイル中に停止問題が発生しやすいので、誰かが以前にこの種のことを解決したことがあるかどうか疑問に思っていました.コンパイルと停止を解決するための標準的な戦略は何ですか?

この質問に触発された

無限のメモリと無制限のCPUパワーを備えた魔法のチューリングマシンがあるとします。

これがどのように可能であるかについて想像力を働かせてください。たとえば、ある種の超空間連続体を使用して、必要なだけ自動的に並列化し、時間計算量や数に関係なく、計算可能な質問に対する答えを計算できるようにします。 1秒で実際の「論理ステップ」の。

ただし、計算可能な質問には1秒でしか答えられません...したがって、私は「不可能な」マシンを想定していません（少なくとも私はそうは思いません）...たとえば、このマシンはまだ答えることができません停止問題を解決します。

そのようなマシンのプログラミング言語はどのようになりますか？私が知っているすべてのプログラミング言語は、現在「アルゴリズムの複雑さ」にいくらかの譲歩をしなければなりません...しかし、その制約を取り除いて、私たちが気にするのはプログラミング言語の「表現力」だけだと思います。つまり、「計算可能な質問」を簡潔に表現する能力...

とにかく、うまくいけば興味深い議論のために、コミュニティウィキとしてそれを開いてください...

プログラミングに関連する停止の問題について人々が尋ねるときはいつでも、人々は「ループを 1 つ追加するだけで、プログラムが停止することになり、タスクを自動化できなくなります」と答えます。

理にかなっています。プログラムに無限ループがある場合、プログラムの実行中に、プログラムがまだ入力を処理しているのか、それとも無限ループしているだけなのかを知る方法はありません。

しかし、これには直観に反するものもあります。ソース コードを入力として受け取る停止型問題解決プログラムを作成していたとしたらどうでしょう。rascher@localhost$ ./haltingSolver source.c

私のコード (source.c) が次のようになっている場合:

私のプログラムがこれを見るのはかなり簡単なようです。「ループを見て、条件を見てください。条件がリテラルのみに基づいており、変数がない場合、ループの結果は常にわかります。変数がある場合 (たとえば、while (x < 10))、これらの変数は常に変更されます。そうでない場合は、ループの結果が常にわかります。」

確かに、これらのチェックは簡単ではありません (ポインター演算の計算など) が、不可能ではないようです。例えば：

検出できました。とともに - 自明ではありませんが:

では、ユーザー入力についてはどうでしょうか。それがキッカーであり、プログラムを予測不能にするものです。

これで私のプログラムは、「ユーザーが 10 以上を入力すると、プログラムは停止します。それ以外のすべての入力では、再びループします」と言うことができます。

つまり、何百もの入力があっても、プログラムが停止する条件をリストできるはずです。実際、私がプログラムを書くときは、必ず誰かがプログラムを終了できるようにしています! 結果として得られる条件のリストを簡単に作成できると言っているわけではありませんが、不可能ではないように思えます。ユーザーからの入力を取得し、それらを使用してポインターインデックスを計算することもできますが、それはプログラムが確実に終了するように条件の数を追加するだけであり、それらを列挙することを不可能にするわけではありません.

では、停止の問題とは正確には何ですか？無限ループを検出する問題を書くことができないという考えについて、私が理解していないことは何ですか? または、なぜ「ループ」がそのようなよく引用される例なのですか?

アップデート

では、質問を少し変えさせてください。コンピューターに適用される停止問題とは何ですか? そして、いくつかのコメントに返信します。

多くの人が、プログラムは「任意の入力」を処理できなければならないと言っています。しかし、コンピューターでは、任意の入力はありません。1 バイトのデータのみを入力すると、可能な入力は 2^8 しかありません。したがって、例として：

突然、すべての可能性を説明しました。cビットパターンが 0x71 の場合、1 つのことを行います。他のすべてのパターンでは、別のことを行います。リソースは有限であるため、任意の文字列入力を受け入れるプログラムでさえ、実際には「任意」ではありません。つまり、「任意」の理論が適用されますが、実際には正確に 1 対 1 ではありません。

人々が引用した他の例は次のとおりです。

n が 32 ビットの整数である場合は、これが停止するかどうかを視覚的に判断できます。

この編集は何も求めていないと思いますが、私が見た中で最も説得力のある例は次のとおりです。

プログラムの停止を判断するための魔法のプログラム/メソッドがあるとします。

さて、次のような小さなコードを書いたとしましょう...

したがって、この例では、魔法の停止方法とは正反対のことを行うプログラムを書くことができます。特定のプログラムが停止すると何らかの形で判断した場合、無限ループに飛び込みます。それ以外の場合、プログラムが無限ループにあると判断した場合は、プログラムを終了します。

繰り返しになりますが、意図的に無限ループを含むプログラムを作成すると... 「停止問題を解決する」というのはちょっと意味がありませんね。

一部の入力文字列に対して、一致するものを永久に検索する正規表現はありますか？

停止性問題には明確な解決策がないことが知られています。a）プログラムが実際に停止し、b）任意の入力を処理するというものですが、問題に対する十分な解決策があるかどうか疑問に思いました。特定の種類のプログラムフローを完全に処理できるもの、問題を正しく解決できない場合を特定できるもの、または正しい割合が高いものなど。

もしそうなら、彼らはどれほど優れていますか、そして彼らはどのようなアイデア/制限に依存していますか？