Printer Friendly

Shifts with decidable language and non-computable entropy.

1 Introduction

An important numerical quantity associated with a dynamical system is its topological entropy. A natural question is then: under what circumstances can one compute the topological entropy of a dynamical systems? While for specific types of dynamical systems, one can often give an algorithm, for examples see, e.g., Milnor (2002), there are also a number of negative results, e.g., for cellular automata by Hurd et al. (1992), for piecewise affine maps by Koiran (2001), and for shift spaces by Simonsen (2006) as well as by the second author, Spandl (2007). Shift spaces are an important, standard class of dynamical systems. For an introduction the reader is referred to Lind and Marcus (1995). They are closed, shift invariant subspaces of the space of bi-infinite sequences over some alphabet, usually assumed to be finite. For simplicity we will consider only subshifts of the space of all bi-infinite binary sequences. Whenever we speak about a shift space or simply a shift in this paper, we will always mean a closed, shift invariant subspace of the space of bi-infinite binary sequences.

As is well known, for simple types of shifts one can compute the entropy, for example for shifts that can be defined by a finite set of forbidden words, and also for the larger class of so-called sofic shifts; see Simonsen (2006); Spandl (2007). Furthermore, Simonsen (2005) obtained computability results for the entropy of [beta]-shifts, Spandl (2007), as well as Hertling and Spandl (2008), for the entropy of S-gap shifts, and Spandl (2007) also for the entropy of shifts having the specification property. Hochman and Meyerovitch (2007) gave a computability-theoretic characterization similar to our main result of the set of real numbers that are the entropy of a two-dimensional shift of finite type.

A natural way of describing a general shift is via its language, that is the set of all finite strings that appear as substrings of elements of the shift space. Simonsen (2006) and Spandl (2007) have shown that the entropy is not uniformly computable with respect to the language of the shift. To be precise, Simonsen (2006) has shown that there is no Turing machine which, given a decision algorithm for the language of some shift with decidable language, is able to compute the entropy of the shift with arbitrary precision. Spandl (2007) has shown that there is no oracle Turing machine which, given the language of some shift via an oracle, is able to compute the entropy of the shift with arbitrary precision. Simonsen (2006) posed the question whether there exists a shift with decidable language whose entropy is a non-computable number, and noted that "then the results in this paper related to uncomputability would follow immediately". In this paper, we construct such a shift. In fact we will show more. The second author, Spandl (2007), showed that, given an enumeration of the complement of the language of some shift space, one can approximate the entropy effectively from the right. Hence, if the complement of the language of a nonempty shift is computably enumerable then the entropy of the shift is a right-computable real number (between 0 and 1). In particular, the entropy of any nonempty shift with decidable language is a right-computable real number between 0 and 1. We will show that conversely any right-computable real number between 0 and 1 is the entropy of a shift with decidable language. In fact, it is even the entropy of an irreducible shift with a polynomial time decidable language. Since the class of right-computable real numbers between 0 and 1 is known to be strictly larger than the class of computable real numbers between 0 and 1, this shows that there exist irreducible shifts with polynomial time decidable language that have non-computable entropy.

In the following section, we give some basic definitions about shifts, forbidden words, and the language of a shift. Note that another natural way of representing a shift space is by giving a so-called set of forbidden words for it. In view of the question whether, given some information about a shift, one can compute its entropy, it is of course interesting to have a clear picture of the relation between different kinds of information about a shift. Here, we analyze the relation between two different kinds of information about a general shift, namely: language or set of forbidden words, and strengthen the observation by Simonsen (2006) that knowing the language of a shift is better than knowing only a set of forbidden words for the shift. Then we define the topological entropy. We observe that the obstacle to computing the topological entropy of a shift from its language is a topological one. Then we state the main result of the paper. We finish the section by considering the inverse question: if the topological entropy of a shift is computable, does this imply that the language is decidable, at least if the complement of the language is known to be c.e.? We show that this is not the case. On the contrary, we show that there exist shifts with topological entropy zero whose language is of any desired degree of computability-theoretic complexity. In the penultimate section, we prove the main result. We conclude with a summary and some open problems.

2 Shifts, Sets of Forbidden Words, and Languages of Shifts

We write N = {0,1, 2, ...} for the set of natural numbers, i.e., of non-negative integers, [summation over (term)] = {0,1} for the binary alphabet, [summation over (term)]* for the set of all finite binary strings, λ for the empty string, [[summation over (term)].sup.n] for the set of all binary strings of length n, for any n [member of] [??]. A subset of [summation over (term)] * is called (binary) language. A subset of [summation over (term)] * or of N is called computably co-enumerable (co-c. e.) if its complement is computably enumerable (c. e.). Furthermore, we write [[summation over (term)].sup.w] := {p | p : [??] [right arrow] [summation over (term)]} for the set of all one-way infinite binary sequences, and [[summation over (term)].sup.[??]] {p | p : Z [right arrow] [summation over (term)]} for the set of all bi-infinite binary sequences. For p [member of] [[summation over (term)].sup.[??]] and n [member of] [??], we write p[n] for the value of p on input n, and p[m ... n] := p[m] ... p [n], if m [less than or equal to] n, and p [m ... n] := [lambda], if m > n. For w [member of] [summation over (term)] * we set w[[summation over (term)].sup.w] := {p [member of] [[summation over (term)].sup.w] | w is a prefix of p} and denote by |w| the length of w. A string w [member of] [summation over (term)] * is a substring of some p [member of] [[summation over (term)].sup.[??]] if there is an n [member of] [??] with w = p[n + 1 ... n + |w|]. For any sets X and Y, we write f :[[subset].bar] X [right arrow] Y for a function whose domain dom(f) is a subset of X and whose range is a subset of Y. In case dom(f) = X we may write f : X [right arrow] Y. Endowed with the product topology of the discrete topology on [summation over (term)], both [[summation over (term)].sup.w] and [[summation over (term)].sup.[??]] are compact topological spaces. The function [sigma]: [[summation over (term)].sup.[??]][right arrow] [[summation over (term)].sup.[??]] defined by

[sigma](p)[n] := p[n+1] for p [member of] [[summation over (term)].sup.[??]] and n [member of] [??]

is called the shift map. It is a homeomorphism.

Definition 1 We call a subset X [[subset].bar] E [right arrow] [[summation over (term)].sup.[??]] a shift or a shift space or a subshift of [[summation over (term)].sup.[??]] if it is closed and satisfies [sigma](X) = X.

Examples of shift spaces are easily obtained.

Lemma 2 For an arbitrary set F [[subset].bar] [summation over (term)] * the set [X.sub.F] [[subset].bar] [[summation over (term)].sup.[??]] defined by

[X.sub.F] := {p [member of] [[summation over (term)].sup.[??]] | no string in F is a substring of p}

is a shift space.

Proof: See (Lind and Marcus, 1995, Definition 1.2.1 and Theorem 6.1.21).

