🚀 go-pugleaf

This answer is yes (it is decidable) for a large class of 
algebraic endomorphisms of varieties where everything is defined over the
rationals.  For example, let f(x) = x^2 + c where c is rational.
Define the height of a rational number p/q (where (p,q)=1) as
h(p/q) = log max(1,|p|,|q|).  Then it is easy to see that 
for x rational, h(f(x)) = 2 h(x) + O(1) (the implied constant depends on c).
This gives an a prior bound on the height of all rational points with
finite forward orbits, thus a bound on the number of such points,
and also on the size of their forward orbits.   

References:
  J. Silverman, Rational points on K3 surfaces:  A new canonical height.
Invent. math. 105 (1991), 347-373.

  G. Call and J. Silverman, Canonical heights on varieties with morphisms.
Preprint 1992.

In <Bu9B1J.H8E@ens-lyon.fr> koiran@ens.ens-lyon.fr (Pascal Koiran) writes:

>Hello,

>Can someone provide a solution to the following problem, or give references
>to related work in the litterature ?

>Let f:[0,1]-->[0,1] be a continuous piecewise-linear function (with a finite
>number of laps). The endpoints of the laps have rational coordinates.
>Given such an f and a rational x \in [0,1], is it decidable whether a fixed
>point is reached in finite time when f is iterated on x ?
>In other words, is it decidable whether there exists t, f^t(x)=f^{t+1}(x) ?

The collection of all such x is clearly recursively enumerable.  Also,
given a (one-tape, one-sided infinite) Turing machine T, it is clear that
one can define a recursive piecewise linear function f with a countable
number of segments, and a G of all possible tape states into [0,1] such
that f(G(state)) = G(T-successor of state), so that f reaches a
fixed point started at G(state) iff T halts starting at "state" (if you
make the convention that any production rule which leaves the entire state
fixed is replaced by a cycle back-and-forth, so that fixed points of T
correspond to halted states.)

If all slopes of segments are 1/n for (positive or negative) integer n,
then for any x, and t, x = A f^t(x) + Q, where A is an integer, and Q has
a bounded denominator.  If, in addition, f does not have an interval of
fixed points, this clearly shows the set of "eventual fixed points" is
recursive.  I believe the proof will go through even if f has an interval
of fixed points; but this still doesn't solve the general case.



--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; please mail anything important.