問題タブ [halting-problem]

マシンのチューリングと停止問題について質問があります。

Atm = {(M,w) ここで、M はチューリング マシンで、w は入力} であり、
HALTtm = {(M,w) ここで、M はチューリング マシンであり、入力 w で停止するとします。

HALTtm <=m Atm であることを証明したい

いくつかの方法を試しましたが、解決には程遠いと思います。誰でもいくつかの手がかりを与えることができますか??

別のプログラムをチェックするプログラムが存在できない理由について、論理的なアランチューリングの説明を見つけようとしています。

計算コースで学んだことを覚えていますが、今は解決策を見つけることができず、職場の誰かに説明する必要があります。

手伝ってくれてありがとう。

エミュレーターとステートメントに関する投票数の多い質問を読んでいたところです

特定のバイナリ内のすべてのコードを見つけることは、停止問題と同等であることが証明されています。

本当に私に突き出ました。

そんなことはあり得ませんよね？それは単なる大きな依存関係グラフではありませんか?

この声明へのさらなる洞察に本当に感謝します。

Android 3.0 エミュレーターで単純なステータス バー通知プログラムをテストしようとしています。
Eclipse からアプリケーションを実行しようとするとapk can't be installed、DDMS ログを確認すると JavaoutOfMemoryエラーが表示されるというメッセージが表示されることがあります。私のアプリケーションはかなり単純ですが、Java ファイルは 1 つだけです。

エミュレータを起動すると、ウィンドウが完全にシャットダウンすることがあります。これもテストしましWindows XPたUbuntu。Ubuntuエミュレーターが完全に起動し、ホームページを表示しようとしているときにも、OS がクラッシュしました。

他のバージョンの Android は、私の PC で正常に動作し2.2ます2.3。この問題は3.0(hocomb) バージョンでのみ見られます。これに対する解決策はありますか？

ありがとう
マニッシュ

決定論的プログラム（つまり、ステートマシン）が停止問題を解くことと同等の無限ループにあるかどうかを検出していますか？

私は解決策を思いついたが、なぜそれが機能しないのかわからない：

• プログラムを実行させます
• 無限ループにあると思われる場合は、定期的にメモリのスナップショットを撮ります
• 同じスナップショットを検出した場合、プログラムは無限ループに陥っています
• 同じスナップショットを2回取得しない限り、（1）無限ループではないか、（2）スナップショットをより迅速に取得する必要があります（おそらく、メモリアクセスごとに1回ですか？）

これはうまくいかないと思います...しかし、なぜですか？

プログラムが無限ループにあるかどうかを検出するのは完全に合理的な方法のようです（たとえば、メモリ自体ではなくハッシュを格納する場合、100％正確ではありませんが）...もしあれば、何が問題になっていますか？

NP、NP-hard、および NP-complete の定義に関するこの質問への回答で、Jason は次のように主張しています。

停止問題は古典的な NP 困難問題です。これは、プログラム P と入力 I が与えられた場合、停止するかという問題です。これは決定問題ですが、NP にはありません。あらゆる NP 完全問題がこの問題に還元できることは明らかです。

停止問題は直感的に NP のどの問題よりもはるかに「難しい」問題であることに同意しますが、停止問題が NP 困難であるという正式な数学的証明を正直に思いつくことはできません。特に、NP のすべての問題 (または少なくとも既知の NP 完全問題) のインスタンスから停止問題への多項式時間多対 1 マッピングを見つけることができないようです。

停止問題が NP 困難であるという簡単な証明はありますか?

ランダウの計算と停止性問題についての記事をいくつか読んだことがあります。明らかに、すべてのアルゴリズムが停止するかどうかを言うことはできません。たとえば、次のようになります。

しかし、そのようなプログラムの大きなものは何でしょうか？定義されていないと思います。同じ理由で、停止するかどうかを判断することはできません。あなたはそれを知りません。

だから...いくつかの可能なアルゴリズムがありますが、それが停止するかどうかはわかりません。しかし、あなたが言うことができないなら、そのアルゴリズムの大物は定義上未定義です。

ここで、私の要点として、ソフトウェアの大部分を計算します。なぜあなたはそれをするプログラムを書くことができないのですか？関数であるか、定義されていないためです。

また、プログラミング言語については何も言っていません。純粋に関数型プログラミング言語はどうですか？そこで計算できますか？

私はシプサーによる計算理論入門の停止問題の証明を検討していますが、私の主な関心事は以下の証明です。

TM M がいつループしているのかわからない場合 (TM がすべての文字列に対してチューリング認識可能である理由は、受け入れることも拒否することもできないためです)、ディサイダー H は、M がループしている可能性があるかどうかをどのように判断できますか? TM D が処理を行うときも、同じ問題が発生します。

while次の Javaの無限ループを見てください。その下のステートメントでコンパイル時エラーが発生します。

ただし、次の同じ無限whileループは正常に機能し、条件をブール変数に置き換えただけのエラーは発生しません。

2番目のケースでも、ブール変数bがtrueであるため、ループの後のステートメントは明らかに到達できませんが、コンパイラーはまったく文句を言いません。なんで？

編集:の次のバージョンは、明らかなように無限ループに陥りますが、ループ内whileの条件が常にであるにもかかわらず、その下のステートメントに対してコンパイラ エラーを発行しません。コンパイル時そのもの。iffalse

編集：ifと同じことwhile。

次のバージョンのwhileも無限ループに陥ります。

これは、ステートメントがブロック自体の中でステートメントの前に遭遇しfinallyたとしても、ブロックは常に実行されるためです。returntry

isAssociative2 つの引数を持つ別の関数を取り、その関数が連想的かどうかを判断する高階関数を構築することは可能ですか?

同様の質問ですが、交換性などの他のプロパティについても同様です。

これが不可能な場合、任意の言語で自動化する方法はありますか? Agda、Coq、または Prolog ソリューションがあれば、興味があります。

考えられるすべての引数の組み合わせをチェックし、決して終了しないブルート フォース ソリューションを思い描くことができます。しかし、「決して終了しない」は、このコンテキストでは望ましくないプロパティです。