Definition 3 If F [[subset].bar] [summation over (term)] * is a set with X = [X.sub.F], then F is called a set of forbidden words for X.

This poses the question whether every shift space can be defined via a set of forbidden words, i.e., whether for every shift space X there is a set F with X = [X.sub.F]. The answer is yes, as can be seen via the "language" of the shift space.

Definition 4 For any set X [[subset].bar] [[summation over (term)].sup.[??]] the set

L(X) := {w [member of] [summation over (term)] * | w is a substring of some p [member of] X}

is the language of X.

For any shift space X, the complement L[(X).sup.c] of L(X) is a set of forbidden words for X, i.e., X = [X.sub.L[(X).sup.c]] (indeed, X [[subset].bar] [X.sub.L[(X).sup.c]] is clear, and [X.sub.L[(X).sup.c]] [[subset].bar] X follows from the assumption that X is closed). In fact, it is the largest forbidden set of words for X since any other set of forbidden words for X is obviously a subset of L[(X).sup.c].

Example 5 For the shift space X := {[0.sup.[??]} containing only the bi-infinite sequence containing only 0's, one sees G(X) = {0}*, hence, L[(X).sup.c] = {0,1} * \ {0} *. Any set F with {1} [[subset].bar] F [[subset].bar] {0,1} * \ {0} * is a set of forbidden words for X. Also the sets {10,11} and {01,11} and so on are sets of forbidden words for X.

A particularly simple class of shifts are those that possess a finite set of forbidden words. But in general, a shift does not need to have a finite set of forbidden words. So, if one wishes to compute something associated with a shift, e.g., its entropy, one needs some kind of description of the shift as input for the algorithm. What is a natural description of a general shift X? One might assume that one knows the characteristic sequence of either a set of forbidden words for X or of L (X). Here the characteristic sequence Xs of a set S [[subset].bar] [summation over (term)] * is the binary sequence [[chi].sub.S] [member of] [[summation over (term)].sup.w] defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the bijection v : [??][right arrow] [summation over (term)] * is defined by the length-lexicographical ordering: order all strings in [summation over (term)] * according to their length (short strings first), and strings of the same length in alphabetical order.

We have just seen that, given the language of a shift, one can easily compute a set of forbidden words for the shift: just take the complement of the language of the shift. But (Simonsen, 2006, Remark 17) showed that there is no Turing machine which, given a decision algorithm for some decidable set F [[subset].bar] [summation over (term)] *, computes a decision algorithm for the language L([X.sub.F]). The argument used by Simonsen in order to prove this statement is actually a topological one: the function mapping the characteristic sequence of an arbitrary forbidden set of a shift to the characteristic sequence of its language is not continuous and can therefore not be computable. Note that any function H : [[subset].bar] [[summation over (term)].sup.w] [right arrow] [[summation over (term)].sup.w] that can be computed by a (Type-2) Turing machine is continuous; see, e.g., Weihrauch (2000).

Proposition 6 The function G : [[summation over (term)].sup.w] [right arrow] [[summation over (term)].sup.w], defined by G([[chi].sub.F]) := [[chi].sub.L]([X.sub.F])] is not continuous.

Proof: A point of discontinuity is for example the sequence [0.sup.w] = [chi]0. Note that G([0.sup.w]) = [1.sup.w] because L([X.sub.0]) = L([[summation over (term)].sup.[??]]) is the whole set [summation over (term)] *. If G were continuous in [0.sup.W], there should be a finite prefix [0.sup.n] of [0.sup.W] such that G([0.sup.W][[summation over (term)].sup.w]). But if F is the set of all binary strings of length greater than [log.sub.2](n) then [[chi].sub.F] also starts with [0.sup.n], but [X.sub.F] = 0, hence L(X) = 0, hence [[chi].sub.L(X)] = [0.sup.w].

We will strengthen Simonsen's remark (Simonsen, 2006, Remark 17) in the following way: in Corollary 11 we will see that there exists a decidable set F such that L([X.sub.F]) is not decidable. That means that there exists computable input for the function G in Proposition 6 which is mapped by this function to non-computable output. Note that any computable function H : [[subset].bar] [[summation over (term)].sup.w] [right arrow] [[summation over (term)].sup.w] maps any computable binary sequence p [member of] dom H to a computable binary sequence; see, e.g., Weihrauch (2000). Before we construct such a computable input, let us clarify what one can compute when one knows (an oracle for) some set F, i.e., if [[chi].sub.F] for some set F is given. We will see that one can still enumerate L([[X.sub.F].sup.c]). In fact in order to be able to do that, it is sufficient to be able to enumerate F. We formulate only a non-uniform (not involving oracle Turing machines) version of this statement.

Proposition 7 If F [[subset].bar] [summation over (term)] * is a computably enumerable set, then L[([X.sub.F]).sup.c]) is computably enumerable as well.

Proof: If a set F is computably enumerable, then also the set of all strings in [summation over (term)] * that have a substring in F is computably enumerable. The assertion follows now from the following lemma.

Lemma 8 Fix some set F [[subset].bar] [summation over (term)] *. A string v is in L[([X.sub.F]).sup.c] if, and only if, there exists some n [member of] [??] such that each of the [2.sup.2n] strings uvw with u, w [member of] [[summation over (term)].sup.n] has a substring in F.

Proof: For a string v we set [K.sub.v] := {p [member of] [[summation over (term)].sup.[??]] | v = p[0 ... |v| - 1]}. A string v is in L[([X.sub.F]).sup.c] if, and only if, every p [member of] [K.sub.v], contains an element of F as a substring. And this is the case if, and only if, for any p [member of] [K.sub.v], there is some n [member of] N such that p[-n ... |v| -1 + n] contains an element of F as a substring. Now, the claim follows easily from the compactness of the set [K.sub.v], for any v.

Especially, if a shift X has a decidable set of forbidden words, then L[(X).sup.c] must be a c.e. set. The converse is true as well.

Theorem 9 If X is a shift such that L[(X).sup.c] is c.e., then there exists a polynomial time decidable set F [[subset].bar] [summation over (term)] * with X = [X.sub.F].

Proof: This is proved by a padding argument. Let X be a shift such that L[(X).sup.c] is computably enumerable. Let M be a Turing machine that halts on input v [member of] [summation over (term)] after finitely many steps if, and only if, v [member of] L[(X).sup.c]. Let h: [[subset].bar] [summation over (term)]* [right arrow] [??] be defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We define a set F [[subset].bar] [summation over (term)] * as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We claim that this set F has the desired properties.

"X = [X.sub.F]": This is clear.

"F is decidable in polynomial time": A Turing machine that decides for a given string x [member of] [summation over (term)] * in time polynomial in [absolute value of x] whether x belongs to F or not can work for example as follows. For every prefix v of x it starts M with input v, lets M run for at most [absolute value of x] - |v| + 1 steps and accepts x if, and only if, there is a prefix v of x such that M stops on input v after exactly [absolute value of x] - |v| steps.

