1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.