0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is very clear and concise. Thank you for the clarification. $\endgroup$
    – King Powa
    Jan 27 at 13:02

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.