Corollary 10 For a shift X the following conditions are equivalent:

1. L[(X).sup.c] is computably enumerable.

2. X has a c.e. set of forbidden words.

3. X has a polynomial time decidable set of forbidden words.

Proof: "3 [??] 2": This is trivial. "2 [??] 1": This is Proposition 7. "1 [??] 3": This is Theorem 9.

Now we easily conclude that there is computable input for the function G in Proposition 6 which is mapped by G to non-computable output.

Corollary 11 There exists a polynomial time decidable set F [[subset].bar] [summation over (term)] * such that L([X.sub.F]) is not decidable.

Proof: In order to derive this from Theorem 9 it is sufficient to observe that there exist shifts whose language is co-c.e., but not decidable. For an infinite set S [[subset].bar] N, define

F(S) := {[10.sup.n]1|n [member of] [??]\S}

Fix some co-c.e., but not decidable set S [[subset].bar] N (such a set must be infinite). Then [??] \ S and F(S) are c.e. and not decidable. By Proposition 7 also L[([X.sub.F(S)]).sup.c] is computably enumerable. But L[([X.sub.F(S)]).sup.c] is not decidable because a string of the form [10.sup.n] 1 is in L[([X.sub.F(S)]).sup.c] if, and only if, n [member of] [??] \ S.

Remark 12 For an infinite set S [[subset].bar] [??], the shift [X.sub.F(S)] defined in the proof is called S-gap shift (Lind and Marcus, 1995, Example 1.2.6). For a finite, nonempty set S [[subset].bar] [??], the shift [X.sub.F(S)] is called S-gap shift where

F(S):= {[10.sup.n]1|n [member of] [??] \ S} [union] {[0.sup.1+max(S)]};

see (Lind and Marcus, 1995, Example 1.2.6).

Corollary 11 strengthens Simonsen's observation (Simonsen, 2006, Remark 17) that there can be no Turing machine which, given a decision algorithm for any decidable set F [[subset].bar] [summation over (term)] *, computes a decision algorithm for L([X.sub.F]).

3 The Entropy of Shifts with Decidable or with Computably Co-Enumerable Language

The following statement is Proposition 4.1.8 in Lind and Marcus (1995).

Proposition 13 If X is a shift, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

exists, and equals

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Here we use [log.sub.2](0) := -[infinity]

Definition 14 For a shift X, the value [h.sub.top](X) := [lim.sub.n[right arrow][infinity]] [log.sub.2]|L(X)[intersection] [[summation over (term)].sup.n]|/n is called the (topological) entropy of X.

The entropy of the empty shift is -[infinity]. In the rest of the paper we will only consider nonempty shifts. It is clear that the entropy of a nonempty subshift of [{0,1}.sup.[??]] is always a real number between 0 and 1, i.e., a real number in the closed interval [0,1]. The converse is true as well; one can even restrict oneself to irreducible shifts.

Definition 15 A shift X is called irreducible if for any two strings u, w [member of] L(X) there is a string v [member of] [summation over (term)] * with uvw [member of] L(X).

The irreducible shifts form an important subclass of shifts; compare Lind and Marcus (1995).

Proposition 16 1. The entropy of a nonempty shift is a real number in the interval [0,1].

2. Any real number in [0,1] is the entropy of a nonempty, irreducible shift.

Proof: The first assertion is clear. The second assertion follows immediately from (Lind and Marcus, 1995, Exercise 4.3.7(d)) where it is stated that every real number in [0,1] is the entropy of an S-gap shift, as defined in Remark 12, following (Lind and Marcus, 1995, Example 1.2.6). It is clear that any S-gap shift is irreducible.

A different proof of the second statement will be given in the following section. In fact, the proof of our main result (see below) will show how, given a non-increasing sequence of rational numbers in [0,1], one can construct an irreducible shift whose entropy equals the limit of this sequence.

Can one compute the entropy of a shift? What kind of information does one need to have about the shift in order to compute its entropy? By (Spandl, 2007, Theorem 6.3) one can effectively approximate the entropy from the right if one has an enumeration of L[(X).sup.c]. We state a non-uniform version of this precisely. Therefore, we need the notion of a right-computable real number. We directly define also the (more basic) notion of a computable real number.

