\documentstyle[12pt]{article}
\title{ONE-DIMENSIONAL DYNAMIC AND\\ FACTORS OF FINITE AUTOMATA}
\author{Petr K\accent23urka \vspace{8pt}\\
Dept. of Mathematical Logic and Philosophy of Mathematics,\\
Faculty of Mathematics and Physics, Charles University\\
Malostransk\'{e} n\'{a}m\v{e}st\'{\i} 25, 118 00 Praha 1, Czechia\\
{\small fax: (422) 532 742, email: kurka@cspguk11.bitnet}}
\date{}
\newcommand{\mez}{\vspace{10pt}}
\newcommand{\arleft}[2] {\begin{picture}(100,10)
\put(10,0){$#2$} \put(27,3){\vector(1,0){48}} \put(48,10){$#1$}
\put(83,0){$#2$} \end{picture} }
\newcommand{\arup}[2] {\begin{picture}(100,25)
\put(3,12){$#1$} \put(94,12){$#2$}
\put(15,2){\vector(0,1){23}} \put(88,2){\vector(0,1){23}}
\end{picture} }
\newcommand{\ardown}[2] {\begin{picture}(100,25)
\put(3,12){$#1$} \put(94,12){$#2$}
\put(15,25){\vector(0,-1){23}} \put(88,25){\vector(0,-1){23}}
\end{picture}}
\newtheorem{dfn}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{pro}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\begin{document}
\maketitle
\begin{abstract}
We argue that simple dynamical systems are factors of finite
automata, regarded as dynamical systems on discontinuum. We show
that any homeomorphism of the real interval is of this class. An
orientation preserving homeomorphism of the circle is a factor of
a finite automaton iff its rotation number is rational.
Any $S$-unimodal system on the real interval, whose kneading
sequence is either periodic odd or preperiodic, is also a factor of a
finite automaton, while $S$-unimodal systems at limits of period
doubling bifurcations are not.
\end{abstract}
\section{Introduction}
The simplest dynamical systems are characterized by the presence
of single fixed points, which attract all other points, the
typical example being the halving of the interval $H(x)=x/2$.
Chaotic systems, on the other hand, keep visiting every region of
the state space in apparently chaotic manner, the simplest
example being the doubling of the circle $D(x) = 2x \mbox{ mod }
1$. Nevertheless, the latter system does not seem to be more
complex, and can be regarded as a dual, of the former. Indeed if
$x=0.x_{0}x_{1}x_{2}...$ is a binary expansion of $x \in [0,1]$,
then $H(x) = 0.0x_{0}x_{1}...$, while $D(x) = 0.x_{1}x_{2}...$.
It turns out that both systems are factors of finite automata
regarded as dynamical systems on discontinuum. The halving of the
interval writes zero to the output tape, while the doubling of
the circle reads a digit from the input tape.
These considerations lead to a complexity classification of
dynamical systems. According to a generalized Alexandrov
Theorem, every dynamical system on a compact metric space is a
factor of some dynamical system on discontinuum (see Balcar and
Simon \cite{kn:Balcar} for a proof). Every type of automata
studied in computer science can be regarded as a class of
dynamical systems on discontinuum. The complexity hierarchy
ranging from finite automata, stack automata, Turing automata,
and cellular automata to neural networks can be transferred to
dynamical systems on compact metric spaces via factorization.
The factors of finite automata are at the bottom of this hierarchy.
We have shown in \cite{kn:Kurka} that they include systems with
finite attractors and hyperbolic systems.
In the present paper we extend and generalize these results.
We use a more general concept of a multitape finite automaton with
variable advance of its tapes. We show that an orientation
preserving homeomorphism of the circle is a factor of a finite
automaton iff its rotation number is rational. We show that any
$S$-unimodal system on real interval with preperiodic or odd
periodic kneading sequence is a factor of a
finite automaton. To obtain these results we modify the kneading
theory using the two closed intervals on either side of the
critical point instead of the open ones. There are multiple
itineraries in some cases, and we choose as a standard the least
one. This modification substantially simplifies the theory, and
we obtain immediately a homomorphism from itineraries to points.
Our approach is dual to that of Crutchfield and Young
\cite{kn:Crutch}, who investigate the regularity of languages
generated by quadratic systems.
Finally we prove that the $S$-unimodal systems with aperiodic
kneading sequences, which occur at common limits
of period doubling and band merging bifurcations, are not factors
of finite automata. Thus we leave open the case of even periodic
and arbitrary aperiodic kneading sequences. The negative results
are obtained with the use of a topological property of having chaotic
limits. This is another simplicity criterion for dynamical systems.
The standard Devaney's \cite{kn:Devaney} definition reads that a chaotic
system is one, which is topologically transitive, whose periodic
points are dense, and which is sensitive to initial conditions.
However, Brooks et al.\ \cite{kn:Brooks} have recently proved,
that on infinite metric spaces, the first two conditions imply
the third. In light of this result it is natural to relax the
definition of chaotic system to topological transitivity and
density of periodic points. According to this relaxed definition,
finite dynamical systems, which are orbits of periodic points,
are chaotic too. These considerations provide some support for
the feeling that chaotic systems are simple too. We define a
system with chaotic limits as one, whose each point is included
in a set, whose $\omega$-limit set is chaotic. We show that
systems which do not have chaotic limits are not factors of
finite automata.
\section{Systems with chaotic limits}
\begin{dfn} A dynamical system $(X,f)$ is a continuous map
$f: X \rightarrow X$ of a compact metric space $X$ to itself.
A homomorphism $\varphi: (X,f) \rightarrow (Y,g)$ of dynamical
systems is a continuous mapping $\varphi:X \rightarrow Y$ such
that $g \varphi = \varphi f$. We say that $(Y,g)$ is a factor of
$(X,f)$, if $\varphi$ is a factorization (i.e. a surjective map).
\begin{picture}(200,55)
\put(124,45){\arleft{f}{X}}
\put(124,15){\ardown{\varphi}{\varphi}}
\put(124,5) {\arleft{g}{Y}}
\end{picture}
\end{dfn}
\noindent
The $n$-th iteration of $f$ is defined by $f^{0}(x)=x$,
$f^{n+1}(x)=f(f^{n}(x))$. A point $x \in X$ is periodic with
period $n>0$, if $f^{n}(x)=x$ and $f^{i}(x) \neq x$ for $0n} f^{m}(A)}$.
It is easy to see that if $A$ is nonempty, then $\omega(A)$ is a
nonempty, closed, invariant set, so $(\omega(A),f)$ is a
dynamical system. If $\varphi: (X,f) \rightarrow (Y,g)$ is a
homomorphism, then $\varphi(\omega_{f}(A)) =
\omega_{g}(\varphi(A))$.
\begin{dfn}
A dynamical system $(X,f)$ is chaotic, if the set of its periodic
points is dense in $X$ and if for any open nonempty sets $U,V
\subseteq X$ there exists $k>0$ with $f^{k}(U) \cap V \neq 0$
(topological transitivity). The system $(X,f)$ has chaotic
limits, if for each $x \in X$ there exists $A \subseteq X$, such
that $x \in A$ and $\omega(A)$ is chaotic.
\end{dfn}
\noindent
In particular a finite system is chaotic iff it is an orbit of a
periodic point, and any finite system has chaotic limits. If
$\omega(x)$ is a periodic orbit for each $x \in X$, then $(X,f)$
is a system with chaotic limits. Moreover if $X$ or $\omega(X)$
is chaotic, then $(X,f)$ has chaotic limits. It is easy to see
that a factor of a chaotic dynamical system is chaotic, and a
factor of a system with chaotic limits has chaotic limits.
\section{Finite automata}
Let $A$ be a finite alphabet and $N=\{0,1,...\}$ the set of
non-negative integers. We frequently use alphabet $2=\{0,1\}$.
Denote $A^{N}= \{u = u_{0}u_{1}... : u_{i} \in A \}$ the set of
infinite sequences of letters of $A$, $A^{*}$ the set of finite
sequences, and $\overline{A^{*}} = A^{*} \cup A^{N}$. Denote
$:u:$ the length of a sequence $u \in \overline{A^{*}}$,
($0 \leq :u: \leq \infty)$, and $\wedge$ the word of zero length so,
$u_{i}=\wedge$ for $i>:u:$. Denote $u_{:i} = u_{0}...u_{i-1}$ the
initial substring of $u$ of length $i$, and write $u \sqsubseteq v$,
if $u$ is an initial substring of $v$. If $u \in A^{*}$,
denote $\overline{u} \in A^{N}$ the infinite repetition of $u$,
defined by $\overline{u}_{k:u:+i} = u_{i}$. Define a metric
$\varrho_{A}$ on $\overline{A^{*}}$ by $\varrho_{A}(u,v) =
2^{-n}$, where $n = \inf\{i \geq 0: u_{i} \neq v_{i} \}$.
We define the shift $\sigma: \overline{A^{*}} \rightarrow
\overline{A^{*}}$ by $\sigma(u)_{i}=u_{i+1}$, thus
$\sigma(\wedge) = \wedge$. We use also inverse shifts. To unify
the formalism, suppose that $\bullet, \sharp$ are symbols not
occurring in $A$, and define $\sigma_{a}: A^{N} \rightarrow
A^{N}$ for $a \in A \cup \{\bullet,\sharp\}$ by
\[ \begin{array}{ll}
\sigma_{\sharp}(u_{0}u_{1}u_{2}...) = u_{1}u_{2}u_{3}...\\
\sigma_{\bullet}(u_{0}u_{1}u_{2}...) = u_{0}u_{1}u_{2}...\\
\sigma_{a}(u_{0}u_{1}u_{2}...) = au_{0}u_{1}... & \mbox{ for }
a \in A \end{array} \]
An automaton (finite, stack or Turing) is a finite control
attached to one or more tapes with some rules of access to them.
For formal reasons it is simpler to conceive an automaton as a
finite system of infinite tapes, which interact at their ends.
In general case these tapes are stacks, so a letter can be either
read or written to them. Two stacks already can be used to
simulate any Turing machine. Finite automata possess only input
or output tapes, which move in one direction only.
\begin{dfn}
Let $T$ be a finite set (of tapes) and for each $t \in T$ let
$A_{t}$ be a finite alphabet. Denote $Q = \prod_{t \in T} A_{t}$,
$X = \prod_{t \in T} A_{t}^{N}$ the state space with a product
metric $\varrho$, and $\pi:X \rightarrow Q$ the projection
defined by $\pi(u)_{t} = u_{t0}$. An automaton with tapes $T$,
alphabets $A_{t}$ and transition functions
$f_{t}: Q \rightarrow A_{t} \cup \{\bullet,\sharp\}$
is a dynamical system $(X,f)$ defined by
\[ f(u)_{t} = \sigma_{f_{t} \pi(u)}(u_{t}) ,\;\; u \in X,\;\; t \in T \]
We say that $t \in T$ is an input tape, if
$\;(\forall q \in Q)(f_{t}(q) \in \{\bullet,\sharp\})$.
We say that $t \in T$ is an output tape, if
$\;(\forall q \in Q)(f_{t}(q) \in A_{t} \cup \{\bullet\})$.
An automaton is a finite automaton, if every tape is either input
tape or output tape.
\end{dfn}
\begin{dfn}
For an automaton $(X,f)$ over $T$, $u \in X$, $n \geq 0$ define
the advance $d_{t}(u,n)$ of $t$ in $n$ steps by $d_{t}(u,0)=0$,
$d_{t}(u,1) = 1$ if $f_{t} \pi (u) = \sharp$, $d_{t}(u,1) = 0$ if
$f_{t} \pi (u) = \bullet$, $d_{t}(u,1) = -1$ if $f_{t} \pi (u)
\in A_{t}$, and $d_{t}(u,n+1) = d_{t}(u,1) + d_{t}(f(u),n)$ for
$n>0$. Clearly $:d_{t}(u,n): \leq n$.
\end{dfn}
\begin{thm} \label{limit}
Any finite automaton has chaotic limits.
\end{thm}
Proof: Let $(X,f)$ be a finite automaton and $w \in X$. Denote
$Q_{0}=\{q \in Q: (\forall m)(\exists n \geq m)(\pi f^{n}(w) = q)
\}$, $T_{in} = \{t \in T: (\exists q \in Q_{0})(f_{t}(q) = \sharp
) \}$, $T_{out}=\{t \in T:(\exists q \in Q_{0})(f_{t}(q) \in
A_{t}) \}$, $T_{\bullet} = T - T_{in} - T_{out}$. Since $(X,f)$
is a finite automaton, $T_{in} \cap T_{out} = 0$. Let $j$ be the
first integer, such that $(\forall n \geq j)(\pi f^{n}(w) \in
Q_{0})$ and denote\\ \hspace*{30pt}
$Y = \{ u \in X:(\forall i)(\pi f^{i}(u) \in Q_{0}) \;\&\;
(\forall t \in T_{\bullet})(\forall i)(u_{ti} = f^{j}(w)_{ti})
\}$.\\ Then $Y$ is a closed invariant set. Let $p$ be the least
integer, for which there exists $z \in Y$ with $\{\pi f^{i}(z): i
0)(:\{in+m+p$ be an integer divisible by $p$. There
exists $s \in Y$ satisfying $\pi(s) = \pi(v)$, and for all $t \in
T_{in}$
\[ \begin{array}{lll}
s_{t,i} = z_{t,i} & \mbox{ for } & 1 \leq i \leq a=d_{t}(z,r)
\\ s_{t,a+i}=v_{t,i} & \mbox{ for } & 1 \leq i \leq
b=d_{t}(v,n+m)\\ s_{t,a+b+i} = z_{t,\ell+i} & \mbox{ for } & 1
\leq i,
\mbox{ where } \pi f^{n+m}(v)=\pi f^{\ell}(z) \end{array} \]
Then $s \in W$, $f^{r}(s)_{ti} = v_{ti}$ for all $i \leq
d_{t}(v,n+m)$, $t \in T_{in}$, and $\varrho(f^{r+n}(s),f^{n}(v))$
$\leq 2^{-k}$, so $\varrho(f^{r+n}(s),u) \leq 2^{-k}$, and
therefore $u \in \omega(W)$. $\Box$
\begin{lem}
$\omega(W \cup\{w\}) = \omega(W)$.
\end{lem}
Proof: It suffices to show $\omega(w) \subseteq \omega(W)$. Let
$u \in \omega(w)$ and $k>0$. We have $f^{j}(w) \in Y$ and there
exist $n,m$, such that $d_{t}(f^{j}(w),n) \leq -k$ for all $t
\in T_{out}$, $\varrho(f^{j+n}(w),u) \leq 2^{-k}$, and
$d_{t}(f^{j+n}(w),m) \geq k$. By Lemma \ref{limit1},
$u \in \omega(W)$. $\Box$.
\begin{lem}
Periodic points are dense in $\omega(W)$.
\end{lem}
Proof: Let $U \subseteq X$ be an open set, and $U \cap \omega(W)
\neq 0$. There exists $u \in U$ and $k$ such that $u \in C_{k}(u)
\cap \omega(W) \subseteq U \cap \omega(W)$, where $C_{k}(u) = \{
v \in X: u_{:k}=v_{:k} \}$ is a cylinder around $u$. There exist
$m$ and $v \in W$ such that $\varrho(f^{m}(v),u) \leq 2^{-k}$,
and $:d_{t}(v,m): \geq k$ for all $t \in T_{in} \cup T_{out}$.
There exists $r>m+k$ and $s \in Y$ such that $\pi(s) = \pi(v)$, and
\[ \begin{array}{ll}
s_{t,i} = v_{t,i} & \mbox{ for } t \in T_{in}, \;\;
1 \leq i \leq d_{t}(v,m)+k \\
\{\pi f^{i}(s): im+k$, $r'>r+m'+k$ and $s \in Y$ such that
\[ \begin{array}{ll}
s_{t,i} = v_{t,i} & \mbox{ for } t \in T_{in},\;\;
1 \leq i \leq d_{t}(v,m)+k \\
\pi f^{r}(s) = \pi(v'),\\
s_{t,a+i} = v'_{t,i} & \mbox{ for } t \in T_{in},\;\;
1 \leq i \leq d_{t}(v',m')+k,\;\; a = d_{t}(s,r) \\
\{\pi f^{i}(s): i0$ define $\varphi(u) = g^{k} \varphi
\sigma^{k}(u)$, $\varphi(\overline{0}) = a$. Then
$\varphi : (2^{N},\sigma_{0}) \rightarrow (I,g)$ is a
factorization. $\Box$
\begin{lem} \label{increase2}
Let $(X,f)$ be a two tape finite automaton defined by $f(u,v)$ =
$(\sigma_{\sharp}(u), \sigma_{\max(u_{0},v_{0})}(v))$. Let $g : I
\rightarrow I$ be an increasing continuous function on a compact
real interval $I$, whose only fixed points are the two endpoints
of $I$. Then $(I,g)$ is a factor of $(X,f)$.
\end{lem}
Proof: Let $I=[a,b]$ and pick some $c \in (a,b)$. Suppose
$f(c)>c$ (the dual case $f(c) 0 \\
X_{\infty} & = & \{(u,v) \in X: (\forall i \geq 0)(v_{i}=1) \}
\end{array} \]
For $k \in Z$ define a projection $\pi_{k}: X_{k} \rightarrow
2^{N}$ by $\pi_{k}(u,v) = \sigma^{k}_{\sharp}(v)$ if $k \geq 0$,
and $\pi_{k}(u,v) = \sigma^{-k}_{0}(v)$ if $k \leq 0$. Then
$\pi_{k+1}f(u,v)=\pi_{k}(u,v)$ for $(u,v) \in X_{k}$. Let
$\psi : 2^{N} \rightarrow I_{0}$ be a factorization. Define
$\varphi(u,v) = g^{k} \psi \pi_{k}(u,v)$ for $(u,v)
\in X_{k}$, $\varphi(u,v)=a$ for $(u,v) \in X_{-\infty}$, and
$\varphi(u,v) = b$ for $(u,v) \in X_{\infty}$. Then $\varphi:
(X,f) \rightarrow (I,g)$ is a factorization. $\Box$
\begin{pro} \label{increase}
Let $g: I \rightarrow I$ be a non-decreasing continuous map on a
compact real interval $I$. Then $(I,g)$ is a factor of a finite
automaton.
\end{pro}
Proof: Define a finite automaton $(X,h)$, where $X = 2^{N} \times
2^{N} \times 2^{N} \times 2^{N}$, and $h(y,u,v,w)$ =
$(\sigma_{0}(y),f(u,v),w)$, where $f$ is the finite automaton
from Lemma \ref{increase2}. We shall prove that $(I,g)$ is a
factor of $(X,h)$. Denote $F=\{x \in I: g(x)=x\}$ the set of
fixed points. $F$ is closed, therefore $I-F = \cup_{k \in K}
A_{k}$ is a finite or countable union of open intervals
$A_{k}=(a_{k},b_{k})$. Define $\theta :2^{N} \rightarrow I$ by
$\theta(u) = a + (b-a) \sum_{i=0}^{\infty} u_{i}2^{-i+1}$,
where $I=[a,b]$. Each $\theta^{-1}(A_{k})$ contains a cylinder
$C_{k} \subseteq 2^{N}$. Let $\prec$ be a lexicographic ordering
on $2^{N}$. Denote
$K_{0} = \{ k \in K : g(a_{k})=a_{k},\; g(b_{k})=b_{k} \}$.
If $k \not\in K_{0}$, let $\psi_{k} : (2^{N}, \sigma_{0}) \rightarrow
(\overline{A_{k}},g)$ be a factorization from Lemma \ref{increase1}.
If $k \in K_{0}$, let $\psi_{k} : (2^{N} \times 2^{N},f)
\rightarrow (\overline{A_{k}},g)$ be a factorization from Lemma
\ref{increase2}. Define $\varphi : (X,h) \rightarrow (I,g)$ by
\[ \begin{array}{lllll}
\varphi(y,u,v,w) = \theta(w) & \mbox{ if } & \theta(w) \in F \\
\varphi(y,u,v,w) = a_{k} & \mbox{ if } & \theta(w) \in A_{k}, &
\mbox{and } (\forall x \in C_{k})(w \prec x) \\
\varphi(y,u,v,w) = b_{k} & \mbox{ if } & \theta(w) \in A_{k}, &
\mbox{and } (\forall x \in C_{k})(x \prec w) \\
\varphi(y,u,v,w) = \psi_{k}(y) & \mbox{ if } & w \in C_{k}, &
\mbox{and } k \not\in K_{0} \\
\varphi(y,u,v,w) = \psi_{k}(u,v) & \mbox{ if } & w \in C_{k}, &
\mbox{and } k \in K_{0} & \Box
\end{array} \]
\begin{thm} \label{realhom}
Any homeomorphism of a real interval into itself is a factor of a
finite automaton.
\end{thm}
Proof: If $g: I \rightarrow I$ is increasing, then it is a factor
of finite automaton by Proposition \ref{increase}. If it is
decreasing, then $g^{2}:I \rightarrow I$ is increasing and
therefore there is a factorization $\psi : (X,f) \rightarrow
(I,g^{2})$, and $(X,f)$ is a finite automaton. We add to this
automaton an output tape with alphabet $2$ and define $h(u,0v)$ =
$(u,10v)$, $h(u,1v)$ = $(f(u),01v)$ ($u \in X$, $v \in 2^{*}$).
Then $h: X \times 2 \rightarrow X \times 2$ is a finite
automaton. Define $\varphi(u,0v) = \psi(u)$, and $\varphi(u,1v) =
g \psi(u)$. Then $\varphi : (X \times 2 , h) \rightarrow (I,g)$
is a factorization. Indeed $\varphi h(u,0v) = \varphi(u,10v) = g
\psi(u) = g \varphi(u,0v)$, and $\varphi h(u,1v) =
\varphi(f(u),01v) = \psi f(u) = g^{2}\psi(u) = g\varphi(u,1v)$.
$\Box$ \mez
We turn now to the orientation preserving homeomorphisms of the
circle, which we regard as the unit circle in the complex plane.
For $x \in R_{1}$ denote $\theta(x) = \exp(2\pi i x)$. An
increasing map $G: R_{1} \rightarrow R_{1}$ is a lift of an
orientation preserving homeomorphism $(S_{1},g)$, if $\theta :
(R_{1},G) \rightarrow (S_{1},g)$ is a factorization. The rotation
number $\varrho(g)$ of $(S_{1},g)$ is defined as the fractional
part of $\varrho_{0}(G) = \lim_{n \rightarrow \infty}
:G^{n}(y):/n$, where $G$ is any lift of $g$, and $y \in R_{1}$
($\varrho(g)$ does not depend on the choice of either $G$ or
$y$). Then an orientation preserving homeomorphism of the circle
$(S_{1},g)$ has a periodic point iff $\varrho(g)$ is rational
(see Devaney \cite{kn:Devaney} for a proof).
\begin{thm}
An orientation preserving homeomorphism $(S_{1},g)$ of the circle
is a factor of a finite automaton iff $\varrho(g)$ is rational.
\end{thm}
Proof: If $(S_{1},g)$ is a factor of a finite automaton, then it
has chaotic limits by Theorem \ref{limit}, and therefore also
periodic points. Thus its rotation number cannot be irrational.
If $\varrho(g)$ is rational, then $\varrho(g^{n}) = 0$ for some
$n$, and $g^{n}$ has a fixed point. We can suppose that 1 is a
fixed point of $g$, and choose a lift $G$, with fixed points $0$
and $1$. Then $(S_{1},g^{n})$ is a factor of $([0,1],G)$, and
this is a factor of a finite automaton by Theorem \ref{realhom}.
We modify the finite automaton obtained by letting it act only
every $n$-th step similarly as in the proof of Theorem
\ref{realhom}. Then $(S_{1},g)$ is a factor of this modified
automaton. $\Box$
\section{Unimodal systems}
\begin{dfn}
A dynamical system $(I,g)$ defined on real interval $I=[a,b]$ is
unimodal, if $g(a)=g(b)=a$, and if there exists a critical point
$c \in (a,b)$, such that $g$ is increasing in $[a,c]$, and
decreasing in $[c,b]$. \end{dfn}
\begin{pro}
Let $g$ be unimodal on $[a,b]$ with critical point $c$. Denote
$I_{0}=[a,c]$, $I_{1}=[c,b]$, and $I_{u} = \{x \in I : 0 \leq i <
:u: \Rightarrow f^{i}(x) \in I_{u_{i}} \}$ for $u \in
\overline{2^{*}}$. Then $I_{u}$ are closed intervals (possibly
empty or singletons).
\end{pro}
Proof: $I_{au} = I_{a} \cap f^{-1}(I_{u})$ for $a \in 2$ and $u
\in \overline{2^{*}}$. $\Box$
\begin{dfn}
For $u \in \overline{2^{*}}$, $n<:u:$ denote $\tau_{n}(u) =
\sum_{i=0}^{n} u_{i} \mbox{ mod } 2$. We say that $u \in 2^{*}$
is even (odd), if $\tau_{:u:-1}(u)$ is zero (one). An infinite
periodic sequence $u \in 2^{\infty}$ is even (odd), if the
shortest sequence $v \in 2^{*}$ with $u = \overline{v}$ is even
(odd). For $u,v \in \overline{2^{*}}$ define
\[ \begin{array}{lll}
u \prec v & \mbox{ iff } & (\exists k < \min(:u:,:v:))
(u_{:k}=v_{:k} \;\;\&\;\; \tau_{k}(u) < \tau_{k}(v))\\
u \preceq v & \mbox{ iff } & u \prec v \;\mbox{ or }\;
u \sqsubseteq v \end{array} \]
\end{dfn}
\begin{pro} \label{interval}
Let $u,v \in \overline{2^{*}}$. Then
\[ \begin{array}{llllll}
& u \prec v & \Rightarrow & (\forall x \in I_{u})
(\forall y \in I_{v})(x \leq y) &
\stackrel{def}{\Leftrightarrow} & I_{u} < I_{v}\\
I_{u} \neq 0 \;\;\;\& & u \preceq v & \Rightarrow &
(\forall y \in I_{v})(\exists x \in I_{u})(x \leq y)
& \stackrel{def}{\Leftrightarrow} & I_{u} \leq I_{v}
\end{array} \]
\end{pro}
Proof: Let $u \prec v$, $k< :u:$, $k < :v:$, $u_{:k}=v_{:k}$,
$\tau_{k}(u) < \tau_{k}(v)$, $x \in I_{u}$, $y \in I_{v}$. We
prove $x \leq y$ by induction on $k$. If $k=0$, then $u_{0}=0$,
$v_{0}=1$, so $I_{u} \subseteq I_{0} < I_{1} \supseteq I_{v}$,
and $I_{u} < I_{v}$. If $k>0$, we apply the Proposition to
$\sigma(u)$ and $\sigma(v)$. If $u_{0}=v_{0}=0$, then $\sigma(u)
\prec \sigma(v)$, so $f(x) \leq f(y)$, and $x \leq y$ since $x,y
\in I_{0}$. If $u_{0}=v_{0}=1$, then $\sigma(v) \prec \sigma(u)$,
so $f(y) \leq f(x)$, and $x \leq y$ since $x,y \in I_{1}$.
Suppose $u \preceq v$, and $y \in I_{v}$. Since $I_{u} \neq 0$,
we have some $x \in I_{u}$. If $u \prec v$, then $x \leq y$ by
the above proof. If $u \sqsubseteq v$, then $y \in I_{u}$, and $y
\leq y$. $\Box$
\begin{dfn}
The itinerary ${\cal I}(x) \in 2^{N}$ of $x \in I$ is defined by
\[ \begin{array}{lll}
g^{i}(x) < c & \Rightarrow & {\cal I}(x)_{i}=0\\
g^{i}(x) > c & \Rightarrow & {\cal I}(x)_{i}=1\\
g^{i}(x) = c & \Rightarrow & \tau_{i}({\cal I}(x))=0
\end{array} \]
The kneading sequence of $g$ is ${\cal K}(g) = {\cal I}(g(c))$.
\end{dfn}
\begin{pro} \label{order}
\[ \begin{array}{rcl}
x \in I_{u} & \Rightarrow & {\cal I}(x) \preceq u\\
{\cal I}(x) \prec {\cal I}(y) & \Rightarrow & x \leq y \\
x < y & \Rightarrow & {\cal I}(x) \preceq {\cal I}(y)
\end{array} \] \end{pro}
Proof: The first formula follows from the definition. If ${\cal
I}(x) \prec {\cal I}(y)$, then $I_{{\cal I}(x)} < I_{{\cal
I}(y)}$. Since $x \in I_{{\cal I}(x)}$, $y \in I_{{\cal I}(y)}$,
we get $x \leq y $ by Proposition \ref{interval}. If $x0)(\sigma^{i}(u) \preceq v)$, and $u \ll^{*} v$ if
$u \ll v$ and $u \preceq v$. A sequence $w \in \overline{2^{*}}$
is maximal, if $\;w \ll w$.
\end{dfn}
\begin{thm} \label{knead1}
If $(I,g)$ is unimodal, then
$(\forall x \in I)({\cal I}(x) \ll {\cal K}(g))$, and ${\cal
K}(g)$ is maximal.
\end{thm}
Proof: Let $x \in I$ and $k > 0$. Denote $u = {\cal I}(x)$ and
suppose $\sigma^{k}(u) \succ {\cal K}(g)$. We have $g^{k}(x) \leq
g(c)$. If $g^{k}(x) = g(c)$, then $g^{k-1}(x) = c$, and
$\tau_{k-1}({\cal I}(x)) = 0$, so $\sigma^{k}(u) = {\cal
I}(g^{k}(x)) = {\cal K}(g)$, which is a contradiction. Thus
$g^{k}(x) < g(c)$, so $g^{k-1}(x) \neq c$, and by Proposition
\ref{order}, ${\cal I}(g^{k}(x)) \preceq {\cal K}(g)$. Let
$i \geq k$ be the least number with $g^{i}(x)=c$ (such a number
exists, since otherwise ${\cal I}(g^{k}(x)) = \sigma^{k}(u)$).
There exists $y \in I$ with ${\cal I}(y)=0u_{k}...u_{i}...$ and
$f^{j}(y) \neq c$ for $0 \leq j \leq i-k+1$. Then $f(y) 0$, and since the set
$\{\sigma^{i}(w) : i>0\}$ is finite, there exists $p$ such that
$\sigma^{i}(w)_{:p} \prec w_{:p}$ for all $i>0$. Let $k$ be an
integer with $nk>p$ and put $r=m+nk$, $s=m+(n+1)k$. Assume
$w_{:r}u \ll^{*} w$ and let us prove $\sigma^{i}(w_{:s}u) \preceq w$
for all $i \geq 0$. For $i=0$ we distinguish two cases. If $w_{:m}$
is even then $w_{:r}$ is even, and $u \preceq \sigma^{r}(w) =
\sigma^{s}(w)$ by the assumption, so $w_{:s}u \preceq w$.
If $w_{:m}$ is odd then $u \succeq
\sigma^{r}(w) =\sigma^{s}(w)$, and again $w_{:s}u \preceq w$. For
$0< i
n$ and $\sigma^{i}(w_{:s}u) = \sigma^{i-n}(w_{:r}u) \preceq w$.
Conversely, if $w_{:s}u \ll^{*} w$, then $w_{:r}u \ll^{*} w$.
By induction, $(\forall u \in 2^{N})(w_{:r}u \ll^{*} w
\Leftrightarrow w_{:r+jn}u \ll^{*} w)$ for all $j>0$.
We construct a finite automaton with input alphabet $A_{0}=2$, and
output alphabets $A_{1}=2$, $A_{2}=\{0,...,s-1\}$. Put $f_{0}(q)
= \sharp$, $f_{1}(q) = q_{0}$ if $w_{:q_{2}}q_{0} \preceq w$,
$f_{1}(q) = 1-q_{0}$ otherwise. Then $w_{:q_{2}}f_{1}(q) \preceq
w$. If $w_{:q_{2}}f_{1}(q) = w_{:q_{2}+1}$, then put $f_{2}(q) =
q_{2}+1$ if $q_{2}+1 < s$, and $f_{2}(q) = r$ if $q_{2}+1 = s$.
If $w_{:q_{2}}f_{1}(q) \prec w_{:q_{2}+1}$, then put
$f_{2}(q) = \max\{k2$,
and $U_{j} = \{u \in \Sigma_{{\cal D}^{\infty}(s)} :
(\exists i \leq 2^{j+1}:s:)({\cal D}^{j}(s) \sqsubseteq
\sigma^{i}(u) \;\mbox{ or } \; \widehat{{\cal D}^{j}(s)}
{\cal D}(s) \sqsubseteq \sigma^{i}(u) \}$. Then $U_{j}$ is a
$\sigma$-invariant set, which is closed and open in
$\Sigma_{{\cal D}^{\infty}(s)}$, and does not contain periodic
points with periods less than $2^{j}:s:$.
\end{lem}
Proof: Clearly $U_{j}$ is closed and open in $\Sigma_{{\cal
D}^{\infty}(s)}$. To prove it is invariant denote $w = {\cal
D}^{j-2}(s)$ and suppose $u \in U_{j}$. Then we can write
$\sigma^{i}(u)=u_{0}u_{1}...$, where $:u_{i}: = 2^{j-2}:s:$.
We use repeatedly the fact $u \ll {\cal D}^{\infty}(s)$ and
prove that if $u_{0}u_{1}u_{2}u_{3} = w\hat{w}ww$, then either
$u_{4}u_{5}u_{6}u_{7}=w\hat{w}ww$ or $u_{4}...u_{11} =
w\hat{w}w\hat{w}w\hat{w}ww$. Since $u_{0}u_{1}u_{2}u_{3}u_{4} \preceq
w\hat{w}www$, and $w\hat{w}ww$ is odd, $u_{4} \succeq w$. Since
$u_{4} \preceq w$, we get $u_{4}=w$. Since $u_{4}u_{5} \preceq
w\hat{w}$, $u_{5} \succeq \hat{w}$. Since $u_{0}...u_{5} \preceq
w\hat{w}www\hat{w}$, and $w\hat{w}www$ is even, $u_{5} \preceq
\hat{w}$, so $u_{5}=\hat{w}$. Since $u_{4}u_{5}u_{6} \preceq
w\hat{w}w$, $u_{6}=w$. Since $u_{6}u_{7} \preceq w\hat{w}$,
$u_{7} \succeq \hat{w}$, so either $u_{7}=w$ or $u_{7}=\hat{w}$.
In the former case we are done. Suppose therefore $u_{7}=\hat{w}$.
Since $u_{0}...u_{8} \preceq w\hat{w}www\hat{w}w\hat{w}w$,
$u_{8}=w$. Since $u_{8}u_{9} \preceq w\hat{w}$, $u_{9} \succeq
\hat{w}$. Since $u_{0}...u_{9} \preceq
w\hat{w}www\hat{w}w\hat{w}w\hat{w}$, $u_{9} \preceq \hat{w}$, so
$u_{9}=\hat{w}$. Since $u_{8}u_{9}u_{10} \preceq w\hat{w}w$,
$u_{10}=w$. Since $u_{0}...u_{11} \preceq
w\hat{w}www\hat{w}w\hat{w}w\hat{w}ww$, $u_{11}=w$, so
$u_{8}u_{9}u_{10}u_{11} = w\hat{w}ww$. If there is a periodic
point $u \in U_{j}$ with period $k < n = :s:2^{j}$, then
$u_{2n-1}$ = $u_{2n-1-k}$ = $u_{n-1-k}$ = $u_{n-1}$, and
$\overline{w}$ would have period $k$, which is impossible. $\Box$
\begin{pro} \label{aper}
If $s \in 2^{*}$ is an odd, aperiodic, maximal sequence, then the
subshift $(\Sigma_{{\cal D}^{\infty}(s)},\sigma)$ has not
chaotic limits.
\end{pro}
Proof: Let $U_{j}$ be sets from Lemma \ref{double}. Then
$\omega({\cal D}^{\infty}(s)) \subseteq U_{j}$, for $j>2$, so
$\omega({\cal D}^{\infty}(s))$ does not contain periodic points.
Suppose that $u \in \omega({\cal D}^{\infty}(s))$, $u \in A
\subseteq \Sigma_{{\cal D}^{\infty}(s)}$, and $\omega(A)$ is
chaotic. Then it contains a periodic point $v \in \omega(A)$.
Choose $j$ so that $v \not\in U_{j}$, and let $V$ be a
neighbourhood of $v$ disjoint from $U_{j}$. Then
$\sigma^{k}(U_{j}) \cap V = 0$ for all $k$, so $\omega(A)$ is not
transitive. $\Box$
\begin{thm} \label{chaot}
If $(I,g)$ is $S$-unimodal system, and ${\cal K}(g) = {\cal
D}^{\infty}(s)$ for some odd, aperiodic, maximal sequence $s$,
then $(I,g)$ has not chaotic limits.
\end{thm}
Proof: By Theorem \ref{nonper} there is a factorization
$\varphi: (\Sigma_{{\cal K}(g)}, \sigma) \rightarrow (I,g)$. Let
$y \in I$ be an eventually periodic point. Since ${\cal K}(g)$ is
aperiodic, $g^{i}(y) \neq c$ for all $i$, and therefore there
exists only one $u \in \Sigma_{{\cal K}(g)}$ with $y =
\varphi(u)$. Since $\omega({\cal K}(g))$ does not contain
periodic points by Proposition \ref{aper}, neither does
$\omega(c) =
\varphi(\omega({\cal K}(g))$. We prove that if $j>2$, then
$\varphi(U_{j})$ is a neighbourhood of $\omega(c)$. If $y \in
\omega(c)$, then there is unique $u \in \omega({\cal K}(g))$ with
$\varphi(u)=y$. There exists $k \leq 2^{j}:s:$ such that
$\overline{0}_{:k} \neq u_{:k} \neq 1\overline{0}_{:k}$. Define
$u',u'' \in U_{j}$ by $u'_{:k} = \overline{0}_{:k}$, $u''_{:k} =
1\overline{0}_{:k}$, $u'_{i} = u''_{i} = u_{i}$ for $i \geq k$.
Then $u' \prec u \prec u''$ and $y=\varphi(u)$ is an inner point
of the interval $[\varphi(u'), \varphi(u'')] \subseteq
\varphi(U_{j})$. Since $\varphi(U_{j})$ is invariant, we get the
result similarly as in Proposition \ref{aper}. $\Box$
\begin{cor}
Let $(I,g)$ be $S$-unimodal system, and ${\cal K}(g) = {\cal
D}^{\infty}(s)$ for some odd, aperiodic, maximal sequence $s$.
Then $(I,g)$ is not a factor of a finite automaton.
\end{cor}
Proof: Theorems \ref{limit} and \ref{chaot}.
\begin{thebibliography}{99}
\bibitem{kn:Balcar} B.Balcar, P.Simon: Appendix on general
topology. Handbook of Boolean Algebras (J.D.Monk and R.Bonnet,
eds.), Elsevier Science Publishers B.V., 1241 (1989).
\bibitem{kn:Brooks} J.Brooks, G.Cairns, G.Davis, P.Stacey: On
Devaney's definition of chaos. The American Mathematical Monthly,
99,4, 332 (1992).
\bibitem{kn:Collet} P.Collet, J.P.Eckmann.: Iterated Maps on
the Interval as Dynamical Systems. Birkhauser, Basel (1980).
\bibitem{kn:Crutch} J.P.Crutchfield, K.Young: Computation at
the onset of chaos. in: Complexity, Entropy and the Physics of
Information, SFI Studies in the Sciences of Complexity, vol VIII
(W.H.Zurek, ed.), Addison Wesley 223 (1990).
\bibitem{kn:Devaney} R.L.Devaney: An Introduction to Chaotic
Dynamical Systems. Addison-Wesley, Redwood City (1989).
\bibitem{kn:Gucken} J.Guckenheimer: Sensitive dependence to
initial conditions for one dimensional maps. Commun.Math.Phys.
70, 133 (1979).
\bibitem{kn:Kurka} P.K\accent23urka: Dynamical systems and
factors of finite automata, submitted.
\end{thebibliography}
\end{document}