FOM: 54:Recursion Theory/Dynamics

[Harvey Friedman]

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.