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

3 Answers

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$.

-

The answer is no by Rice's theorem.

The only property of computable languages/graphs of functions that can be decided computably are the trivial ones (i.e. the property that is satisfied by all, and one which is satisfied by none).

Being the constant function 0 is not a trivial property so it cannot be decided.

-

1
This is the theorem to look up; it is one of the more general undecidability theorems. Unfortunately, the conclusion of Rice's theorem is only that the problem is undecidable; it doesn't give any more precise information about the amount of undecidability. – Carl Mummert May 8 '11 at 10:50

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 59, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9128789305686951, "perplexity_flag": "head"}