By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically:
Let $f(x)$ be any computable function.
Let $F(x, a \, | \, y_1, \dots, y_n)$ be a diophantine polynomial such that $f(x) = a \iff \exists (y_1, \dots, y_n) F(x, a \, | \, y_1, \dots, y_n) = 0$.
Let $g_f(x, k)$ be the computable function that is equal to $\underbrace{f(f( \dots f(x) \dots ))}_{k \, times}$.
Find a diophantine polynomial $G(x, k, a \, | \, y_1, \dots, y_m)$ such that $g(x, k) = a \iff \exists (y_1, \dots, y_m) G(x, k, a \, | \, y_1, \dots, y_m) = 0$.
I'm very new to the idea of diophantine programming, so I would appreciate an answer to this problem and/or a good reference that can help me get the tools to solve it myself.
Thank you!
The Matiyasevich part of the theorem is that polynomial Diophantine equations are as expressive as exponential Diophantine equations. Goedel showed how to encode strings of arbitrary length using exponential Diophantine equations, which was the key to his proof and can be used to express "sequence of length $k$ where $a_{i+1} = f(a_i)$". Then every $a=b^c$ can be replaced by a Matiyasevich system of polynomials.