# Partial recursive function with no total recursive extension

We define a partial recursive function $f:\{0,1\}^* \longrightarrow \{0,1\}^*$ to be semi-good if we can define a total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f$, such for all $x \in \{0,1\}^*$ either $f(x) = g(x)$ or $f(x)\uparrow$.

Now I want to prove that there exists a partial recursive function that is not semi-good.

I must make a partial recursive function that is not semi-good for example $f_1$ ,but my problem is that I must show that I can not define any total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f_1$.

I don't have any idea how can I show this. Can I use the fact that a specific language like $L$ is not recursive so its characteristic function $\mathcal{X}_L$ is not total recursive function? How can I make the partial function from this fact?

• Your question is unclear, but I guess your goal is to find a partial recursive function which has no total recursive extension. That is, we want a partial recursive $f$ such that no total recursive $g$ agrees with $f$ on its domain. Jan 29, 2017 at 8:23
• yeah,exactly I want this! Jan 29, 2017 at 8:41
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jan 29, 2017 at 16:51