Definition 17 1. A sequence [([q.sub.n]).sub.n[member of][??] if EN of rational numbers is computable if there exist three total computable functions s, a, b : [??] [right arrow] [??] with b(n) [not equal to] 0 and [q.sub.n] = [(-1).sup.s(n)] * a(n)/b(n), for all n.

2. A real number x is computable if there exists a computable sequence [([q.sub.n]).sub.n[member of][??] of rational numbers with |x - [q.sub.n]|[less than or equal to] [2.sup.-n], for all n [member of] [??].

3. A real number x is right-computable if there exists a computable sequence [([q.sub.n]).sub.n[member of][??] of rational numbers with [q.sub.n] [greater than or equal to] [q.sub.n+1] for all n [member of] [??] (a sequence satisfying this condition will be called non-increasing) and x = [lim.sub.n[right arrow][infinity]][q.sub.n].

Remark 18 Similarly, a real number is called left-computable if it is the limit of a computable non-decreasing sequence of rational numbers. Obviously, a real number x is right-computable if, and only if, -x is left-computable. And a real number is computable if, and only if, it is left-computable and right-computable. But it is well known that the class of left-computable real numbers is strictly larger than the class of computable real numbers; the same applies to the class of right-computable real numbers. If, e.g., K [[subset].bar] [??] is a c.e., but undecidable set, then the number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a right-computable but not computable real number between 0 and 1; see, e.g., Weihrauch (2000). For an overview concerning left-computable real numbers and other classes of real numbers defined by computability properties, see Zheng (2002).

Proposition 19 If X is a nonempty shift such that L[(X).sup.c] is c.e., then the entropy of X is a right-computable real number.

Proof: This follows from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (Proposition 13). It is also a direct consequence of (Spandl, 2007, Theorem 6.3).

Corollary 20 If a nonempty shift X has a c. e. set of forbidden words, then its entropy is a right-computable real number.

Proof: By the previous proposition and Proposition 7.

Of course, one would like not only to approximate the entropy from the right, but to compute it with any precision.

Simonsen (2006) and the second author, Spandl (2007), have shown that the entropy is not uniformly computable with respect to the language of the shift. To be precise, Simonsen (2006) has shown that there is no Turing machine which, given a decision algorithm for the language of some shift with decidable language, is able to compute the entropy of the shift with arbitrary precision. In fact, Simonsen (2006) showed that this negative result is true even if one restricts oneself to the class of irreducible shifts. The second author, Spandl (2007), showed that there is no oracle Turing machine which, given the language of some shift via an oracle, is able to compute the entropy of the shift with arbitrary precision. In fact, as was noted by Spandl (2007) and by Simonsen (2006) as well, these negative statements are true for topological reasons, similarly as the negative statement of Proposition 6 in the previous section was true for topological reasons.

Proposition 21 The function H : [[subset].bar] [[summation over (term)].sup.w] [right arrow] [??] with

dom H = {[[chi].sub.L(X)] | X is a nonempty, irreducible shift}, H([[chi].sub.L(X)]) = [h.sub.top](X) for any such shift X.

is discontinuous. It is even discontinuous if on [??] the weaker topology is considered whose open sets are the sets (a, [infinity]), with a [member of] [??], and the sets 0, [??].

The proof will be given in the following section. The proposition says essentially that there is no algorithm, in fact not even a continuous function, which, given the characteristic function of the language of a shift, would deliver arbitrarily good lower bounds to the entropy of the shift.

Simonsen (Simonsen, 2006, Page 94) then asked the question whether there exists a shift with decidable language but non-computable entropy. We shall show that this is indeed the case. Note that this strengthens the negative results by Simonsen (2006) and Spandl (2007) about the noncomputability of the entropy when the language of a shift is known. In fact, we shall show more. We have already seen that the entropy of any nonempty shift X with decidable language (even with co-c.e. language) is a right-computable real number between 0 and 1. We shall show that any such number is the entropy of a shift with decidable language. It is even the entropy of an irreducible shift with a polynomial time decidable language. The following theorem is the main result of this paper.

Theorem 22 For every right-computable real number a [member of] [0,1] there exists a nonempty, irreducible shift X with [h.sub.top](X) = [alpha] and with polynomial time decidable language L(X).

The proof will be given in the following section.

Corollary 23 For a real number a the following conditions are equivalent.

1. [alpha] [member of] [0,1] and [alpha] is right-computable.

2. There exists a shift X with co-c.e. language L(X) and entropy [alpha].

3. There exists an irreducible shift X with polynomial time decidable language L(X) and entropy [alpha].

Proof: "3 [??] 2": Trivial. "2 [??] 1": By Proposition 19 and Proposition 16.1. "1 [??] 3": By Theorem 22.

Corollary 24 There exists an irreducible shift X with polynomial time decidable language L(X) such that its entropy [h.sub.top] (X) is not a computable real number.

Proof: In Remark 18 we already mentioned that there exist right-computable real numbers between 0 and 1 that are not computable.

Remark 25 Our main result, Theorem 22, can be considered as an effective version of Proposition 16.2. We will see that by simplifying the proof (by forgetting about effectivity properties) one obtains a second proof of Proposition 16.2.

One may now also ask the other way around whether it might not be possible to prove our main result by effectivizing the proof given above for Proposition 16.2, i.e., by effectivizing the statement of (Lind and Marcus, 1995, Exercise 4.3.7(d)) that any real number in [0,1] is the entropy of an S-gap shift (compare Remark 12). Thus, the question arises whether for an arbitrary right-computable real number a [member of] [0,1] there is an S-gap shift with entropy [alpha] and decidable language. The answer to this question is no, as was observed already by the second author in (Spandl, 2007, Section 7): for a nonempry set S [[subset].bar] N, the language of the S-gap shift [X.sub.F(S)] is decidable if, and only if, S is decidable, and in that case the entropy [h.sub.top] ([X.sub.F(S)]) is a computable real number.

We have seen that decidability of the language of a shift implies right-computability of the entropy, but not computability of the entropy. One might ask also the inverse question: does computability of the entropy of a shift imply any computability property of the language of the shift, e.g., that is is decidable, perhaps at least if the language is already known to be co-c.e.? The next result shows that this is not the case. In order to formulate it we remind the reader of some notions from computability theory. A language L [subset or equal to] [summation over (term)] * is many-one reducible to a set S [member of] [??] if there is a total computable function h : [summation over (term)] * [right arrow] [??] with x [member of] L [??] h(x) [member of] S, for any x [member of] [summation over (term)] *. Conversely, a set S [subset or equal to] [??] is many-one reducible to L [subset or equal to] [summation over (term)] * if there is a total computable function g : [??] [right arrow] [summation over (term)] * with x [member of] S [??] g(x) [member of] L, for any x [member of] N. Finally, L [subset or equal to] [summation over (term)] * and S [subset or equal to] N are called many-one equivalent to each other if L is many-one reducible to S and S is many-one reducible to L. If two sets are many-one equivalent to each other then they have the same computability-theoretic degree of difficulty. For example, if one of them is decidable resp. c.e. resp. co-c.e., then the other one has the same property.

Theorem 26 For any set S [subset or equal to] [??] with S [not equal to] 0 and S [not equal to] [??] there exists a shift over the binary alphabet whose topological entropy is equal to zero and whose language is many-one equivalent to S.

Proof: For s [member of] [??] we define

[X.sub.per](s) := {c [member of] [{0,1}.sub.[??]] | c contains infinitely many 1's, and, for any k [member of] [??], the string [10.sup.k]1 is a substring of c if, and only if, k = s}.

In other words, [X.sub.per](s) contains exactly the s + 1 bi-infinite binary periodic sequences of the form

... [10.sup.s][10.sup.s][10.sup.s]1....

For finite S [subset or equal to] [??] with S [not equal to] 0, we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and for infinite S [subset or equal to] [??], we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us fix a set S [subset or equal to] [??] with S [not equal to] 0.

First, we show that [X.sub.per](S) is a shift space. The set [X.sub.per](S) is obviously invariant under the shift map [sigma], i.e., [sigma]( [X.sub.per](S)) = [X.sub.per](S). Furthermore, it is closed. In the case of infinite S, we ensured that [X.sub.per](S) is closed by adding the sequence [0.sup.[??]] and the sequences in [[summation over (term)].sup.[??]] containing exactly one 1.

Now, we show that [h.sub.top]([X.sub.per](S)) = 0. Since [X.sub.per](S) is nonempty and a subset of [X.sub.per]([??]), it is sufficient to show that [h.sub.top]([X.sub.per]([??])) = 0. Consider some n > 0. Let us give an upper bound on the number of strings in L([X.sub.per]([??])) [intersection] [[summation over (term)].sup.n]. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and, for any s [member of] N,

|L([X.sub.per](s))[intersection] [[summation over (term)].sup.n]|[less than or equal to] s+1,

thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the rest of the proof we assume not only S [not equal to] 0, but also S [not equal to] [??]. We still have to show that L([X.sub.per](S)) is many-one equivalent to S. The set S is many-one reducible to L([X.sub.per](S)) because, for S [member of] N,

s [member of] S [??] [10.sup.s]1 [member of] L([X.sub.per](S)).

For the inverse claim (that L([X.sub.per](S)) is many-one reducible to S) we distinguish two cases.

1. S is finite. Then L([X.sub.per](S)) is obviously decidable. Thus, both sets are decidable. Since furthermore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] they are many-one equivalent.

2. S is infinite. Then L([X.sub.per](S)) contains all strings that contain at most one 1. And a string w with two or more 1's is in L([X.sub.per](S)) if, and only if, it satisfies the following two conditions:

(A) w contains at least two 1's, and there is some s [less than or equal to] |w| such that w is a substring of the periodic bi-infinite sequence

... [10.sup.s][10.sup.s][10.sup.s]1 ...,

(B) this number s (if is exists, it is obviously uniquely determined) is an element of S.

Condition (A) can be checked directly, and Condition (B) can be checked by a many-one reduction to S. To complete the proof formally, we define a computable reduction function [h.sub.L([X.sub.per](S)),S] [summation over (term)] * [right arrow] [??] from L([X.sub.per](S)) to S. Fix some [s.sub.yes] [member of] S and some [s.sub.no] [not member of] S (remember our assumptions S [not equal to] 0 and S [not equal to] N). We define

[h.sub.L]([X.sub.per](S)),[S.sup.(w)] :=

[s.sub.yes] if w contains at most one 1, [s.sub.no] if w contains at least two 1's, but does not satisfy Condition (A), s if w satisfies Condition (A), and s is the number of 0's between any two 1's in w between which there is no other 1.

It is clear that this function is computable and reduces L([X.sub.per](S)) to S.

We have shown that [X.sub.per](S) has all the desired properties.

Corollary 27 There exists a shift over the binary alphabet whose entropy is zero and whose language is co-c.e., but not decidable.

Proof: By taking for S in Theorem 26 any co-c.e., but undecidable set, one obtains such a shift.

4 Proofs

In this section, we prove Proposition 21 and Theorem 22. In addition, we give a new proof of Proposition 16.2. Certain sofic shifts (compare Lind and Marcus (1995)) will play an important role.

Definition 28 1. A finite [summation over (term)]-labeled graph is a pair (V, E) consisting of a finite set V (the set of nodes) and a finite set E [subset or equal to] V x V x [summation over (term)] (the set of edges labeled with elements of[summation over (term)]).

2. For a finite [summation over (term)]-labeled graph (V, E), we define three functions start : E [right arrow] V, end: E [right arrow] V, and label : E [right arrow] [summation over (term)] giving the three components of a labeled edge as follows:

e = (start(e), end(e), label(e)),

for any e [member of] E.

3. A bi-infinite path through a finite E-labeled graph (V, E) is a function q : [??] [right arrow] E such that end (q(i)) = start(q(i + 1)), for all i [member of] [??].

Lemma 29 If (V, E) is a finite E-labeled graph, then the following set is a shift and called the sofic shift defined by the graph: {p [member of] [[summation over (term)].sup.[??]] | there exists a bi-infinite path q : [??] [right arrow] E through the graph such that p[i] = label(q(i)), for all i [member of] [??]}.

For the proof see (Lind and Marcus, 1995, Section 3.1).

By [{0, *}.sup.+] we denote the set of all nonempty strings over the alphabet {0, *}.

[FIGURE 1 OMITTED]

Definition 30 For any w [member of] [{0, *}.sup.+], let X (w) be the sofic shift defined by the graph defined as follows. The graph has |w| nodes [v.sub.0], ... , [v.sub.|w|]-1. For each i [member of] {0, ... , |w| - 1}, it has an edge labeled with 0 from [v.sub.i] to [v.sub.i+1 mod |w|]. Additionally, for i [member of] {0, ... , |w| - 1}, it has an edge labeled with 1 from [v.sub.i] to [v.sub.i+1 mod |w|] if, and only if, w[i] = * (where w = w[0]w[1] ... w[|w| - 1]).

Example 31 The graph of X (w) for w = 00 * 0 * * 00 is depicted in Figure 1.

The shift X (w) can be described as follows: its elements are exactly all bi-infinite binary sequences of the form ... [v.sub.-2][v.sub.-1][v.sub.0][v.sub.1][v.sub.2] ... where, for every i [member of] [??], [v.sub.i] is a binary string of length |w| that matches w in the following sense: at every position where [v.sub.i] has a 1, w must have a *. It is equivalent to say that [v.sub.i] can be obtained from w by replacing every * in w either by a 0 or a 1. In the following we will call any element of {0, *}* a pattern. In the next lemma we collect several useful properties of the shifts X (w).

Lemma 32 1. For any w [member of] [{0, *}.sup.+], [0.sup.[??]] [member of] X (w). Hence, X (w) is nonempty.

2. For any w [member of] [{0, *}.sup.+], X (w) is irreducible.

3. For any w [member of] [{0, *}.sup.+], [h.sub.top] (X(w)) = # * (w)/|w| (where #*(w) is the number of *'s in w).

4. For any w [member of] [{0, *}.sup.+] and any integer k [greater than or equal to]1, X ([w.sup.k]) = X (w).

5. For any v, w [member of] [{0, *}.sup.+], if |v| = |w| and if v can be obtained from w by replacing some *'s in w by 0's, then X (v) [subset or equal to] X (w).

6. For any w [member of] [{0, *}.sup.+], any integers a, b with a [greater than or equal to] 2 and b [greater than or equal to] 0, and any v [member of] [summation over (term)]* with |v| [less than or equal to] |w|, one has v [member of] L (X(w)) [??] v [member of] L(X([w.sup.a][0.sup.|w|*b]).

Proof:

1. Clear.

2. Clear.

3. Left to the reader (compare, e.g., Lemma 20 and Theorem 21 in Simonsen (2006)).

4. Clear.

5. Clear.

6. Since by Statements 4 and 5 of this lemma, the set L(X([w.sup.a][0.sup.|w|*b]) is a subset of L(X(w)), the direction from right to left is clear. For the other direction, assume that v [member of] L(X(w)) and |v|[less than or equal to] |w|. Then v matches a subpattern of ww. Since a [greater than or equal to] 2, we obtain v [member of] L(X([w.sup.a][0.sup.|w|*b]).

Proof of Proposition 21: The function H defined in Proposition 21 is discontinuous for example in [1.sup.w], even with respect to the weaker topology on R, mentioned in Proposition 21. Note that [1.sup.w] = [chi] [summation over (term)]* = [[chi].sub.L] ([[summation over (term)].sup.[??]]), and that the full shift [[summation over (term)].sup.[??]] = X(*) has entropy 1 and is irreducible. If H were continuous in [1.sup.w] with respect to the weaker topology on [??], then there would be a finite prefix [1.sup.n] of [1.sup.w] with n [greater than or equal to] 2 such that the entropy of any shift X with the property that [[chi].sub.L](X) starts with [1.sup.n] would be strictly larger than 1/2. In that case, we set l := [log.sub.2](n)], and observe that by Lemma 32.3 the shift X ([*.sup.l][0.sup.l]) has entropy 1/2, but, obviously, all strings of length [less than or equal to] l are in the language of this shift, hence, the characteristic sequence of its language starts with [1.sup.n] as well.

Before we come to the proof of Theorem 22, we need some more preparations. We had defined right-computable real numbers as the limits of computable, non-increasing sequences of rational numbers. In fact, one can restrict oneself to dyadic rational numbers, and one can ask that the sequence can be computed quite fast. A sequence [([z.sub.n]).sub.n [member of][??]] of natural numbers is computable in time polynomial in n if there is a Turing machine which, given a binary name of some n [member of] [??], computes a binary name of [z.sub.n] in time bounded by a polynomial in n.

Lemma 33 A real number [alpha] [member of] [0,1] is right-computable if, and only if, there is a sequence [([z.sub.n]).sub.[member of][??]] of natural numbers computable in time polynomial in n such that [z.sub.n] [member of] {1, ... , [2.sup.n]}, for all n, and such that the sequence [([z.sub.n] /[2.sup.n]).sub.n [member of][??]] is non-increasing and converges to [alpha].

For reasons which will become clear in the proof of Theorem 22, we do not allow [z.sub.n] = 0.

Proof: The direction from right to left is clear: for a sequence [([z.sub.n]).sub.n[member of][??]] with the properties formulated in Lemma 33 the limit [lim.sub.n[right arrow][infinity]] [z.sub.n]/[2.sup.n] is a right-computable real number in [0,1].

We come to the direction from left to right. Let [alpha] [member of] [0,1] be right-computable. Let us assume that a computable, non-increasing sequence ([q.sub.n]).sub.n[member of][??] of rational numbers with [lim.sub.n[right arrow][infinity]][q.sub.n] = [alpha] is known. The sequence ([y.sub.n]).sub.n[member of][??] defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a computable sequence of integers [y.sub.n] [member of] {1, ... , [2.sup.n]} such that the sequence ([y.sub.n]/ [2.sup.n]).sub.n[member of][??] is non-increasing and converges to [alpha]. The only problem why we cannot take [y.sub.n] for [z.sub.n] is that the sequence ([y.sub.n]).sub.n[member of][??] might not be computable in time polynomial in n. Let M be a Turing machine which, without ever stopping, writes the one-way infinite sequence

bin([y.sub.0])#bin([y.sub.1])#bin([y.sub.2])# ...

onto a one-way output tape, where, for an integer x, we denote its binary name by bin(x). We define the desired sequence ([z.sub.n]).sub.n[member of][??] as follows.

For [z.sub.n], perform the first n steps of the computation of M. Let m be the number of #'s written by M during these steps. In case m = 0, define [z.sub.n] := [2.sup.n]. In case m > 0, define [z.sub.n] := [y.sub.m-1]x[2.sup.n+1-m].

Note that [y.sub.0] = 1 and that for any x, l [member of] N with x > 0 it is clear that bin(x * [2.sup.l]) = bin(x)[0.sup.l]. It is clear that the sequence [([z.sub.n]).sub.n [member of][??]] is computable in time polynomial in n. Furthermore, [([z.sub.n]) [member of] E {1, ... , [2.sup.n]} for all n, and the sequence [([z.sub.n]).sub.n [member of][??]] is non-increasing and converges to [alpha].

The strategy of the proof of Theorem 22 is to consider a computable sequence of integers [([z.sub.n]).sub.n [member of][??]] as in the previous lemma and to construct a decreasing sequence of (sofic) shifts [x.sub.n] with entropy equal to [z.sub.n]/[2.sup.n]. Then the desired shift X will be defined as the limit of the shifts [X.sub.n], as in the following lemma.

Lemma 34 Let [([X.sub.n]).sub.n [member of][??]] be a sequence of nonempty subshifts of [[summation over (term)].sup.[??]] with [X.sub.n+1] [member of] [X.sub.n] for all n. Set X := [intersection].sub.n [member of][??]][X.sub.n]. Then

1. X is a nonempty subshift of [[summation over (term)].sup.[??]] as well,

2. L(X) = [intersection].sub.n [member of][??]]L([X.sub.n]),

3. [h.sub.top](X) = [lim.sub.n[right arrow][infinity]][h.sub.top]([X.sub.n]).

Proof: The first statement, that X is a subshift of [[summation over (term)].sup.[??]], is shown once we have shown that X is nonempty and closed and that [sigma] (X) = X.

"X is nonempty": Consider an arbitrary sequence ([x.sub.n]).sub.n[member of][??]] of elements [x.sub.n] [member of] [X.sub.n], for each n. Since [[summation over (term)].sup.[??]] is compact, this sequence has an accumulation point in [[summation over (term)].sup.[??]]. Let us call it x. Since for all n [member of] [??] and all m [greater than or equal to] n we have [x.sub.m] [member of] [X.sub.m] [subset or equal to] [X.sub.n], we conclude that x is contained in the closure of [X.sub.n] for all n, hence in [X.sub.n] itself for all n, hence x [member of] X. Thus, X is nonempty.

"X is closed": For every n, [X.sub.n] is closed, and the intersection of arbitrarily many closed sets is closed again.

"[sigma](X) [subset or equal to] X": From [sigma], [X.sub.n] [subset or equal to] [X.sub.n] for all n we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

"[sigma](X) [contains or equal to] X": Let us fix some y [member of] X. We have to show that there is some x [member of] X with [sigma]([x.sub.n]) = y.

Since y [member of][X.sub.n] and [sigma]([X.sub.n])[contains or equal to] [X.sub.n], for all n, for every n [member of] [??] there is some [x.sub.n] [member of] [X.sub.n] with [sigma]([x.sub.n]) = y. As in the proof of "X is nonempty" we can conclude that the sequence ([x.sub.n]).sub.n [member of][??]] has an accumulation point x, and that x is an element of X. The sequence ([x.sub.n]).sub.n [member of][??]] has a subsequence that converges to x. Since [sigma]([x.sub.n]) = y for all n and since [sigma], is continuous, we conclude that [sigma](x) = y.

"L(X) [subset or equal to] [intersection].sub.n [member of][??]]L([X.sub.n])": For any subshifts Y, Z of [[summation over (term)].sup.[??]] with Y [[subset].bar] Z one has L(Y) [subset or equal to] L(Z). The assertion follows.

"L(X) [contains or equal to] [intersection].sub.n [member of][??]]L([X.sub.n])": Let us fix some w [member of] [intersection].sub.n [member of][??]]L([X.sub.n]). For every n [member of] [??] there is some [x.sub.n] [member of] [X.sub.n] such that [x.sub.n] [0 ... |w| - 1] = w. As in the proof of "X is nonempty" we can conclude that the sequence ([x.sub.n]).sub.n [member of][??]] has an accumulation point x, and that x is an element of X. It is also clear that x [0, ... , |w|-1] = w. This implies w [member of] L(X).

