Sta raggiungendo in meno linee semi-decidabili?

Question

Supponendo che disponiamo di due programmi $ P_1 $ e $ p_2 $ e due numeri di riga $ n_1 $ e $ n_2 $ . $ P_1 $ Raggiungi $ n_1 $ in minore passaggi computazionali rispetto a $ p_2 $ raggiunge $ n_2 $ ? Dalla riduzione da fermata, questo non è chiaramente decidabile, ma penso che sia semi decidabile.

Per fare ciò, costruirei un interprete, che esegue $ p_1 $ e $ p_2 $ contemporaneamente passo dopo passo e contare i passaggi per ciascun programma. Non appena $ p_1 $ raggiunge $ n_1 $ , confronto il numero di passaggi per $ N_2 $ e restituisci true se è inferiore. Se $ p_2 $ raggiunge $ n_2 $ Innanzitutto, restituisco false. Nel caso in cui nessun programma raggiunga $ N_1 $ o $ n_2 $ , non succede nulla (dopo semi-decidabilità).

Answer 1

È solo semi-decidabile se si parla il problema della tua decisione con molta attenzione.E devi scriverlo in modo tale che il caso in cui entrambi i programmi non raggiungano mai il loro $ N $ s è nella categoria di rifiuto.Dal momento che $ \ INFTY <\ INFTY $ è ambiguo / indefinito, menzionerò esplicitamente questo caso nel tuo problema di decisione.

Oltre a questo, sì è corretto.La tua macchina si ferma se né $ P_1 $ o $ p_2 $ halts (visualizzazione raggiungimento $ N $ come solo un'altra condizione di fermezza) e fornisce la risposta corretta in un tale scenario.Se si patografa il problema sopra riportato, quando né $ p_1, p_2 $ si ferma nella custodia di rifiuto e quindi è consentito mai fermarti anche per la semi-decidabilità.