home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: sci.math.research
- Path: sparky!uunet!spool.mu.edu!sol.ctr.columbia.edu!usc!zaphod.mps.ohio-state.edu!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!usenet
- From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
- Subject: Re: decidability and dynamical systems
- References: <Bu9B1J.H8E@ens-lyon.fr>
- Nntp-Posting-Host: dn66.dse.beckman.com
- Message-ID: <a_rubin.716248328@dn66>
- Sender: Daniel Grayson <dan@math.uiuc.edu>
- X-Submissions-To: sci-math-research@uiuc.edu
- Organization: University of Illinois at Urbana
- X-Administrivia-To: sci-math-research-request@uiuc.edu
- Approved: Daniel Grayson <dan@math.uiuc.edu>
- Date: Fri, 11 Sep 1992 21:52:08 GMT
- Lines: 38
-
- 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.
-
-