Quando una funzione PC 1: 1 estendibile ha un'estensione calcolabile 1: 1?
-
05-11-2019 - |
Domanda
Una funzione calcolabile parziale $ varphi_e $, definita su un set ce $ w_e $, è chiamata estendibile se esiste una funzione calcolabile $ f $ che estende $ varphi_e $, ie $ varphi_e (w_e) = f (w_e) $ .
La mia domanda è quali sono le condizioni per una funzione PC $ varphi_e $ per avere un'estensione iniettiva.
Finora ho trovato alcune condizioni necessarie:
Ovviamente, $ varphi_e $ stesso dovrebbe essere iniettivo.
$ | overline {w_e} | leq | overline { varphi_e (w_e)} | $. Perché $ f ( overline {w_e}) $ non dovrebbe avere alcuna intersezione con $ f (w_e) = varphi_e (w_e) $, quindi $ f ( overline {w_e}) sottoseteq overline { varphi_e (w_e)}}} $.
Questo esclude $ varphi_e (x) = x/2 $, definito sui numeri pari. E anche qualsiasi altra funzione parziale chiruria.
Non sono riuscito a trovare ancora una condizione sufficiente.
Nessuna soluzione corretta