Our example is a Z -subshift, and we interpret subsystems in the sense of being closed under the Z -action, while subsystems in the sense of need to be closed under the induced N -action only. The proof of this is given in Section 3, Proposition 3. There exists a recursive universal subshift with finitely manyminimal subsystems. It turns out that thisis not a very strong condition, and as such, the conjecture is false. A universal symbolic system has infinitely many minimalsubsystems.Ĭonversely, this conjecture would imply that a system with finitely manyminimal subsystems has to be non-universal (even if not necessarily decidable).Note that this conjecture talks about infinitely many minimal subsystems, butallows us to have any number of subsystems in general. It is interesting to ask where the precise border ofdecidability lies, by extending the family of subshifts further, and to this endthe authors also make the following conjecture.Ĭonjecture 1 (). The algorithm of must be even smarter: if no w with this listof properties exists, then after enumerating some finite number of forbiddenpatterns, the algorithm will state this fact.The algorithm of applies more generally to systems where every propersubsystem has nonempty interior, and to systems whose limit set is a finiteunion of minimal systems. In thispaper, we consider the cases M ∈, an algorithm can check whether thereexists a subword w of a point of X where the number of 1s differs from thenumber of 0s by more than 7 while simultaneously the number of 2s in w is notdivisible by 5.It is not particularly hard to show that if the forbidden words of X can beenumerated and X is minimal, then also the words that do occur in X can beenumerated (see Theorem 7), so that if such w exists, a rather simple algorithmcan find it. M ⊂ X, where M is a monoid and S a finite set.A system is called decidable if the model-checking problem for Mullerlanguages is decidable, and universal if its model-checking problem for regu-lar languages is Σ -complete (that is, the halting problem many-one reduces Here, subshifts are sets X ⊂ S M which are topologically closed, and also closed under theshift action of M in the sense X The model-checking problem for regular languages is the question ofwhether a finite sequence of observations in the language can be made in thesystem. Given any finite clopenpartition of a space and a Muller language of infinite words (one of the no-tions of regularity for infinite words) with partition elements as letters, the model-checking problem is defined as the problem of checking whether one ofthe sequences in the language corresponds to a sequence of observations alongan orbit.
These systems generalize one-sided subshifts whoselanguage is recursive, and also contain many other symbolic systems such asTuring machines, counter machines and tag systems. More generally, dynamical systems oncompact metric spaces always contain minimal subsystems.In, zero-dimensional dynamical systems with an N -action and an effec-tive presentation, called symbolic systems, are studied from the point of view ofcomputational universality. We direct the reader to for a discussion of such systems. Some reasons that these subshifts are of great in-terest are that every subshift contains a minimal subshift, and many naturalexamples of subshifts, such as those generated by primitive substitutions andthose generated by Toeplitz sequences, are minimal. These are precisely the nonempty subshifts containing no propernonempty (sub-)subshifts. One of the most studied classes of subshifts in the literature is that of mini-mal subshifts. With N -actions, their theory essentially reduces to thetheory of minimal systems, but with Z -actions, the class is much larger.We show many examples of such subshifts, and in particular construct auniversal system with only a single proper subsystem, refuting a conjec-ture of.
We introduce the quasiminimal subshifts, subshifts having only finitelymany subsystems. J a n Decidability and Universality of QuasiminimalSubshifts
0 kommentar(er)
