[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: 54:Recursion Theory/Dynamics*From*: Harvey Friedman <friedman@math.ohio-state.edu>*Date*: Thu, 22 Jul 1999 21:28:09 +0100*Sender*: owner-fom@math.psu.edu

This is the 54th in a series of self contained postings to fom covering a wide range of topics in f.o.m. Previous ones are: 1:Foundational Completeness 11/3/97, 10:13AM, 10:26AM. 2:Axioms 11/6/97. 3:Simplicity 11/14/97 10:10AM. 4:Simplicity 11/14/97 4:25PM 5:Constructions 11/15/97 5:24PM 6:Undefinability/Nonstandard Models 11/16/97 12:04AM 7.Undefinability/Nonstandard Models 11/17/97 12:31AM 8.Schemes 11/17/97 12:30AM 9:Nonstandard Arithmetic 11/18/97 11:53AM 10:Pathology 12/8/97 12:37AM 11:F.O.M. & Math Logic 12/14/97 5:47AM 12:Finite trees/large cardinals 3/11/98 11:36AM 13:Min recursion/Provably recursive functions 3/20/98 4:45AM 14:New characterizations of the provable ordinals 4/8/98 2:09AM 14':Errata 4/8/98 9:48AM 15:Structural Independence results and provable ordinals 4/16/98 10:53PM 16:Logical Equations, etc. 4/17/98 1:25PM 16':Errata 4/28/98 10:28AM 17:Very Strong Borel statements 4/26/98 8:06PM 18:Binary Functions and Large Cardinals 4/30/98 12:03PM 19:Long Sequences 7/31/98 9:42AM 20:Proof Theoretic Degrees 8/2/98 9:37PM 21:Long Sequences/Update 10/13/98 3:18AM 22:Finite Trees/Impredicativity 10/20/98 10:13AM 23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM 24:Predicatively Unfeasible Integers 11/10/98 10:44PM 25:Long Walks 11/16/98 7:05AM 26:Optimized functions/Large Cardinals 1/13/99 12:53PM 27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM 28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM 28':Restatement 1/28/99 5:49AM 29:Large Cardinals/where are we? I 2/22/99 6:11AM 30:Large Cardinals/where are we? II 2/23/99 6:15AM 31:First Free Sets/Large Cardinals 2/27/99 1:43AM 32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM 33:A Variant 3/4/99 1:52PM 34:Walks in N^k 3/7/99 1:43PM 35:Special AE Sentences 3/18/99 4:56AM 35':Restatement 3/21/99 2:20PM 36:Adjacent Ramsey Theory 3/23/99 1:00AM 37:Adjacent Ramsey Theory/more 5:45AM 3/25/99 38:Existential Properties of Numerical Functions 3/26/99 2:21PM 39:Large Cardinals/synthesis 4/7/99 11:43AM 40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM 41:Strong Philosophical Indiscernibles 42:Mythical Trees 5/25/99 5:11PM 43:More Enormous Integers/AlgGeom 5/25/99 6:00PM 44:Indiscernible Primes 5/27/99 12:53 PM 45:Result #1/Program A 7/14/99 11:07AM 46:Tamism 7/14/99 11:25AM 47:Subalgebras/Reverse Math 7/14/99 11:36AM 48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM 49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM 50:Enormous Integers/Number Theory 7/17/99 11:39PN 51:Enormous Integers/Plane Geometry 7/18/99 3:16PM 52:Cardinals and Cones 7/18/99 3:33PM 53:Free Sets/Reverse Math 7/19/99 2:11PM NOTE: There is a bad typo in #53:Free Sets/Reverse Math. I wrote: >Let F:N^k into N. An F-free set is an A containedin N such that for all >x1,..., xk in N, if F(x1,...,xk) is in A then F(x1,...,xk) is among x1,...,xk. I meant to write: Let F:N^k into N. An F-free set is an A containedin N such that for all x1,..., xk in A, if F(x1,...,xk) is in A then F(x1,...,xk) is among x1,...,xk. Sorry for the confusion. I'm grateful to Jeff Hirst for pointing this out. ************** We consider semilinear self maps of the unit square IxI. These are functions F:IxI into IxI whose graph is a semilinear set as a subset of I^4. It is well known that this is the same as there being a semilinear partition of IxI such that F is affine on each piece. And if F is, in addition, continuous, then F is what is generally called "continuous piecewise linear". We actually focus on the rational semilinear self maps of the unit square. A rational semilinear set is a semilinear set that is given by a Boolean combination of inequalities with rational coefficients. It is well known that this is the same as there being a rational semilinear partition of IxI such that the function is rational affine on each piece. And F is a continuous rational semilinear self map of IxI if and only if F is a continuous piecewise linear self map of IxI with rational break points and rational values at rational break points. We write PL(IxI,Q) for the set of all rational semilinear self maps of the unit square, and CPL(IxI,Q) for the continuous ones. A presentation of a semilinear set is any Boolean combination of inequalities that defines it. A presentation of a rational semilinear set is any Boolean combination of inequalities with rational coefficients that defines it. Note that in the rational case, each presentation is a discrete object. It is well known from decision procedures for the field of real numbers (actually we need only need the group of real numbers) that one can effectively tell whether a presentation of an element of PL(IxI,Q) is a presentation of an element of CPL(IxI,Q). Let T be an element of CPL(IxI,Q). A very basic question is whether there exists n >= 1 such that T^n(0) = 0. THEOREM 1. There is no algorithm which, given a presentation of an element T of CPL(IxI,Q), determines whether there exists n >= 1 such that T^n(0) = 0. There is no algorithm which, given a presentation of an element T of CPL(IxI,Q), determines whether the orbit of the origin under T is finite. Here the orbit of x under T is the set {x,Tx,TTx,...}. Let DQ be the set of dyadic rationals. THEOREM 2. The sets of the form {x in I intersect DQ: there exists n >= 1 such that T^n(x,0) = (0,0)}, where T is in PL(IxI,Q), are exactly the recursively enumerable subsets of I intersect DQ. The sets of the form {x in I intersect DQ: there exists n >= 1 such that T^n(x,0) = (x,0)}, where T is in PL(IxI,Q), are exactly the recursively enumerable subsets of I intersect DQ. The sets of the form {x in I intersect DQ: the orbit of (x,0) under T is finite}, where T is in PL(IxI,Q), are exactly the recursively enumerable subsets of I intersect DQ. These two Theorems just barely scratch the surface of "an interpretation of recursion (computability) theory in terms of the dynamics of rational semilinear self maps". I was intending to say more at this point about this topic, but on a closer analysis, the dynamics of these maps is a much more delicate matter than I had previously thought. I intend to come back to this.

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]