Erreicht in weniger Linien halb entschlossen?

Question

vorausgesetzt, wir haben zwei Programme $ P_1 $ und $ P_2 $ und zwei Zeilennummern $ n_1 $ und $ n_2 $ . Ist $ P_1 $ REACH $ n_1 $ in weniger Rechenschritten als $ p_2 $ reicht $ n_2 $ ? Durch die Reduktion durch den Anhalten ist dies eindeutig nicht enttäuschbar, aber ich denke, es ist halb entschlossen.

Um dies zu tun, würde ich einen Dolmetscher erstellen, der $ P_1 $ und $ P_2 $ ausführt> Gleichzeitig Schritt für Schritt und zählen Sie die Schritte für jedes Programm. Sobald der $ P_1 $ erreicht wird, erreicht ich $ n_1 $ , vergleiche ich die Anzahl der Schritte in $ n_2 $ und rufen Sie true zurück, wenn es weniger ist. Wenn $ p_2 $ erreicht, erreicht $ n_2 $ Zunächst wird ich false zurückgeben. Falls kein Programm erreicht, erreicht $ n_1 $ oder $ n_2 $ , passiert nichts (nach der semi-decidability).

Answer 1

Es ist nur halb entschlossen, wenn Sie Ihr Entscheidungsproblem sehr sorgfältig wenden.Und Sie müssen es so plündern, dass der Fall, in dem beide Programme niemals ihren $ n $ s erreichen, in der Kategorie Ablehnung ist.Da $ \ Infty <\ Infty $ mehrdeutig / nicht definiert ist, würde ich diesen Fall in Ihrem Entscheidungsproblem explizit erwähnen.

anders als das, ja es ist richtig.Ihr Gerät hält an, wenn entweder $ P_1 $ oder $ P_2 $ haltet (Anzeigen des Erreichens $ n $ als nur ein weiterer Anhaltungszustand) und bietet die richtige Antwort in einem solchen Szenario.Wenn Sie die obige Ausgabe patchen, dann sind Sie, wenn Sie weder $ P_1, P_2 $ hehre, in dem Ablehnung des Falls und somit dürfen Sie niemals auch nach der Halbschlägerbarkeit bleiben.