"[h.sub.top] (X) = [lim.sub.n[right arrow][infinity]][h.sub.top]([X.sub.n])": Since for any subshifts Y, Z of [[summation over (term)].sup.[??]] with Y [subset or equal to] Z one has [h.sub.top] (Y) [less than or equal to] [h.sub.top] (Z), the sequence [h.sub.top] ([X.sub.n]) is non-increasing. Since it is bounded from below by 0, the limit [lim.sub.n[right arrow][infinity]][h.sub.top]([X.sub.n]) exists. Furthermore, [h.sub.top] (X) [less than or equal to] [h.sub.top] ([X.sub.n]), for all n, follows as well, hence [h.sub.top] (X) [less than or equal to] [lim.sub.n[right arrow][infinity]][h.sub.top]([X.sub.n]). We still have to show that [h.sub.top] (X) cannot be strictly smaller than [lim.sub.n[right arrow][infinity]][h.sub.top]([X.sub.n]). In order to show this, let us fix some [epsilon] > 0. We show that [h.sub.top] ([X.sub.n]) [is less than or equal to] [h.sub.top] (X) + [epsilon] for almost all n. Remember that for an arbitrary subshift Y of [[summation over (term)].sup.[??]],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, there exists some k [greater than or equal to] 1 with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Above we have seen [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Especially, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since the sets L([X.sub.n]) [intersection] [[summation over (term)].sup.k] are finite and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any m, n [member of] [??] with m [less than or equal to] n, we conclude that there is some l [member of] N such that for all n [greater than or equal to] l we have L([X.sub.n]) [intersection] [[summation over (term)].sup.k] = L(X) [intersection] [[summation over (term)].sup.k]. We conclude that for all n [greater than or equal to] l

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This ends the proof.

Proof of Theorem 22: Let a [member of] [0,1] be a right-computable real number. By Lemma 33 there exists a sequence [([z.sub.n]).sub.n [member of][??]] of integers computable in time polynomial in n with [z.sub.n] [member of] {1, ... , [2.sup.n]} such that the sequence ([q.sub.n]).sub.n [member of][??]] defined by [q.sub.n] := [z.sub.n]/[2.sup.n] is non-increasing and converges to [alpha]. We define a sequence ([w.sub.n]).sub.n [member of][??]] of patterns [w.sub.n] [member of] [{0, *}.sup.+] recursively by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that [z.sub.n] [not equal to] 0 for all n and that the assumption that the sequence ([q.sub.n]).sub.n[member of][??] is non-increasing implies that 4[z.sub.n] [greater than or equal to] 2[z.sub.n+1] for all n. We define a sequence ([X.sub.n]).sub.n[member of][??] of sofic shifts by

