I have to prove that the following function is not computable
$$ f(x) = if\ (x\ is \ even\ and\ f_{x/2}\ is \ total\ ) \ then\ 1\ else \ (x\ is \ even\ and\ f_{x/2}\ is \ partial\ )\ then\ 0\ else\ \bot$$
I was trying to count on the fact that I have no possibility to show that $f_{x/2}$ is total by means of a TM (I think). But I have no clue on how to prove this. I was also trying to reduce the function to a set on TM indexes and try to apply the Rice Theorem, but I couldn't do it. Is someone able to give me a clue on how to proceed?
EDIT: I thought that maybe the proof hides in the meaning of total and partial, even though I do not know how to formally prove this. My guess is that for a given index $x$, even if I could prove that $f_{x/2}$ is not defined for a least 1 value, I cannot be sure that for such value the TM cannot stop (i.e. accept the input) in the future, and therefore I cannot conclude it is partial. Moreover, in order to define the function as total I would need to try every possible input, and even after a long time where all the input I tried caused the machine to stop I cannot conclude that $f_{x/2}$ is total.
Best Answer
Your intuition is correct: if your function was computable, then you would be able to decide the TOTAL problem (deciding whether or not a Turing machine halts on all inputs) - which is undecidable.
We first fix an encoding of Turing Machines.
We use the following reduction: suppose that you have a machine $M$ that computes $f$. Now, we design a machine $N$, which accepts $x$ if the machine $M_x$ is total.
$N$ work as follows: on input $x$, it runs $M$ on the input $2x$, and gets the result $y = f(2x)$. Now, if $y = 1$, $N$ accepts; otherwise, it rejects.
It is easy to prove that $N$ accepts $x$ $\Leftrightarrow$ $M_x$ is total. Hence, $f$ is undecidable.
One point that I overlooked in the previous proof is the fact that TOTAL is undecidable. This can be done easily, by considering a machine which does the same thing regardless of its input (and so it hats on all inputs iff it halts on any input). With this idea in mind, the reduction to the Halting Problem is then easy to define.