# For any primitive recursive $f$ whose most values are equal to $0$, can there be found $N$ after which all of values of $f$ are equal to $0$?

$$\forall f: \mathbb{N} \to \mathbb{N}$$ primitive recursive function, whose most values are equal to $$0$$, in general can there be algorithmically found a number $$N$$ such that $$(\forall i > N)\,\,f(i)=0$$?

With "most of values" is meant that $$\sum_{i=0}^\infty {f(i)}$$ is finite. I think that such an $$N$$ cannot be found if we aren't considering some special case, because no matter for how many values of $$i$$ you check, you never know if $$f(i+1)=0$$ or not. This in the general case, but I'm not sure how this can be proven. It looks like the halting problem in some sense, but I'm not sure how to find a real connection between them.

This is not a problem from a textbook, but an intuition of mine, while trying to solve this: Show that infinite sum/product of primitive recursive functions can be non-recursive.. I decided to ask this separately to isolate it from the main question.

Am I right that such an $$N$$ cannot be found for the general case?

UPDATE Here is what I have just tried. Could you verify if its a valid solution?

Consider a Turing machine which should halt when run on input $$y$$. Consider the primitive recursive function $$\xi(n)$$ which is equivalent to the Godel number of $$n+1$$ $$1$$s. Consider the primitive recursive function $$H(t)$$ that returns the Godel number of the sequence of all symbols on the Turing machine on moment $$t$$. If the Turing machine has halted, then it keeps returning the same value. And finally consider the function $$h(t) = sg|H(t)-\xi(y)|$$. Then according to our supposition $$\exists N_1$$ such that $$\forall t > N_1 \implies h(t)=0$$, in other words, the output does not change anymore, which means that we have solved the Halting problem which is not possible.

The primitive recursiveness of $$\xi$$ can be easily shown. $$H(t)$$ is a Godel number which is generated from the function that is computed by the Turing machine, so it is primitive recursive.

• In general? I do not think why... Consider e.g. $f(n)=n$ that is obviously p.r. Commented Jan 17, 2022 at 9:53
• @MauroALLEGRANZA thanks, I've forgotten to mention, that most of $f$'s values are actually equal to 0, just some of them aren't. I have to edit the question. Commented Jan 17, 2022 at 9:55
• The function $f(n)=n$ for odd integers and $f(n)=0$ for the evens is easily p.r., since you can just check what was the last value and then either put 0 or $n$ as the next. Commented Jan 17, 2022 at 9:57
• @AsafKaragila thanks for the comment. yes, but there are infinite odd numbers. In my case just some of the values are non-zero, in other words there are finite many possibilities for $i$, for which $f(i)\neq 0$. Sorry for the initial ambiguity. Commented Jan 17, 2022 at 10:00
• Oh. I see. Try proving that by induction on the generating tree of $f$. This is trivial for the basic functions; then show that you can find this $N$ for composition and recursion constructors, given the upper bound for the functions you've input into them. Commented Jan 17, 2022 at 10:15

I can't quite follow your proposed argument (what is "$$sg$$"?), but indeed the conclusion is correct: there is no computable way of doing this.
In my opinion the cleanest way to see this is as follows. For each $$n$$ let $$g_n$$ be the function sending $$x$$ to $$0$$ unless the $$n$$th Turing machine on input $$n$$ halts in exactly $$x$$ steps, in which case $$g$$ outputs $$1$$. The $$g_n$$s are all primitive recursive, and in fact are uniformly primitive recursive - the binary function $$(n,x)\mapsto g_n(x)$$ is prmitive recursive.
Now the $$g_n$$s are each almost always $$0$$, regardless of whether $$n$$ is in the halting problem or not. However, if we know that $$g_n$$ stabilizes by stage $$k$$, we can check whether $$n$$ is in the halting problem by running the $$n$$th Turing machine on input $$n$$ for $$k$$ steps and seeing if it halts in that amount of time.
• Thank you for the answer! sg is the sign function, I am checking if the Turing machine has reached the final value $(y+1)$ and thus halted. And if it has halted on the moment $t=T$, then $H(t)$ will keep giving the Gödel number of $y+1$ ones for any $t \geq T$, and as every discussed function is primitive recursive then according to the supposition there exists an N beginning from which $h(t)=0$ which means we can determine whether the Turing machine halts or not and we can determine the exact moment, which is not possible. Commented Jan 18, 2022 at 7:12