Atteint moins de lignes semi-décidables?

Question

en supposant que nous avons deux programmes $ p_1 $ et $ p_2 $ et deux numéros de ligne $ n_1 $ et $ n_2 $ . Est-ce que $ p_1 $ atteindre $ n_1 $ dans des étapes moins compatibles que $ p_2 $ atteint $ n_2 $ ? Par réduction de haltage, cela n'est clairement pas décidable, mais je pense qu'il est semi-décidable.

Pour ce faire, je construirais un interprète, qui exécute $ p_1 $ et $ p_2 $ Simultanément étape par étape et compter les étapes de chaque programme. Dès que $ p_1 $ atteint $ n_1 $ , je comparais le nombre d'étapes à $ n_2 $ et retourne vrai si c'est moins. Si $ P_2 $ atteint $ n_2 $ d'abord, je retourne faux. Au cas où aucun programme n'atteint $ n_1 $ ou $ n_2 $ , rien ne se passe (suivant la semi-dette).

Answer 1

Il est seulement semi-décidable si vous parlez de votre problème de décision très soigneusement.Et vous devez le verser de manière à ce que le cas où les deux programmes n'atteignent jamais leur $ n $ s est dans la catégorie de rejet.Depuis $ \ \ \ € $ est ambigu / indéfini, je mentionnerais explicitement cette affaire dans votre problème de décision.

Autre que cela, oui c'est correct.Votre machine s'arrête si $ p_1 $ ou $ p_2 $ s'arrête-Container "> $ n $ comme une autre condition d'arrêt) et fournit la bonne réponse dans un tel scénario.Si vous corrigez le problème ci-dessus, alors lorsque vous n'avez ni $ p_1, p_2 $ vous êtes dans le cas de rejet et que vous êtes donc autorisé à ne jamais arrêter également par semi-dette.