3
$\begingroup$

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?

$\endgroup$
  • 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$ – Yuval Filmus Jan 29 '17 at 8:23
  • $\begingroup$ yeah,exactly I want this! $\endgroup$ – haleh Jan 29 '17 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 '17 at 16:51
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can't understand this sentence :"since you could use any such extension to solve the halting problem"? $\endgroup$ – haleh Jan 29 '17 at 9:01
  • $\begingroup$ Yes, this requires an argument, which I leave to you. $\endgroup$ – Yuval Filmus Jan 29 '17 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 '17 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$ – Yuval Filmus Jan 29 '17 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$ – Yuval Filmus Jan 29 '17 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.