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?

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 29, 2017 at 8:23
  • $\begingroup$ yeah,exactly I want this! $\endgroup$
    – haleh
    Jan 29, 2017 at 8:41
  • $\begingroup$ 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! $\endgroup$
    – Raphael
    Jan 29, 2017 at 16:51

1 Answer 1


Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function is clearly partially computable, but it has no computable extension, since you could use any such extension to solve the halting problem (why?).

Exercise for the reader: convert this construction to a Boolean function.

  • $\begingroup$ I can't understand this sentence :"since you could use any such extension to solve the halting problem"? $\endgroup$
    – haleh
    Jan 29, 2017 at 9:01
  • $\begingroup$ Yes, this requires an argument, which I leave to you. $\endgroup$ Jan 29, 2017 at 9:02
  • $\begingroup$ do you mean that since there is no total computable function for solving halting problem so there is no computable exentions for this function you said? $\endgroup$
    – haleh
    Jan 29, 2017 at 9:48
  • $\begingroup$ If there were a computable extension of the function I define then the halting problem would be decidable (!), which we know is not the case. There is a gap here that I indicated with (!), which you should fill. $\endgroup$ Jan 29, 2017 at 9:51
  • 3
    $\begingroup$ Unfortunately I am not willing to give a complete solution. You'll have to do the rest on your own. $\endgroup$ Jan 29, 2017 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.