# Algorithm to tell if a partial recursive function is 0 everywhere

Is there a (partial) recursive function that tells me, if a partial recursive function encoded by the number $c$ is the constant zero function ?

-
When writing questions, it's better practice to explain why you are interested in the question and what you have already tried. In this case, this question is a standard sort of result/exercise for a computability textbook. Once you learn the general method you will be able to answer these yourself. –  Carl Mummert May 8 '11 at 10:46
ok, I will do that next time –  temo May 8 '11 at 20:40

This wording in the question is ambiguous. It is unclear whether you want to show that the set of constant zero partial recursive functions is decidable or semi-decidable. I will show that the answer for the latter is negative and thus a fortiori so will be the answer for the former. Also it is unclear what you mean by partial recursive constant zero functions. There are two cases, (1) in which a function is considered constant zero only if it is total and constant zero and (2) in which a function is considered constant zero if for every input in its domain (which in general is a subset of the natural numbers) the output is zero. I will argue for both cases.

(1) Here I assume that constant zero means total and constant zero.

In the first case I will show that if the set of constant zero functions is semi-decidable then the set of total functions is semi-decidable. This wields as a result that you can recursively enumerate total recursive functions. This is impossible, because then if $f_n$ is an enumeration of total recursive functions let $g(n)=f_n(n)+1$. This $g$ is a total recursive function and different from every total recursive function, which is impossible.

So let's show that if the set of constant zero functions is semi-decidable then the set of total functions is semi-decidable. I'll argue using Turing machines: Assume that there is a machine $Zero$ that witnesses the semi-decidability of the set of constant zero functions. I will create a witness $Total$ for the semi-decidability of the set of total functions. The algorithm of $Total$ will be as follows:

For input a TM $M$, create a new machine $M^*$ that for every input $x$ runs $M$ with input $x$ and if $M$ halts $M^*$ gives $0$ as output. Then run $Zero$ with input $M^*$ and give as output the output of $Zero$.

$M$ is total if and only if $M^*$ is constant zero and thus $Total$ will witness the semi-decidability of the set of total functions.

(2) Here I assume that constant zero means constant zero in its domain that may be a subset of the natural numbers.

The second case requires a bit more. First observe that the complement of the set of constant zero partially recursive functions is semi-decidable. Use dovetailing (I hope this is the right term) to do this. That is given a partial recursive function "run" it with input $1$ for $1$ step, then run it with input $1$ and $2$ for $2$ steps, etc. If there is an element of the function's domain for which the function doesn't give $0$ as output the aforementioned process with find it.

The above shows that if the set of constant zero partial recursive functions is semi-decidable then it is decidable (since both the set and its complement are semi-decidable).

This leads to a contradiction: Assume there is a Turing machine that decides if a partial recursive function is constant zero or not and let's call it $ZERO$. I will use this $ZERO$ to create a Turing machine that solves the halting problem. Let $M$ be a Turing machine and $x$ an input for it. We create the following Turing machine $M^x$: For any input other than $x$ print as output $0$, for input $x$ run $M$ with input $x$ and if the machine halts then print as output $1$. Now using $ZERO$ with input $M^x$ we decide if $M$ halts with input $x$.

-

We can find a (total) recursive (indeed quite simple) function $f(c,n)$ with the following properties:

(i) If $c$ is the index of a Turing machine, then so is $f(c,n)$

(ii) The Turing machine with index $f(c,n)$, on input anything other than $n$, halts and gives result $0$.

(iii) On input $n$, the Turing machine with index $f(c,n)$ halts and gives result $0$ if the machine with index $c$ halts. Otherwise, the machine with index $f(c,n)$ does not halt.

Then the machine with index $c$ halts on input $n$ iff the machine with index $f(c,n)$ computes the identically $0$ function.

It is well-known that the Halting Problem for Turing machines is not Turing machine solvable. But if there were an algorithm (Turing machine) for determining whether a machine output is identically $0$, then by applying the algorithm to the machine $f(c,n)$ we would have an algorithmic solution to the Halting Problem.

-