X.sub.n] := X([w.sub.n]).

By Lemma 32.1, [X.sub.n] is nonempty, for each n. Since [w.sub.n+1] can be obtained from [w.sup.4[z.sub.n].sub.n] by replacing some *'s in [w.sup.4[z.sub.n].sub.n] by 0's, Lemma 32.4 and 32.5 tell us that X([w.sub.n+1]) [subset or equal to] X ([w.sub.n]), for all n. We define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By Lemma 34.1, X is a nonempty subshift of [[summation over (term)].sup.[??]]. We claim that it has all desired properties.

"[h.sub.top] (X) = [alpha]": This is true by Lemma 34.3 because we have constructed [X.sub.n] so that [h.sub.top]( [X.sub.n]) = [q.sub.n] for all n. We show this by induction. For n = 0 it is true because [z.sub.0] = 1, hence [q.sub.0] = 1, and [X.sub.0] = X ([w.sub.0]) = X (*) = [[summation over (term)].sup.[??]] is the full shift, and the entropy of the full shift is equal to 1. For n + 1 we obtain by Lemma 32.3 and by the induction hypothesis

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, the subshift X has the desired entropy.

We still have to show that X is irreducible and that its language L(X) is decidable in polynomial time.

First, we observe that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all n, hence own [w.sub.n] > [4.sup.n] for all n.

