¿Está llegando a menos líneas semi-decidibles?

Question

Suponiendo que tenemos dos programas $ P_1 $ y $ p_2 $ y dos números de línea $ N_1 $ y $ n_2 $ . Hace $ p_1 $ alcance $ n_1 $ en menos pasos de computación que $ p_2 $ alcanza $ n_2 $ ? Por reducción de detenerse, esto claramente no es decidible, pero creo que es semi decidible.

Para hacerlo, construiría un intérprete, que ejecuta $ p_1 $ y $ p_2 $ Simultáneamente, paso a paso y cuenta los pasos para cada programa. Tan pronto como $ P_1 $ llega a $ n_1 $ , comparo la cantidad de pasos para $ n_2 $ y devuelve verdadero si es menos. Si $ p_2 $ llega a $ n_2 $ primero, devuelvo falso. En caso de que ningún programa llegue a $ n_1 $ o $ n_2 $ , nada sucede (después de la semi-decidibilidad).

Answer 1

Es solo semi-decidible si observa su problema de decisión con mucho cuidado.Y tiene que decirlo de tal manera que el caso donde ambos programas nunca lleguen a su $ n $ s en la categoría de rechazo.Desde $ \ INFTY <\ INFTY $ es ambiguo / indefinido, mencionaría explícitamente este caso en su problema de decisión.

Aparte de eso, sí, es correcto.Su máquina se detiene si $ p_1 $ o $ p_2 $ detenciones (Visualización de alcance $ n $ como solo otra condición de detención) y proporciona la respuesta correcta en dicho escenario.Si parcha el problema anterior, entonces, cuando ni $ p_1, p_2 $ se detiene en el caso de rechazo y, por lo tanto, se le permite nunca detenerse también por la semi-decidibilidad.