NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/theory/1887

Internet Message Format | 1992-09-08 | 973 b

Path: sparky!uunet!mcsun!corton!babbage!ensl!absinthe!koiran
From: [e-mail] (Pascal Koiran)
Newsgroups: comp.theory
Subject: decidability and dynamical systems
Message-ID: <[e-mail]>
Date: 8 Sep 92 09:21:00 GMT
Sender: [e-mail]
Reply-To: [e-mail]
Organization: Ecole Normale Superieure de Lyon
Lines: 18

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) ?

One can ask the same question for other classes of non-linear functions,
such as polynomials, rational functions, ...

Thanks,

Pascal.