# Proving a certain primitive recursive function exists

Assume $$f\colon ω × ω → ω$$ is a computable function. How can we prove that there is a primitive recursive function $$g\colon ω × ω → ω$$ where the following holds:

$$∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$$

So for every $$n$$, there is an $$s$$ such that $$f(n, s) = 1$$ if and only if there is a $$k$$ such that $$g(n, k) = 1$$.

Been working on this problem for a while now, if anyone could please help?

## 1 Answer

The function $$g$$ interprets $$k$$ as two inputs $$k_1,k_2$$. It runs $$f(n,k_1)$$ for $$k_2$$ steps, returns whatever $$f$$ does if $$f$$ halts, and returns $$0$$ otherwise.