Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates $f(p),f(f(p)),\ldots$ are bounded? Is this problem known to be algorithmically undecidable?
This was posted on Math stackexchange here .
This is almost an answer, but not quite:
It is known that determining if $(0,0)$ is a point in the attractor of an IFS, is undecidable, see this paper. This is very close to what you have.
There is also a very concrete problem, where one iterates a rational map, and it is unknown if starting with $x=2$ is unbounded. I think the map was $x \mapsto x-1/x$ but I might be mistaken.
There are also non-computable julia sets obtained from polynomial iteration, see here.
The following answer is relevant:
As there, the key question is which definition of decidability to use. The most natural notion comes from computable analysis. Here the point is ever only known up to some finite precision, and then the answer to "can you determine whether the iterates are bounded" is trivially negative. On the other hand, the similar question of computing the filled Julia set (i.e., set of points with bounded orbits) was settled in the positive by Braverman and Yampolsky, as pointed out by Robert. This means essentially that you can tell at least whether there is a point with bounded orbit nearby or not.
Of course, you are asking about maps with rational coefficients, and if you are interested in the behaviour of rational starting points, then you have a decision problem in the classical sense of computer science, whose decidability is likely an open question. However, in my view it is not a natural question from the point of view of dynamics, since the answer then seems to have much more to do with "what can we say about the existence and behaviour of rational/algebraic points in Julia sets?" rather than "can we decide whether a point has bounded orbit?" ...
