当前位置:首页 >> >>

Observability of Hybrid Systems and Turing Machines

43rd IEEE Conference on Decision and Control December 14-17, 2004 Atlantis, Paradise Island, Bahamas


Observability of Hybrid Systems and Turing Machines
Pieter Collins and Jan H. van Schuppen
Abstract— In this paper we discuss the observability of hybrid systems and Turing machines. We give an elementary example to show that observability is undecidable for Turing machines with output. Since many classes of system simulate Turing machines, we can then show that observability for these classes is undecidable. We discuss the observability of piecewise-af?ne hybrid systems, and give examples illustrating different observability properties.

I. INTRODUCTION In linear control theory, the basic system properties of stability, controllability and observability are straightforward to check. Beyond linear systems, a number of undecidability results for various classes of nonlinear systems exist. Most existing undecidability results concern the reachability relation, that is, given two points x0 and x1 , is there a system trajectory from x0 and x1 . For Turing machines [1], the reachability relation is known to be undecidable, since it is simply a reformulation of the halting problem. A twostack pushdown automaton can trivially simulate a Turing machine, and a two-counter machine also has equivalent computational power. A reversible Turing machine was shown to be computationally universal by Bennett [2], and a reversible two-counter machine was shown to be universal by Morita [3]. The reachability relation is undecidable for all these machines. As well as the halting problem, related problems are also undecidable, such as the mortality problem, under which a machine halts starting from any con?guration (state and input). The mortality problem for Turing machines with an in?nite input tape was shown to be undecidable by Hooper [4]. An elementary proof that the mortality problem for two-counter machines is undecidable was given by Blondel et al. [5]. The study of computability properties for continuousspace systems requires the reduction of problems either to a Turing machine, or to a model with similar computational power. Systems known to be able to simulate Turing machines include planar diffeomorphisms [6], planar piecewise-linear maps [7], piecewise-constant derivative systems [8] and high-dimensional saturated linear systems [9]. (It was shown that a saturated linear system with 866 variables can simulate a universal Turing machine.) In the literature, most attention has been directed towards the system properties of stability and controllability. Results for saturated linear systems were obtained by Siegelmann and Sontag [9], [10] and a number of additional results have been obtained by Blondel, Tsitsiklis et al. [11], [12].
Centrum voor Wiskunde en Informatica, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. Email:

In [10], distinguishability of a state from zero was related to reachability analysis, and hence shown to be undecidable. Existing work on observability has focused on systems with saturated outputs, which arise naturally in many applications including neural networks. Observability for continuoustime linear systems with saturated outputs holds if and only if the Kalman rank condition plus an additional property hold [13], but the computability of this property was not discussed. In this paper we study the observability problem for systems on a compact state space, with the evolution and output de?ned by continuous functions, since this is the case of most interest. We consider the cases that the set of possible initial states is either ?nite, or is the entire state space. We show that these observability problems are undecidable for the class of rational piecewise-af?ne systems. These systems are effective (i.e. the evolution of rational points can be exactly computed), have a hybridspace character (i.e. the system evolution law depends on the position in phase space), and include the saturated linear systems. Unlike the restricted case of saturated linear systems, we can show that the observability problem for general piecewise-af?ne systems is undecidable even in dimension two. The observability problem for a ?nite initial state set reduces to the halting problem by considering an appropriate observation function. When the initial state set is the entire state space, we reduce to the mortality problem. Since we consider systems on a compact state space de?ned by continuous maps, it is of crucial importance that we reduce to a class of machine with a compact con?guration space. This includes Turing machines with an in?nite input tape, but not Turing machines with a ?nite input or two-counter machines. We ?rst show that two appropriately-formulated observability problems for Turing machines are undecidable. Although we do not use these results directly in the sequel, they are of independent interest, and the proofs illustrate some of the techniques used when considering piecewiseaf?ne systems. Finally, we discuss the distinguishability time for two trajectories. For observable linear systems, all states can be distinguished in ?nite time. For observable hybrid systems, we may be able to distinguish two states in ?nite time, but may need to look at the trajectories on in?nite time intervals. A. Observability notions We consider observability for systems without inputs. De?nition 1 (Distinguishability and Observability): Two initial states x and x of a system S are distinguishable


