🚀 go-pugleaf

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.