半押し可能な線に到達していますか？

Question

2つのプログラムがあると仮定して $ p_1 $ 、 $ p_2 $ と2行番号 $ n_1 $ と $ n_2 $ 。 $ P_1 $ にregh $ n_1 $ $ P_2 $ reach $ n_2 $ ？停止からの削減により、これは明らかに決定的ではありませんが、私はそれが半決定的であると思います。

そうするために、 $ p_1 $ と $ p_2 $ を実行するインタプリタを構築します。ステップバイステップでステップバイステップで、各プログラムのステップを数えます。 $ p_1 $ に到達するとすぐに $ n_1 $ に到達すると、 $ N_2 $ 、それが少ない場合はtrueを返します。 $ p_2 $ の場合 $ n_2 $ に到達すると、falseを返します。プログラムが $ n_1 $ 、または $ n_2 $ に到達する場合は、何も起こりません（半定刻の後）。

Answer 1

あなたがあなたの決定問題を非常に慎重に言わせるならば、それは半決定的なものです。また、両方のプログラムが $ n $ sに到達しない場合のような方法でそれを言葉する必要があります。 $ \ infty <\ infty $ はあいまい/未定義であるので、私はあなたの決定問題において明示的に言及します。

それ以外は、はい、それは正しいです。どちらか $ p_1 $ 、または $ p_2 $ halts（ $ p_1、p_2 $ を停止していない場合は、拒否ケースにいないため、半押し可能性が停止することはできません。。