問題タブ [halting-problem]

Total問題が再帰的でない (決定可能)ことを証明する助けが必要です。

Halting問題の対角化証明は知っていますが、 Total問題についても同じ種類の証明が必要です。参照用にHalting Problem Proof を投稿しています。

問題の証明の停止

停止問題を決定できると仮定します。次に、次のようないくつかの合計関数 Halt が存在します。

ここでは、すべてのプログラムに番号を付けており、[x] はこの順序で x 番目のプログラムを指します。入力を one-one 関数を介して 2 つの数値のペアを表す単一の数値として扱うことにより、Halt を ℵ から ℵ へのマッピングと見なすことができます。

Halt が存在する場合、Disgree も存在します。

Disagree は ℵ から ℵ へのプログラムであるため、Disagree は Halt によって推論できます。d を Disagree = Φd とします。

Disagree(d) が定義されている ⇔ Halt(d,d) = 0 ⇔ Φd (d) が定義されていない ⇔ Disagree(d) が定義されていない

しかし、これは、不一致がそれ自体の存在に矛盾することを意味します。元の仮定を除いて、私たちが取ったすべてのステップは建設的だったので、元の仮定が間違っていたと推測しなければなりません. したがって、停止問題は解決できません。

Pythonファイルのコードが無限ループを通過するかどうかを識別する関数を作成しようとしています。これは私がこれまでに持っているものです:

私がやろうとしているのは、ファイルを実行することです。おそらく、実行された行数を数えて、それを前のカウンターの数値と比較してみてください。たとえば、counter > lines_exected の場合に True を返すと、コードに無限ループが発生します。これは機能しますか？それとも、何か他のことを試す必要がありますか?

チューリングは、停止問題がチューリング マシン上で決定不能であることを証明しました。ただし、実際のコンピューターは実際にはチューリング完全ではありません。無限のメモリがあれば、完全になるでしょう。

コンピュータのメモリ量は有限であり、完全なターニング完全ではないという事実を考えると、停止問題は決定可能になりますか? 私の直感では、そうですが、この制限付きの停止問題を解決するプログラムの時間と空間の複雑さは、対象となるコンピューターのメモリのサイズに指数関数的に比例する可能性があります。

Python (または疑似コード) で、特定の関数 [f1,...,fn] のリストと特定の入力のリスト [x1,...,xn] は、fi(xj) (関数と入力のすべてのペアを意味する) を 1 回だけ出力します。

もちろん、これを実装する単純な提案は次のようになります。

しかし問題は、一部の関数が一部の入力で永遠にループする可能性があることです。

ステッパーを使用することが許可されています (これには、呼び出されるたびに関数の後続の計算ステップを 1 つ作成する step() メソッドがあります)

その方法についてのアイデアまたはアルゴリズムが必要です。

このような質問には答えるべきだと思っていましたが、Google で解決策が見つからないようです。

とにかく。関数が無限再帰であるかどうかを確認する組み込み関数を誰かに提供またはリンクしてもらえますか?

このように見える関数は素晴らしいでしょう

Pythonでそのようなものはありますか？

停止問題を実現する Haskel 関数が存在するとします。

x が定義されている場合は True に評価され、それ以外の場合は False に評価されます。

Haskell でこの関数を別の関数で呼び出していると仮定しましょう。

この状況で何が起こるのか、そして fHalt が単調な場合はどうなるのだろうかと思っています。私には2つの可能な答えが生じます：

1. Haskell は、事前定義された演算子 (つまり、(+) に対しても) に対して厳密な評価を使用します。fHalt が現在 BOT で評価されている場合、私の推測では、BOT+1 を最初に評価する必要があり (BOT になります)、全体的な評価は終了せず、BOT になります。

2. 何らかの形で Haskell が内部 (x+1) が終了しないと判断した場合 (これは停止問題のために不可能です)、結果は False になり、fHalt は単調性に違反します。

私の質問は、Haskell で定義された実現不可能な停止関数を既に暗示していたので、この時点でイライラしています。答え1.が正しいと思いますが。

私は CS の理論クラスを受講しており、停止の問題について話し合ったところです。私の理解では、問題が解決できない理由は、プログラムが停止しないかどうかを教えてくれるプログラム Halt があり、別のプログラムを書くと、

私にとって、問題の核心は、if 条件がプログラムを無限にループさせることであり、これが Halt の失敗条件であるということです。

これは私が確信していない部分です：

別のプログラムが特定の入力に対して数値 4 を返すかどうかをチェックするプログラムがあるとします。このプログラムを FourCheck としましょう。次に、次のような別のプログラム ProofFour を作成できます。

この場合、ProofFour(ProofFour,input) を呼び出すことができます。FourCheck() が true を返す場合、ProofFour は 5 を返すため、FourCheck() の出力は正しくありません。FourCheck が false を返す場合、ProofFour は 4 を返し、FourCheck() の出力が正しくなくなります。

したがって、チェッカー プログラムの出力を本質的に反転させる Proof() や ProofFour() に似たプログラムをいつでも構築できるため、他のプログラムをチェックするプログラムは本質的にないと仮定するのは正しいでしょうか。

問題があります。

ユーザーが入力した IP で Game-Server に接続したい。サーバーが正しいサーバーであるか、サーバーが存在しない限り、すべて問題ありません。接続または例外があります。

問題は、ゲームを実行していない既存のサーバーに IP を入力した場合です。この場合、プログラムは接続イベントにとどまり、何にも反応しません。うまくいきませんでしたが、タイマースレッドを設定することを考えました。プログラムはユーザーによる入力に反応せず、閉じることのみを許可します。

クライアントをスレッドとして、タイマーをスレッドとして実装しました。時間切れの場合、Timer-Thread は Client-Thread を停止する必要があります。

マイタイマー:

そして私のクライアント：

それが問題であれば、私はJmonkeyでJAVAを使用しています。