0-7803-8682-5/04/$20.00 ?2004 IEEE


if the outputs η and η for the trajectories starting at x and x are different. A system S is observable if the output map x → η , which gives the output for the trajectory starting at x, is injective. For deterministic systems, observability amounts to determining the initial state. There is a corresponding notion of reconstructibility, which states that for any initial states x and x there exists T such that if the corresponding observations η and η are equal on the interval [0, T ], then ξ (T ) = ξ (T ), where ξ and ξ are the trajectories starting at x and x . For systems with inputs, there are a number of different observability notions [14], corresponding to the system being observable for some predetermined input, for every input, or for an input given as a feedback based on the observations up to the current time. II. OBSERVABILITY OF TURING MACHINES We use a standard de?nition of Turing machine [1]. De?nition 2 (Turing machine with output): Let Σ be a ?nite input alphabet and ? a ?nite output alphabet. A Turing machine with output M over (Σ, ?) is a tuple {Q, Qinit , Qhalt , Γ, Λ} where Q is a ?nite state set, Qinit is the set of initial states and Qhalt is the set of halting states. The transition function Γ and observation function Λ are Γ : Q × Σ → Q × Σ × ?, Λ : Q → ? ∪ {ε }. where ? = {?1, 0, +1}. A con?guration of a Turing machine M is an element of (q, w) of Q × ΣZ . The element w ∈ ΣZ is the tape contents. The successor function τ of M is a function τ : Q×ΣZ → Q × ΣZ de?ned as follows. If the state is q, and the element w0 of the tape is equal to a, then the transition (q, a) → (q , a , δ ) is applied, The element w0 is replaced by a , the tape is shifted by the map σ δ , where (σ (w))i = wi+1 , and the new state is q . We say that a Turing machine has a ?nite tape if there is a special blank symbol ∈ Σ such that every symbol is blank except for a ?nite contiguous block of non-blank symbols, otherwise it has an in?nite tape. De?nition 3: A (Turing) machine M is mortal if it halts on every con?guration, and nilpotent if there exists an integer N such that M halts on every con?guration after at most N steps. The mortality problem for Turing machines with an in?nite tape was shown to be undecidable by Hooper [4]. It is straightforward to show [12] that a Turing machine with in?nite tape is mortal if and only if it is nilpotent. The mortality problem for Turing machines with a ?nite tape is a distinct problem; a Turing machine which moves right until it ?nds the ?rst blank symbol on the tape is always mortal for a ?nite tape but not for an in?nite tape, since the latter need not contain any blanks. In general, results on the mortality problem for one class of systems cannot be used to derive results on the mortality problem for other classes, even if each class can simulate the other.