Secondly, we claim that for any n [member of] [??] and any v [member of] [[summation over (term)].sup.[??]] with |v| [less than or equal to] |[w.sub.n]|

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Indeed, by Lemma 34.2 L(X) = [intersection].sub.m [member of][??]] L(X([w.sub.m])). Thus, the direction from right to left in (1) is clear. For the direction from left to right, fix some n [member of][??]] and some v [member of] L (X([w.sub.m])) with |v| [less than or equal to] |[w.sub.n]|. By Lemma 32.6, v [member of] L (X([[w.sub.n+1]])). Since |v| [less than or equal to] |[w.sub.n+1]|, we can repeat this argument and obtain v [member of] L(X([w.sub.n+2])), and so on. Thus, v [member of] L(X ([w.sub.m])) for all m > n. Since v [member of] L(X([w.sub.m])) for all m < n is clear anyway (due to L (X([w.sub.k])) [bar.[contains]] L (X ([w.sub.k+1])) for all k [member of] [??]), we obtain v [member of] L(X). This ends the proof of (1).

"X is irreducible": Assume that x, z [member of] [summation over (term)] * are two strings in L(X). Choose n large enough so that |[w.sub.n]| [greater than or equal to] max {[absolute value of x],|z|}. By Lemma 34.2, we observe x, z [member of] L(X ([w.sub.n])). This implies that x matches a subpattern of [w.sub.n][w.sub.n] in the sense explained above, i.e., in the sense that it can be obtained from a subpattern of [w.sub.n][w.sub.n] if the *'s in the subpattern are replaced appropriately by 0's or l's. The same as for x is true for z. But then, since [w.sub.n+1] contains [w.sub.n][w.sub.n] as a subpattern, there is a string y [member of] [summation over (term)] * such that xyz matches a subpattern of [w.sub.n+1][w.sub.n+1] in the same sense, and, hence, by the same argument, matches a subpattern of [w.sub.n+2]. By (1), this implies that xyz is an element of L(X). Hence, X is irreducible.

"L(X) is decidable in polynomial time": We claim that the following algorithm decides for an arbitrary input string v [member of] [summation over (term)]* whether v belongs to L(X) or not. Furthermore, the algorithm can be implemented on a Turing machine that works in time polynomial in |v|. In the algorithm we use a Turing machine M which, given a binary name of any n [member of] [??], computes in time polynomial in n the binary name of [z.sub.n].

Algorithm: Assume that some v [member of] [summation over (term)]* is the input.

First part: For i = 0, 1, 2, ... compute the binary name of [z.sub.i] (use M for this task) and the string [w.sub.i] until a number i has been found such that |[w.sub.i]| [greater than or equal to] |v|.

Second part: For this i, check whether v is an element of L(X([w.sub.i])) by checking whether v matches a subpattern of [w.sub.i][w.sub.i].

(End of the description of the algorithm)

Due to |[w.sub.n]| [greater than or equal to] [4.sup.n], the search in the first part of the algorithm will be successful, and by (1) it is clear that this algorithm decides whether v is an element of L(X) or not. We show now that the algorithm (when implemented properly on a Turing machine) works in time polynomial in |v|.

