Abstract:
We study recurring sequences over finite fields sets and the set
$\mathbf N=\{0,1,2,\ldots\}$.
The complexity of recurring sequences over finite sets
is estimated as the complexity of computing on determinate linearly bounded
automata. We introduce the notion of a branching recurring sequence. The complexity
of branching recurring sequences over finite sets is estimated as the complexity
of computing on non-determinate linearly bounded automata.
Recurring sequences over the set $\mathbf N$ simulate computations on multi-tape
Minsky machines.
We ascertain undecidability of some problems concerning this type of recurring
sequences.
This research was supported by the Russian Foundation for Basic Research,
grant 00–01–00351.
Fulltext:
PDF file (1280 kB)