For applications to dynamical systems, we will require mortality for Turing machines with an in?nite tape. The decidability of the mortality problem for Turing machines with a ?nite tape is not known to the authors. A. Tape observability Consider the following tape observability problem for a Turing machine M with a single initial state qinit ∈ Qinit . The observability problem is to determine the initial state of the tape from the output. We assume that the initial tape is ?nite, but can take any value. It is clear that there is no upper bound on the time needed to distinguish two initial tapes, since an output of length n can only distinguish between outputs of length n. The following result reduces the tape observability problem to the mortality problem for Turing machines on a ?nite tape. Theorem 4: Tape observability for Turing machines is undecidable if the mortality problem for a ?nite tape is undecidable. Proof: Let M be a Turing machine with alphabet Σ which has at least two non-blank symbols. Construct a Turing machine with output M as follows: M ?rst makes a copy of its input. It then modi?es this copy by replacing the ?rst non-blank symbol with a blank. It ?nally runs M on the modi?ed copy of the input without disturbing the original input. If M halts, then M outputs its original input. Otherwise, M outputs nothing. Any input for M can be obtained as the modi?ed version of the input for M . Hence if M is mortal, then M is mortal, and hence tape observable. If M is immortal, then there is an input on which M does not halt. There are at least two inputs for M which give this input for M after blanking the ?rst symbol. On these inputs, M does not halt, and hence these inputs are indistinguishable. Note that the construction does not work for Turing machines with an in?nite tape, since there is no way to effectively copy the initial tape. B. State observability Instead of considering the initial tape as the unknown con?guration, we can instead consider the initial tape as a known parameter describing the system, and consider observability of the initial state. A Turing machine is state observable if the initial state qinit ∈ Qinit can be determined from the initial tape contents and the output. Theorem 5: State observability is undecidable for Turing machines with an in?nite tape. Proof: Let M be a Turing machine with a single initial state and a single halting state. Let Λ(q) = ε except for the halting state qhalt for which Λ(qhalt ) = y. Let Q be a set disjoint from Q, and i : Q → Q a be bijection. We let M be a copy of M with halting state qhalt = i(qhalt ) ∈ Q for which Λ(qhalt ) = y . The transition function Γ of M is ? ? ? ? given by Γ (i(q), a) = (i(q), a, δ ) if Γ(q, a) = (q, a, δ ).










s B1 B2 B3 s?1

s(B3 ) s(B2 ) s(B1 )

Fig. 1.

Tape contents of a Turing machine. Fig. 2.

The image of boxes under the shift map

Consider the disjoint union M M of M and M whose states are Q Q , initial states are Qinit Qinit , and halting states are Qhalt Qhalt . The transitions are given by Γ Γ (q, a) = Γ(q, a) if q ∈ Q, and Γ Γ (q , a) = Γ (q , a) if q ∈ Q . An observation of a state of M M is empty, except for one of the two halting states qhalt and qhalt , in which case M M reveals whether its state is in the original machine or the copy. If M halts on an input w, then so does M M , and the halting state reveals the initial state. If M does not halt, neither does M M , and no output is observed. Therefore, it is impossible to decide in general whether the initial state is qinit or qinit . In the construction, the halting states of M M reveal aspects of the initial con?guration which are not observed in other con?gurations. We therefore refer to halting states as revealing states for the machine with output. III. SIMULATION OF TURING MACHINES BY PIECEWISE-AFFINE SYSTEMS The standard simulation of a Turing machine relies on an encoding of the tape contents as a pair of numbers, which are rational for a ?nite tape. A. Encoding of Turing machines We now show how to simulate a Turing machine using a piecewise-af?ne map. This map will ?rst be a partial function on a number of cells; later we can glue these together in an appropriate way. Without loss of generality, we restrict to Turing machines with a transition function Γ : Q × Σ → Q × Σ × ? such that for every state q of the Turing machine, either Γ(q, a) = (q , a, δ ) where q does not depend on a, or Γ(q, a) = (q , a , 0). The former move simply shifts the tape without reading or writing, whereas the latter changes the tape without shifting. We can write the con?guration of a Turing machine as a triple (q, w, v) ∈ C = Q × Σω × Σω = C . The pair (w, v) ∈ Σω × Σω represents the tape contents . . . , v?2 , v?1 , v0 · w0 , w1 , w2 , . . ., with the tape head pointing to w0 . Finite tapes can be represented by pairs of ?nite words (w, v) ∈ Σ? × Σ? with no trailing blanks. Note that Σ? can be embedded in Σω by padding with in?nitely many blank symbols. There is a natural topology on Σω given by the metric d(w, w ) = 1/2k , where wi = wi for i < k but wk = wk . In this topology Σω is compact, but Σ? is not a closed subset of Σω . We encode the con?guration of a Turing machine as a subset of Q × [0, 1] × [0, 1] as follows. We assume Σ has

