Are all eventually periodic functions on the natural numbers primitive recursive?

Question

A periodic function from $\mathbb{N}$ to $\mathbb{N}$ is a function $f$ such that there exists a nonzero natural number $n$ such that $f(m+n)=f(m)$, for all natural numbers $m$. An eventually periodic function is a function that is periodic from some natural number onwards. I want to know, are all eventually periodic functions on the natural numbers, recursive functions? Indeed, are they all primitive recursive?

Answer 1

Yes.

We say two functions $f, g : \mathbb{N} \to \mathbb{N}$ are equal almost everywhere when $\{x \in \mathbb{N} \mid f(x) \neq g(x)\}$ is finite.

We saw in my answer to your other question that if we have a primitive recursive function $f$ and a function $g$ such that $f = g$ almost everywhere, then $g$ is also primitive recursive. If $g$ is eventually periodic, then there is a periodic function $f$ such that $f = g$ almost everywhere. So it suffices to show that periodic functions are primitive recursive.

We begin by noting (without proof here) that the function

$$cases(a, b, c, d) = \begin{cases} c & a = b \\ d & otherwise \end{cases}$$

Is primitive recursive.

Suppose $f$ is periodic. Then there is some $n$ and some sequence $a_0, \ldots, a_{n - 1}$ such that for all $x$, $f(x) = a_{x \% n}$. Here, $x \% n$ is “reduction mod $n$” - it denotes the unique $i$ such that $0 \leq i < n$ and $x \equiv i \mod n$.

Now $\%$ is a primitive recursive function. We can see this by defining $0 \% n = 0$ and

$$S(x) \% n = cases(x \% n + 1, n, 0, x \% n + 1)$$

We can also define the function

$w(x) = \begin{cases} a_x & x < n \ 0 & otherwise \end{cases}$$

This function is primitive recursive, as it equals $0$ almost everywhere. So we can define $f(x) = w(x \% n)$, proving $f$ is primitive recursive.