home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / research / 451 < prev    next >
Encoding:
Text File  |  1992-09-11  |  2.5 KB  |  54 lines

  1. Newsgroups: sci.math.research
  2. 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
  3. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  4. Subject: Re: decidability and dynamical systems
  5. References: <Bu9B1J.H8E@ens-lyon.fr>
  6. Nntp-Posting-Host: dn66.dse.beckman.com
  7. Message-ID: <a_rubin.716248328@dn66>
  8. Sender: Daniel Grayson <dan@math.uiuc.edu>
  9. X-Submissions-To: sci-math-research@uiuc.edu
  10. Organization: University of Illinois at Urbana
  11. X-Administrivia-To: sci-math-research-request@uiuc.edu
  12. Approved: Daniel Grayson <dan@math.uiuc.edu>
  13. Date: Fri, 11 Sep 1992 21:52:08 GMT
  14. Lines: 38
  15.  
  16. In <Bu9B1J.H8E@ens-lyon.fr> koiran@ens.ens-lyon.fr (Pascal Koiran) writes:
  17.  
  18. >Hello,
  19.  
  20. >Can someone provide a solution to the following problem, or give references
  21. >to related work in the litterature ?
  22.  
  23. >Let f:[0,1]-->[0,1] be a continuous piecewise-linear function (with a finite
  24. >number of laps). The endpoints of the laps have rational coordinates.
  25. >Given such an f and a rational x \in [0,1], is it decidable whether a fixed
  26. >point is reached in finite time when f is iterated on x ?
  27. >In other words, is it decidable whether there exists t, f^t(x)=f^{t+1}(x) ?
  28.  
  29. The collection of all such x is clearly recursively enumerable.  Also,
  30. given a (one-tape, one-sided infinite) Turing machine T, it is clear that
  31. one can define a recursive piecewise linear function f with a countable
  32. number of segments, and a G of all possible tape states into [0,1] such
  33. that f(G(state)) = G(T-successor of state), so that f reaches a
  34. fixed point started at G(state) iff T halts starting at "state" (if you
  35. make the convention that any production rule which leaves the entire state
  36. fixed is replaced by a cycle back-and-forth, so that fixed points of T
  37. correspond to halted states.)
  38.  
  39. If all slopes of segments are 1/n for (positive or negative) integer n,
  40. then for any x, and t, x = A f^t(x) + Q, where A is an integer, and Q has
  41. a bounded denominator.  If, in addition, f does not have an interval of
  42. fixed points, this clearly shows the set of "eventual fixed points" is
  43. recursive.  I believe the proof will go through even if f has an interval
  44. of fixed points; but this still doesn't solve the general case.
  45.  
  46.  
  47.  
  48. --
  49. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  50. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  51. My opinions are my own, and do not represent those of my employer.
  52. My interaction with our news system is unstable; please mail anything important.
  53.  
  54.