elements with integer numbers between 1 and N, and encode a sequence w ∈ Σω by

θ (w) = ∑ wi /ri+1 ,

where r > N + 1 (say r = N + 2). The encoding of a state of a Turing machine is given by ν (q, w, v) = (q, θ (w), θ (v)). The function θ is continuous and injective. Its image θ (Σω ) is a Cantor set contained in the interval (0, 1). If all elements of w are eventually equal to some constant, then θ (w) ∈ Q, so whatever value is chosen to represent the blank symbol , the encoding of a word w ∈ Σ? is always a rational. We de?ne the cell C(q) = {q} × [0, 1] × [0, 1], and the box B(q, a) to be the convex hull of ν (q, aw, v) in C(q). To encode a Turing machine, we also need to simulate its transition by a map f . If Γ(q, a) = (q , a , 0), then we can take f : B(q, a) → B(q , a ) by f (q, x1 , x2 ) = (q , x1 + (a ? a)/r, x2 ), which simply moves around boxes. A shift of the tape can be simulated by the shift map s on [0, 1] × [0, 1] given by s(x1 , x2 ) = rx1 ? rx1 , ( rx1 + x2 )/r . (1)

The map s is af?ne on each of the boxes B. If Γ(q, a) = (q , a, 1), then we take f : B(q, a) → C(q ) by f (q, x1 , x2 ) = q , rx1 ? rx1 , ( rx1 + x2 )/r = (q , s(x1 , x2 )) The reverse-shift s?1 can also be given as a piecewise-af?ne map. Overall, the transitions are related by the commutation relation f ? ν = ν ? τ . B. Rational piecewise-af?ne maps Our goal is to represent Turing machines by continuous rational piecewise-af?ne functions, since computations may be performed effectively on such functions, and continuity is a natural condition to require for functions on continuous spaces. Further, discontinuities are a well-known source of uncomputability; a discontinuous real-valued function is uncomputable using interval arithmetic [15]. For an overview of computability questions in analysis, see [16]. De?nition 6 (Rational piecewise-af?ne maps): A continuous function f : X → Y is a rational piecewise-af?ne map if X is the union of ?nitely many sets Xi such that each Xi is given by a matrix inequality of the form Bi x ≤ bi , and f : Xi → Y is given by f (x) = Ai x + ai . Here, the ai


B(0, 0)

B(0, 1)

φ(x) = 0 for x ∈ B(q, a)




C(qhalt )
Fig. 4. A function φ (x) which is positive except on boxes B(q, a) for q ∈ Qhalt .

Fig. 3. State space of a piecewise-af?ne map simulating a Turing machine.

and bi are vectors with rational coef?cients, and the Ai and Bi are matrices with rational coef?cients. The following results show how to extend the simulating partial functions to total functions. Theorem 7: Let X be a contractible (e.g. convex) polytope. 1) If f : A → X is a rational piecewise-af?ne map de?ned on A ? X, then f extends to a rational piecewise-af?ne map de?ned on X. 2) If in addition f is de?ned on a ?nite disjoint union of topological discs which are disjoint from the boundary and is injective, then f can be extended to a rational piecewise-af?ne homeomorphism. Proof: [Sketch] To prove Pt. 1, we simply triangulate the complement of A, and extend f in a piecewiselinear way by giving its values on the vertices of the simplices. To prove Pt. 2, we see that since f is isotopic to the identity on A, so by the isotopy extension theorem (see [17] Thm. 8.1.3) f extends to a homeomorphism on X. This can be triangulated by taking small enough perturbations. (Alternatively, we can construct the original isotopy by a suitable piecewise-constant derivative vector ?eld, and extend within the class of piecewise-constant vector ?elds.) In particular, any Turing machine can be simulated by a rational piecewise-af?ne map, and any reversible Turing machine by a rational piecewise-af?ne homeomorphism. The following result shows that any orbit which remains in the boxes B(Q, Σ) for all time is shadowed by the image of some point in the Cantor set ν (Q, Σω , Σω ). Lemma 8 (Shadowing lemma): Suppose x ∈ X is such that there exist sequences (qn ) and (an ) such that f n (x) ∈ B(qn , an ) for all n. Then there exists a con?guration (q, w, v) ∈ C such that f n (ν (q, w, v)) ∈ B(qn , an ) for all n. Proof: For each m, let Rm be the set of points y such that f n (y) ∈ B(qn , an ) for all n ≤ m. Then Rm is a rectangle, since R0 is a rectangle, and f maps rectangles in some B(q, a) to rectangles. We claim that the vertices of Rm are points of ν (C ) for all m. This is true for m = 0, since R0 = B(q0 , a0 ) and the vertices of R0 are points of ν (C ). For any m we have f m (Rm ) = f m (Rm?1 ) ∩ B(qm , am ), so if the vertices of f m (Rm?1 ) are points of ν (C ), then so are those of f m (Rm ). The claim follows by induction since ν (C ) is invariant under f , and f is locally injective on each B(q, a). Hence each Rm is a nonempty compact set containing a

point of ν (C ), and so Rm ∩ ν (C ) is a decreasing sequence of nonempty compact sets. Therefore there is a point in ∞ n=0 Rm ∩ ν (C ), and this point is the required image of (q, w, v). IV. OBSERVABILITY OF PIECEWISE-AFFINE SYSTEMS We wish to consider continuous systems consisting of continuous functions with continuous output. We also wish to consider various kinds of sets of initial conditions. In particular, we would like to take all possible initial conditions, or initial conditions in some compact set. We de?ne output functions of a similar form to h(x) = (φ (x), x1 , . . . , xk , xk+1 φ (x), . . . , xn φ (x)) where φ : X → R and x ∈ Rn , so that the ith coordinate of x is observable if and only if i ≤ k or φ (x) = 0. An example of the function φ is given in Fig. 4. We often take φ (x) = 0 on the boxes B(q, a) for q ∈ Qhalt , and φ (x) > 0 otherwise. A. Continuous rational piecewise-af?ne systems De?nition 9 (Continuous piecewise-af?ne systems): A pair ( f , h) is a continuous rational piecewise-af?ne system if f : X → X and h : X → Y are rational piecewise-af?ne maps. Theorem 10: Observability is undecidable for continuous rational piecewise-af?ne systems with ?nitely many possible initial states. Proof: Let f simulate a pair of identical Turing machines M , M as in the proof of Thm. 5. Let Xinit = {x0 , x0 } be a set consisting of two initial states, corresponding to the initial states of each Turing machine. Consider an output h : X → R where h(x) > 0 if x ∈ B(qhalt , a), h(x) < 0 for x ∈ B(qhalt , a), and h(x) = 0 if x ∈ C(q) if q ∈ {qhalt , qhalt }. Then deciding observability of ( f , h) is equivalent to solving the halting problem for M . If M halts, then x0 reaches B(q, a) for q ∈ Qhalt giving positive output, and x0 reaches B(q , a) for q ∈ Qhalt giving negative output. If M does not halt, then no output is detected for either x0 and x0 , and the system is unobservable on its initial state. Theorem 11: Observability is undecidable for continuous rational piecewise-af?ne systems with any possible initial states. Proof: Let M be a Turing machine with M states ? and halting states Qhalt , let X = [0, M] × [0, 1] and let


f? be a rational piecewise-af?ne map simulating M on ? ? X, let X = X × [0, 1], let f (x1 , x2 , x3 ) = ( f?(x1 , x2 ), x3 ) and let h : X → X × [0, 1] × [0, 1] be given by h(x1 , x2 , x3 ) = (x1 , x2 , φ (x1 , x2 )x3 ) where φ = 0 on Bq,a for q ∈ Qhalt , and φ ∈ (0, 1] otherwise. Then the initial x1 , x2 coordinates are known, so the initial state can be determined as soon as the x3 coordinate is known. This occurs if φ ever becomes nonzero. This can only not occur if f n (x) ∈ B(Q, Σ) for all iterates, and further that the machine never halts. By the shadowing lemma, it suf?ces to consider points in ν (C ), and then it is clear that the system is unobservable if and only if M is mortal on an in?nite tape‘. Hence observability is undecidable, since mortality for Turing machines with an in?nite tape is undecidable. B. Piecewise-af?ne planar homeomorphisms A reversible Turing machine is simulated by homeomorphisms of the plane. Since for a reversible system, knowing the current state gives full knowledge of the initial state, we can consider observability for planar systems and take h(x) = (φ (x), x1 φ (x), x2 φ (x)). Observability is then equivalent to having every state entering the set where φ (x) = 0 (though we need a dummy ?xed state with φ (x) = 0 so as not to allow a state staying in the set where φ = 0 to be distinguished from every other state). Although [2] shows that any Turing machine is simulated by a reversible Turing machine, this is not enough to show that the mortality problem is undecidable. We obtain the following results. Theorem 12: 1) Observability is undecidable for continuous reversible piecewise-af?ne planar systems with ?nitely many initial states. 2) If the mortality problem for reversible Turing machines with an in?nite tape is undecidable, then so is observability for continuous rational piecewise-af?ne planar homeomorphisms. C. Discontinuous piecewise-af?ne systems Up to now we have considered continuous functions. However in many situations it is natural to model hybrid systems by discontinuous piecewise-af?ne functions. On the boundaries of partition elements, we take the functions to by multivalued; this mild form of nondeterminism does not cause any serious problems. A multivalued function f : X → X is a rational piecewiseaf?ne function if that X is a union of polytopes of the form Bx ≤ b on which f (x) = Ax + b. The function f is multivalued on a common boundary of two polytopes. A piecewise-af?ne hybrid system is speci?ed by a rational piecewise-af?ne function f on a (possibly disconnected) union of polytopes, and a continuous observation function h. Note that the system as de?ned may be nondeterministic; when the intersection of polytopes is reached, the behaviour is undetermined. However, this does not cause dif?culties in determining system observability.

De?nition 13 (Discrete-state observability): A piecewise-af?ne hybrid system is discrete-state observable if it is possible to determine the initial discrete state from the output. By reduction to the state observability problem for Turing machines, we obtain the following result for systems. Theorem 14: Discrete-state observability is undecidable for discontinuous piecewise-af?ne hybrid systems. V. FINITE- AND INFINITE-TIME OBSERVABILITY A system is said to be observable in time T if every pair of trajectories can be distinguished by the output over the time interval [0, T ]. A system can be ? Observable in in?nitesimal time if it is observable in time T for any T > 0, ? Observable in ?nite time if it is observable in time T for some T < ∞. ? Observable in in?nite time if any pair of trajectories can be distinguished on [0, ∞). A linear system is observable if and only if it is observable in in?nitesimal time. For Turing machines with outputs, state observability must be in ?nite time, since there are only ?nitely many possible trajectories which need to be distinguished, and input observability must be in in?nite time, since in?nitely long inputs are allowed. For discrete-time and hybrid systems, it is straightforward to construct examples which are observable in in?nite time. Example 15: Consider a Turing machine which reads its input from left to right and halts on ?nding the ?rst zero. Then the piecewise-af?ne continuous simulator is observable in in?nite time, but not in ?nite time, since there does not exist ?nite N such that M halts in time N. Example 16: Consider the continuous piecewise-af?ne system with state space X = [0, 2] and output space Y = [0, 1]. Let f (x) = x + 1 if x ≤ 1, 2 if x ≥ 1; h(x) = 0 if x ≤ 1 x ? 1, if x ≥ 1.

(2) Then if x ≤ 1, h(x) = 0 and h( f (x)) = x, whereas if x ≥ 1, h(x) = x ? 1 and h( f (x)) = 1. Clearly, the outputs differ after one step for any two initial states. Hence the system is observable in time 1. Example 17: Consider the continuous piecewise-af?ne system with state space X = [0, 2] and output space Y = [0, 1]. Let f (x) = 2x if x ≤ 1, 2 if x ≥ 1; h(x) = 0 if x ≤ 1, x ? 1 if x ≥ 1. (3)

Note that f and h are continuous at x = 1. If x0 > 0, then f n (x0 ) > 1 for some least n, the output is (0, 0, . . . , 0, 2n x0 ? 1, 1, 1, . . .) and x0 = (h( f n (x0 )) + 1)/2n . If x0 = 0, then the output is (0, 0, . . .). Hence the output for any two initial points is different, but since there are points whose output consists of arbitrarily long initial sequences


of zeroes, it is not possible to distinguish x0 = 0 from x0 > 0 on any ?nite time interval. VI. CONCLUSIONS AND FUTURE WORKS A. Conclusions In this paper we have shown how to extend results on undecidability of reachability to results on observability. Two observability problems for Turing machines were shown to be undecidable. These results translate immediately to undecidability results for classes of systems which can simulate Turing machines with suitable initial state sets. To obtain undecidability of observability for systems in which any initial state is allowed, it is necessary to take more care over the construction to ensure that the hybrid system is not trivially unobservable. Examples of piecewise-af?ne hybrid systems were given to show that observability may be in ?nite-time or even in?nite time. B. Future Works These results show that for even relatively simple classes of system, observability is not decidable. However, observability is still an important system property which requires study. A number of approaches are possible. Sub-classes of system for which observability is decidable are known to exist, such as a result of Vidal et al. [18] for linear switched systems. Suf?cient conditions for observability for general systems which are decidable may be given, such as observability in ?nite time [10] or observability after a single discrete event for piecewise-af?ne systems [19]. An alternative approach is to consider approximate system properties, in the same spirit as discrete-state observability, which may be decidable. There are also links with information theory, since observability of a system providing an encoding can be viewed as decidability of the encoding; see [20]. The relationship between observability and realisations of piecewise-af?ne hybrid systems [21] is also an important area for further work. VII. ACKNOWLEDGEMENTS The authors gratefully acknowledge the ?nancial support of the European Commission through the project Control and Computation (IST-2001-33520) of the Program Information Societies and Technologies.

[1] M. Sipser, Introduction to the Theory of Computation. Brooks Cole, 1996. [2] C. H. Bennett, “Logical reversibility of computation,” IBM J. Res. Develop., vol. 17, pp. 525–532, 1973. [3] K. Morita, “Universality of a reversible two-counter machine,” Theoret. Comput. Sci., vol. 168, no. 2, pp. 303–320, 1996. [4] P. K. Hooper, “The undecidability of the Turing machine immortality problem,” J. Symbolic Logic, vol. 31, pp. 219–234, 1966. [5] V. D. Blondel, O. Bournez, P. Koiran, C. H. Papadimitriou, and J. N. Tsitsiklis, “Deciding stability and mortality of piecewise af?ne dynamical systems,” Theoret. Comput. Sci., vol. 255, no. 1-2, pp. 687–696, 2001. [6] C. Moore, “Generalized shifts: unpredictability and undecidability in dynamical systems,” Nonlinearity, vol. 4, no. 2, pp. 199–230, 1991. [7] P. Koiran, M. Cosnard, and M. Garzon, “Computability with lowdimensional dynamical systems,” Theoret. Comput. Sci., vol. 132, no. 1–2, pp. 113–128, 1994. [8] E. Asarin, O. Maler, and A. Pnueli, “Reachability analysis of dynamical systems having piecewise-constant derivatives,” Theoret. Comput. Sci., vol. 138, no. 1, pp. 35—65, 1995. [9] H. T. Siegelmann and E. D. Sontag, “On the computational power of neural nets,” J. Comput. System Sci., vol. 50, no. 1, pp. 132–150, 1995. [10] E. D. Sontag, “From linear to nonlinear: Some complexity questions,” in Proceedings of the 34th IEEE Conference on Decision and Control. New York: IEEE Press, 1995, pp. 2916–2920. [11] V. D. Blondel and J. N. Tsitsiklis, “A survey of computational complexity results in systems and control,” Automatica, vol. 36, no. 9, pp. 1249–1274, 2000. [12] V. D. Blondel, O. Bournez, P. Koiran, and J. N. Tsitsiklis, “The stability of saturated linear dynamical systems is undecidable,” J. Comput. System Sci., vol. 62, no. 3, pp. 442–462, 2001. [13] R. Koplon, E. Sontag, and M. Hautus, “Observability of linear systems with saturated outputs,” Linear Algebra Appl., vol. 205-206, pp. 909–936, 1994. [14] E. D. Sontag, “On the observability of polynomial systems, i: Finitetime problems,” SIAM J. Control Optim., vol. 17, no. 1, pp. 139–151, 1979. [15] A. Grzegorczyk, “Computable functionals,” Fund. Math., vol. 42, pp. 168–202, 1955. [16] K. Weihrauch, Computable analysis - An introduction, ser. Texts in Theoretical Computer Science. Berlin: Springer-Verlag, 2000. [17] M. W. Hirsch, Differential Topology, ser. Graduate Texts In Mathematics. Springer-Verlag, 1976, no. 33. [18] R. Vidal, A. Chiuso, S. Soatto, and S. Sastry, “Observability of linear hybrid systems,” in Hybrid Systems: Computation and Control, ser. Lecture Notes in Computer Science, O. Maler and A. Pnueli, Eds., no. 2623. Berlin Heidelberg New York: Springer-Verlag, 2003, pp. 527–539. [19] P. Collins and J. H. van Schuppen, “Observability of piecewise-af?ne hybrid systems,” in Hybrid Systems: Computation and Control, ser. Lecture Notes in Computer Science, no. 2993. Berlin Heidelberg New York: Springer-Verlag, 2004, pp. 265–279. [20] T. M. Cover and J. A. Thomas, Elements of information theory, ser. Wiley Series in Telecommunications. New York: John Wiley & Sons, Inc., 1991. [21] L. Habets and J. H. van Schuppen, “Reduction of af?ne systems on polytopes,” in Proceedings of the International Symposium on the Mathematical Theory of Networks and Systems, Univ. of Notre Dame, Notre Dame, IN, U.S.A., August 2002, 2002.


Processes General Terms Theory.pdf
. . , Pk be Turing machines (the provers) which are computationally ...We also showed that multiagent systems with collective partial observability ...
...power of Piecewise Constant Derivative systems..pdf
Nous prouvons que les systemes PCD sont equivalent aux machines de Turing ...of hybrid systems: Piecewise Constant Derivative Systems (PCD systems) are ...
...Control Discrete-Event and Hybrid Systems, in So....pdf
Computational Issues in Intelligent Control Discrete-Event and Hybrid Systems,...3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 3.2 Algorithms and Turing Machines ....
Stabilization of Hybrid Dynamical Systems.pdf
Stabilization of Hybrid Dynamical Systems_专业资料。We consider stabilization of... as revealed in 7], is that many HDS models have super-Turing ...
vol. 3343, p. 281. Lecture Notes in Control and Information....pdf
[10] D. D’Alessandro, “On quantum state observability and measurement,”...I. INTRODUCTION Hybrid systems consisting of interacting continuous and discrete...
...hybrid model with byzantine faults, crashes, and reco.pdf
Since parties are modeled as interactive Turing machines, the complete state ...4 Conclusion We have presented the ?rst hybrid distributed system model that...

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。