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:

  1. Ovviamente, $ varphi_e $ stesso dovrebbe essere iniettivo.

  2. $ | 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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top