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

Internet Message Format | 1992-09-11 | 1.1 KB

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

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, ...
For piecewise-linear functions f:[0,1]^2-->[0,1]^2, the problem is known to
be undecidable.

Thanks,

Pascal.