Let i be the smallest number i with |[w.sub.n]| [greater than or equal to] [v]. Since |[w.sub.n]| [greater than or equal to] [4.sup.n] for all n, we obtain i = 0 for |v| [less than or equal to] 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The computation of the numbers [z.sub.0], ... , [z.sub.i] in the first part of the algorithm can be done in time polynomial in i, hence, certainly in time polynomial in |v|. If, for some k < i, the string wk and the numbers [z.sub.k], [z.sub.k+1] are known, one can in time polynomial in the length of [w.sub.k+1] compute the string [w.sub.k+1]. Note that [w.sub.0] = *. Hence, if |v| [less than or equal to] 1, the algorithm will already stop with i = 0. Assume now that |v| > 1. Then |[w.sub.0]| = |*| = 1 < |v|, hence i [greater than or equal to] 1 and |[w.sub.n-1]| < |v|, hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This and |[w.sub.k]| < |[w.sub.i]| for k [less than or equal to] i imply that the strings [w.sub.0], ... , [w.sub.i] can be computed in time polynomial in |v| (in the first part of the algorithm). Thus, the first part of the algorithm works in time polynomial in |v|. The checking in the second part can be done in detail as follow: for each position in [w.sub.i][w.sub.i], one checks whether v matches the subpattern of [w.sub.i][w.sub.i] starting at this position with length |v| (of course, at the last |v| - 1 positions of [w.sub.i][w.sub.i] no subpattern of length |v| can start). For each position, this checking can be done in time linear in |v|. Since there are only 2 * |[w.sub.i]| positions, the second part takes only time polynomial in |v|. Thus, the whole algorithm works in time polynomial in |v|. This ends the proof of Theorem 22.

Proof of Proposition 16.2, 2nd variant: For any real number [alpha] [member of] [0,1] there exists a sequence [([z.sub.n]).sub.n [member of][??]] of numbers [z.sub.n] with [z.sub.n] [member of] {1, ... , [2.sup.n]}, for each n, such that the sequence ([z.sub.n]/[2.sup.n]).sub.n [member of][??]] is non-increasing and converges to [alpha]. By defining patterns [w.sub.n] and shifts X([w.sub.n]) and, finally, a shift X in exactly the same way as in the proof of Theorem 22, one obtains a nonempty, irreducible shift X with topological entropy [alpha].

5 Summary and Open Problems

We have answered positively the question by Simonsen (2006) whether there exists a shift with decidable language whose topological entropy is non-computable. In fact, the shift constructed by us is even irreducible and its language is polynomial time decidable. Simonsen (2006) also suggested to study the class of shifts with primitive recursive language, a subclass of the shifts with decidable language. Since any polynomial time language is primitive recursive, our result shows that restriction to shifts with primitive recursive language does not help with respect to the topological entropy: there are even shifts in this smaller class whose topological entropy is non-computable.

In the second paragraph of the introduction we mentioned several positive results concerning the computability of the entropy for certain types of shift spaces. But there is still a gap between those positive results and the negative result of this paper. It remains an interesting task to narrow this gap and to identify more known classes of shifts such that the entropy is computable for the shifts in the class.

On the other hand, we have also shown that computability of the entropy of a shift does not imply any kind of computability of the language of the shift. Especially, it does not imply that the language is decidable, not even if the language happens to be computably co-enumerable. Thus, in a computability theoretic sense the language of a shift and the entropy of the shift are not closely related: decidability of the language does not imply computability of the entropy, and computability of the entropy does not imply decidability of the language.

We have not only shown that there exist shifts with (polynomial time) decidable language and non-computable entropy. Actually, we have classified exactly the real numbers that can appear as the topological entropy of a subshift of the full shift of all binary bi-infinite sequences with co-c.e. resp. with decidable resp. with polynomial decidable language (the answer is in each case: exactly the right-computable real numbers between 0 and 1). Note that Hochman and Meyerovitch (2007) showed an analogous result for multi-dimensional shifts of finite type: they showed that the real numbers that are the entropy of a multi-dimensional shift of finite type are exactly the non-negative right-computable real numbers. It would be interesting to ask the same question for other types of dynamical systems, modifying slightly two questions raised by Koiran (2001): which real numbers can be the entropy of a one-dimensional cellular automaton (note that Hurd et al. (1992) have shown that there is no algorithm which, given a one-dimensional cellular automaton, computes its entropy with any desired precision) or of a piecewise affine map as studied by Koiran (2001)?

Acknowledgements

We thank one of the anonymous referee for informing us about the paper by Simonsen (2005) and the preprint by Hochman and Meyerovitch (2007).

References

P. Hertling and C. Spandl. Computability theoretic properties of the entropy of gap shifts. Fundamenta Informaticae, 83(1-2):141-157, 2008.

M. Hochman and T. Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. arXiv:math/0703206v1, March 2007.

L. Hurd, J. Kari, and K. Culik. The topological entropy of cellular automata is uncomputable. Ergodic Theory and Dynamical Systems, 12:255-265, 1992.

P. Koiran. The topological entropy of iterated piecewise affine maps is uncomputable. Discrete Mathematics and Theoretical Computer Science, 4(2):351-356,2001.

D. Lind and B. Marcus. Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, UK, 1995.

J. Milnor. Is entropy effectively computable? Remark, see http://www.math.sunysb.edu/~jack/compent.pdf, 2002.

J. G. Simonsen. On beta-shifts having arithmetical languages. In J. Jedrzejowicz and A. Szepietowski, editors, Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings, volume 3618 of Lecture Notes in Computer Science, pages 757-768. Springer, 2005.

J. G. Simonsen. On the computability of the topological entropy of subshifts. Discrete Mathematics and Theoretical Computer Science, 6:83-96, 2006.

C. Spandl. Computing the topological entropy of shifts. Mathematical Logic Quarterly, 53(4-5):493-510, 2007.

K. Weihrauch. Computable Analysis. Springer, Berlin, 2000.

X. Zheng. Recursive approximability of real numbers. Mathematical Logic Quarterly, 48(Suppl. 1): 131-156, 2002.

Peter Hertling([dagger]) and Christoph Spandl

Institut fur Theoretische Informatik and Mathematik, Fakultat fur Informatik, Universitat der Bundeswehr Munchen, 85577 Neubiberg, Germany

([dagger]) During the preparation of this work the first author was partially supported by DFG (grants no. HE 2489/4-1, 446 CHV 113/240/0-1), by NSFC (grant no. 10420130638), and by JSPS (grant no. 16340028).
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Hertling, Peter; Spandl, Christoph
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Formula
Geographic Code:1USA
Date:Nov 1, 2008
Words:10630
Previous Article:Extremal [K.sub.(s,t)]-free bipartite graphs.
Next Article:Multidimensional cellular automata and generalization of Fekete's lemma.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |