A state of a dynamic computational structure distributed in an environment: a model and its corollarie
In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible....
Saved in:
| Published in: | Труды Института прикладной математики и механики |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2010
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/123962 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | A state of a dynamic computational structure distributed in an environment: a model and its corollarie / O. Kurganskyy // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 150-160. — Бібліогр.: 5 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-123962 |
|---|---|
| record_format |
dspace |
| spelling |
Kurganskyy, O. 2017-09-15T17:17:24Z 2017-09-15T17:17:24Z 2010 A state of a dynamic computational structure distributed in an environment: a model and its corollarie / O. Kurganskyy // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 150-160. — Бібліогр.: 5 назв. — англ. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/123962 519.7 In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose an approach for defining what a state is. В работе коллектив взаимодействующих в дискретной среде автоматов рассматривается как цельный автоматоподобный вычислительный динамический объект. Для таких распределённых в среде объектов предлагается метод определения их функциональной эквивалентности, инвариантной относительно динамики. У роботі колектив взаємодіючих автоматів з одним станом у дискретному середовищі розглядається як цільний автоматоподібний обчислювальний динамічний об'єкт. Для таких розподілених по середовищу об'єктів пропонується метод визначення їхньої функціональної еквівалентності, інваріантної щодо динаміки. The author acknowledges the useful discussions on this work with Dr. V.Kozlovskyy, Dr. I.Grunsky and Dr. I.Potapov. en Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики A state of a dynamic computational structure distributed in an environment: a model and its corollarie Состояние динамической вычислительной структуры, распределенной в среде: модель и её следствия Стан динамічної обчислювальної структури, розподіленої в середовищі: модель і її наслідки Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| spellingShingle |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie Kurganskyy, O. |
| title_short |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| title_full |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| title_fullStr |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| title_full_unstemmed |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| title_sort |
state of a dynamic computational structure distributed in an environment: a model and its corollarie |
| author |
Kurganskyy, O. |
| author_facet |
Kurganskyy, O. |
| publishDate |
2010 |
| language |
English |
| container_title |
Труды Института прикладной математики и механики |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| title_alt |
Состояние динамической вычислительной структуры, распределенной в среде: модель и её следствия Стан динамічної обчислювальної структури, розподіленої в середовищі: модель і її наслідки |
| description |
In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose an approach for defining what a state is.
В работе коллектив взаимодействующих в дискретной среде автоматов рассматривается как цельный автоматоподобный вычислительный динамический объект. Для таких распределённых в среде объектов предлагается метод определения их функциональной эквивалентности, инвариантной относительно динамики.
У роботі колектив взаємодіючих автоматів з одним станом у дискретному середовищі розглядається як цільний автоматоподібний обчислювальний динамічний об'єкт. Для таких розподілених по середовищу об'єктів пропонується метод визначення їхньої функціональної еквівалентності, інваріантної щодо динаміки.
|
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/123962 |
| citation_txt |
A state of a dynamic computational structure distributed in an environment: a model and its corollarie / O. Kurganskyy // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 150-160. — Бібліогр.: 5 назв. — англ. |
| work_keys_str_mv |
AT kurganskyyo astateofadynamiccomputationalstructuredistributedinanenvironmentamodelanditscorollarie AT kurganskyyo sostoâniedinamičeskoivyčislitelʹnoistrukturyraspredelennoivsredemodelʹieesledstviâ AT kurganskyyo standinamíčnoíobčislûvalʹnoístrukturirozpodílenoívseredoviŝímodelʹííínaslídki AT kurganskyyo stateofadynamiccomputationalstructuredistributedinanenvironmentamodelanditscorollarie |
| first_indexed |
2025-11-25T01:23:49Z |
| last_indexed |
2025-11-25T01:23:49Z |
| _version_ |
1850500769522909184 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2010. Том 21
UDK 519.7
c©2010. Oleksiy Kurganskyy
A STATE OF A DYNAMIC COMPUTATIONAL STRUCTURE
DISTRIBUTED IN AN ENVIRONMENT: A MODEL AND ITS
COROLLARIES
In this work a collective of interacting stateless automata in a discrete geometric environment is
considered as an integral automata-like computational dynamic object. For such distributed on the
environment object different approaches to definition of the measure of state transition are possible. We
propose an approach for defining what a state is.
Keywords: collective of automata, cellular automata, finite automata theory, special relativity theory.
1. Introduction. Currently there is great interest in computational models consisting
of underlying regular computational environments, and built on them distributed
computational structures. Examples of such models are cellular automata, spatial
computation and space-time crystallography [1]. For any computational model it
is natural to define a functional equivalence of different but related computational
structures. In the finite automata theory an example of such equivalence is automata
homomorphism and, in particular, automata isomorphism. If we continue to stick to
the finite automata theory, a fundamental question arise, what a state of a distributed
computational structure is. This work is devoted to particular solution of the issue.
The work consists of the informal presentation in this introduction of an idea that
came from the Poincaré’s relativity theory, and an illustration of this idea by a simple
computational model with a regular and discrete dynamics that is especially suited for
the illustration purpose. The model with the problem statement is like the model of [1],
but in essence differs from it. One of the distinguishing features of the model is spatial
movement of computational structure in the environment. As consequence we present the
number of results on the relationship between computational and dynamic properties of
these structures.
So, in this work the collectives of stateless (i.e. with one state) automata interacting
with an environment defined as a graph are considered. We study a collective of automata
as an integral automata-like dynamic computational object. The fundamental question
what is the state of such dispersed and moving on the environment object and how to
measure the amount of state transitions is quite non-trivial. As opposed to the finite
state automata where the measure of state transition is one state per unit of time,
for a computational dynamic object distributed on the environment certainly different
approaches to definition of the measure of state transition are possible.
The idea of our approach came from the special relativity theory. It is based on the
concept of relativity in Poincaré’s interpretation [2]. In explanation how to generally
understand the relativity Poincaré begins with an example of resizing of all dimensions
in the Universe in the same number of times and proceeds with consideration of arbitrary
150
A state of a dynamic computational structure distributed in an environment
deformations concluding that they should be unnoticed by an observer because observer’s
standards are subjected to the same deformations. This reasoning coupled with the
principle that without any changes in the object the process of computation in it is
not possible is used in this study to define a state of collective automata. A “change” in
an object is a change in the relative position of its “elementary” parts per se. Thus, the
movement in the environment underlies the process of computation in our model.
Let us explain it by an example of a chessboard with pawns. The chessboard is
provided with a natural reference frame. Suppose that we can move any pawn one chess
square per unit time in one of four directions: ←,↑,→,↓, i.e. pawn’s velocity is one chess
square in a certain directions per unit time. Let us compose from the pawns a figure, for
example, an “O”-like figure, and look at all these pawns as an integral object. Define the
velocity of the object on the chessboard as the average velocity of his pawns. Suppose
that the object is moved at maximal velocity “one chess square per unit time” in a
constant direction. Can the object be transformed simultaneously with the motion from
“O” to, for example, “T”? It is obviously that no. That is, at maximum constant velocity
in the example the object cannot be changed and, from our point of view, its state is
invariable and it performs no computation. This point of view we have formally illustrated
in this work by the simplest example model of stateless automata interacting with one-
dimensional environment.
The introduced illustrative model is computational universal, and collectives of
automata in the environment can be seen as automata-like computational objects. By
analogy with Turing machines, which can answer certain questions about properties of
words on the tapes, for these objects natural questions arise what properties of the
environment and other objects in it they can identify. One of the interesting questions is
what can an object say about the velocity of its elementary parts (i.e. stateless automata).
Can it “perceive” any changes in velocity of elementary parts which it consists of?
This question is similar to the issue in the Poincaré’s story about relativity: can the
observer see the deformation of the space, which includes the deformation measurement
standards? Having as a goal the answer “no”, we define our computational model. This
goal determines the language (motion velocity, proper time velocity as a measure of state
transition, reference frame) of interaction between collectives of automata.
The concluding comparison of the obtained results with some formulas of special
relativity theory shows that the formulated principles are invariant in relation to physical
and informational linguistic means of expression. In other words, the semantic affinity
of the original principle of motion in our discrete model to the principles of the special
relativity theory resulted in the syntactic affinity of their languages (e.g., time dilation
formula, velocity-addition formula, “length contraction/extension” formula). But because
of discreteness of our model there are differences. For example, the linear sizes of objects
can either decrease or increase in different reference frames. Comparing the formulas
with the formulas of the special relativity theory allows also revealing different physical
meaning of Lorentz factor in the formulas of length contraction and time dilation.
To emphasize a physical analogy in the proposed model and the problem statement
we use the short word “body” as alias for “collective of automata”.
151
Oleksiy Kurganskyy
Figure 1. A chessboard with pawns
Figure 2. The environment G
The proposed research is inspired by several research directions which are: 1) collective
of automata in finite automata theory and complexity of the interactions between
them; 2) discrete models of physical processes and projecting of the physical world into
informational space of symbols and languages for computer simulation of the physical
world; 3) studying the notion of time; 4) spatial computation.
2. Definitions. In what follows we use denotations Z and R for the sets of integers
and real numbers, respectively. Initially in the model defintion we assume that the
domains for the time T and space coordinates X coincide with Z but then we will
extend them to R.
The computational model, that we use for this study, consists of two main
components: an underlying environment G that is represented by a graph and a set
of stateless automata, which are interacting with the environment.
The environment G (see Fig.2) is defined as the infinite directed graph with the set
of nodes V = {x+ 1
2 |x ∈ Z} and the set of edges E = {(x− i
2 , x+ i
2)|x ∈ Z, i ∈ {−1, 1}}.
An edge (x− i
2 , x + i
2) for some i ∈ {−1, 1} has the absolute coordinate x ∈ Z and the
direction i. Absolute coordinate of an edge e will be denoted by x(e) and its direction by
r(e). Also the edge e will be denoted by x(e)r(e). By the neighborhood of an edge xi we
understand the pair of edges xi and (x + i)−i. The edges xi and (x + i)−i will be called
opposite edges and xi and x−i will be called contrary edges.
Let A = (SA, IA, OA, δA, λA) be a Mealy automaton, where SA, IA and OA are the
sets of states, input symbols, and output symbols, respectively, and δA : SA × IA → SA
and λA : SA × IA → OA are transition function and function of outputs respectively.
We consider only stateless Mealy automata. The set of states of a stateless automaton
A consists of single state, so there is no sense to mention the transition function and
the set of states of a stateless automaton. Thus we write A = (IA, OA, λA) instead of
A = (SA, IA, OA, δA, λA). Within the framework of this article for reasons of consistency
of latter definitions we name a stateless Mealy automaton as an elementary body, and
152
A state of a dynamic computational structure distributed in an environment
we name its unique state as the internal state. The elementary bodies will be denoted by
lowercase letters, for example, b = (Ib, Ob, λb). We assume also that elementary bodies are
coloured in a way that isomorphic automata will have the same colour and non-isomorphic
automata will have different colours. We assume that r different numbered from 1 to r
colours are used. Every moment of time t any elementary body b is located on an edge
b(t) of the environment G. The input for an elementary body, located on an environment
edge xi, is the sequence (p1, p2, . . . , pr, q1, q2, . . . , qr) ∈ Ib called the neighbourhood
state of the edge xi, where pk and qk are the numbers of elementary bodies of the colour
k, located on the edges xi and (x + i)−i at the same moment of time, respectively. The
output of an elementary body is one of the two motions either the straight-line motion
→∈ Ob or the turn ←↩∈ Ob. If the output of an elementary body b at a time moment
t ∈ Z on an edge b(t) = xi is the straight-line motion, then at the next time moment
b(t+1) = (x+ i)i and we say that it does not change its external state. If the output is
the turn then b(t + 1) = x−i and we say that the elementary body changes its external
state. Accordint to definition all elementary bodies have the same sets of input and
Figure 3. t = s + τ vs. t2 = s2 + τ2
output symbols, so we can write b = (I, O, λb) instead of b = (Ib, Ob, λb).
Denoting by τb(t) the number of external state changes of b until the moment of time t
we have that 1 = τb(t+1)−τb(t)+ |x(b(t + 1))− x(b(t))| and also t = τb(t)−τb(0)+sb(t),
where sb(t) =
∑t
j=1 |x(b(j)) − x(b(j − 1))| is the path covered by b during the period
of time from 0 to t. In other words any elementary body uses the absolute time unit t
either for one spatial coordinate change s in the environment or for one external state
transition τ . Schematically, this has the form t = s + τ , illustrated in the left side of
Figure 3. On the right in Figure 3, for comparison, a similar formula t2 = s2 + τ2 is
shown that one would expect in a space with Euclidean metric. This formula is using in
the special relativity theory for the expression of so-called spacetime interval τ2 = s2−t2,
which is invariant under Lorentz transformations.
We call τ = τb(t) the proper time of b and wb(t) = τb(t + 1) − τb(t) the proper
time velocity of b. We call wb(t) uniform proper time velocity if wb(t) is a constant.
Let us denote by xb(t) = x(b(t)). We call xb(t) the absolute coordinate of b at the
moment of time t. We denote by vb(t) = xb(t+1)−xb(t) the absolute spatial velocity
of b at the moment of time t. We call it uniform spatial velocity if vb(t) is a constant.
For example, it follows from above definitions that any elementary body can have only
one of the following uniform spatial velocities: v = 1, v = −1, v = 0.
An elementary body is unambiguously definable by the set of input symbols that
change its external state. So in the context of our model we can understand under an
153
Oleksiy Kurganskyy
Figure 4. Dynamics of elementary bodies from the Example 1
elementary body b the set of signals from I that change its external state rather than the
triple b = (I, O, λb). In additional we assume also that elementary body can not change
its external state anyway if opposite environment edge is empty, that is, the interaction
between elementary bodies occurs only by collisions in the vertices of the environment
(compare with the notion of vacuum state in [1]). The elementary bodies can be seen as
analogues of signals propagating in the causal network [1]. Propagation of signals in [1]
depends on the functions in the nodes of a causal network, in our model it depends on
the output functions λ of elementary bodies, i.e., on the properties of “signal”.
It should be noted that a set I can be infinite. We have done nothing to circumvent
this problem but we can simply assume that the interaction of elementary bodies proceeds
so that the set of all possible input symbols can only be finite.
We call the pair of a space coordinate x and a time coordinate t as coordinate in the
absolute reference frame O = X × T and denote by the column vector. We call O also
the event space.
Definition 1. A body is an arbitrary finite set of elementary bodies.
According to the defintion different bodies may have common parts and one body can
contain another body as a subset. If an elementary body belongs to a body then we will
look at it as an elementary part of this body. An elementary body can be an elementary
part of different bodies simultaneously.
The following two examples illustrate some of introduced definitions. Any elementary
body in both examples changes its external state if and only if opposite environment edge
is not empty. From it follows that all elemantary bodies are automata isomorphic. We
assume that all elementary bodies in each example are enumerated by integer numbers.
Example 1. At time t = 0 for each x ∈ Z the elementary body with the number x is
located on the edge x+1 if x is even number and x−1 otherwise. We define the body A1
as the set A1 = {0, 1, 2} of elementary bodies 0, 1 and 2.
Example 2. At time t = 0 for each x ∈ Z the elementary body with the number x
has the coordinate 4
⌊
x
3
⌋
+ (x mod 3) and located on the edge with the direction −1 if
x ≡ 1 mod 3 and on the edge with the direction +1 otherwise. In this example we define
the body A2 = {0, 1, 2}.
Let a body B consist of n elementary bodies enumerated by numbers {1, 2, . . . , n}.
Then the absolute (average) coordinate of the body B at time t is the value xB(t) =
x1(t)+...+xn(t)
n and absolute spatial velocity of the body B at time t is the value vB(t) =
154
A state of a dynamic computational structure distributed in an environment
xB(t + 1)− xB(t). The bodies A1 and A2 from the above examples have uniform spatial
velocities 0 and 1
3 , respectively. From the definitions it follows that the maximal possible
positive or negative spatial velocities of any body can be 1 or −1.
Since the coordinate values of a body can be non-integers let us extend the absolute
reference frame O from Z×Z to R×R. Let t ∈ Z and −1
2 < ∆ ≤ 1
2 then we say that an
elementary body b at time t + ∆ has the coordinate xb(t + ∆) = xb(t) + r(b(t)) ·∆ and
is located on the edge b(t + ∆) = b(t). The definition implies that the all neighborhood
states of the environment edge b(t′) at time t′ = t+∆ coincide for all ∆, −1/2 < ∆ ≤ 1/2,
t ∈ Z. In particular, the neighborhood state of the environment edge b(t′) at times t′ = t
and t′ = t + 1/2 are the same, t ∈ Z, and thus, the behavior of elementary bodies is
completely determined in the nodes of the environment in which, figuratively speaking,
the elementary bodies collide.
We define the world line b(t′ : t′′) of an elementary body b in time interval from t′ ∈ R
to t′′ ∈ R as b(t′ : t′′) =
{(
xb(t)
t
)
|t′ ≤ t ≤ t′′, t ∈ R
}
.
If the motion of an elementary body in a time interval from t′ to t′′ corresponds to a
straight world line segment, that is, during this time the elementary body did not change
the external state, such a motion is called elementary motion.
3. A state of a body. A body interacting with other bodies exert influence on them
and is also under their influence. It is quite natural to describe such influences on the
basis of the notion of a state of a body. Our definition of a state of a body takes into
consideration the relative positioning of its elementary parts in the environment. The
changes of relative positioning of elementary parts in a body can affect the body entirely
or a particular part of it. This motivates the question how to measure the amount of state
transition. Before the definition of the notion of a state we introduce the denotation for
the measure τ = τB(t) of state transition of a body B with the flow of time t. A casual
meaning of τ = τB(t) is the “age” of the body B at the moment t. We call τ = τB(t) the
proper time of B.
Independently from the definition of τ = τB(t), we introduce the velocity wB(t) of
external state transition of the body B as wB(t) = τB(t+1)− τB(t). We call this value
as the proper time velocity of B at the moment of the absolute time t.
Definition 2. For any body B wB(t) = 1 ⇔ ∀b∈Bwb(t) = 1
Definition 3. For any body B wB(t) = 0 ⇔ ∀b∈Bwb(t) = 0
From it follows that a body B does not change its external state if all its elementary
bodies do not change their external states. It means that two bodies are at the same
external state in the environment if one of them can be transformed into another by
straight-line shifts on the equal number of steps applied to all its elementary parts in
direction corresponding their external states.
We have defined what does it mean that two bodies are in the same external state,
rather than what the external state of a body in fact is. If needed the notion of external
state can be in generally defined as follows. Since the relation “to be in the same external
state” is an equivalence relation, the external states are equivalence classes of this relation.
The same holds for the latter definition of internal state.
155
Oleksiy Kurganskyy
Theorem 1. For any body B, if |vB(t)| = 1 then wB(t) = 0.
Proof. The statement follows from the fact that any change of the external state of a
body is not possible in case of maximal spatial velocity of all its elementary parts. ¤
The notion of external state of a body allows to start to consider the bodies as an
automata-like model of algorithms. It is natural to ask a functional equivalence of different
bodies for example something like automata isomorphism in the finite automata theory.
But since two bodies with different absolute spatial velocities are definitely in different
external states we can not compare them functionally. For example there is no sense to
“ask” a body to determine its absolute spatial velocity. However we would like to identify
two bodies as the same algorithm even if they move with different spatial velocities.
It will be achieved by introduction of affine isomorphism of bodies through definition
of inertial reference frame associated with a body so that the external state of a body
will be presented as pair of components: spatial velocity of the body and its spatial
velocity invariant internal state. The point of introducing the notion of inertial reference
frame associated with a body lies in the ability to consider other bodies in relation to
the given one. With reference frames we attempt to develop a language of interaction
between bodies just as the input and output alphabets of finite Mealy automata are for
the interaction between them. The language that we develop is one of the possible and
thus our approach reflects a Poincaré’s conventional point of view on the physical laws.
An example of inertial reference frame is the absolute reference frame O associated
with an immovable body B such that for all t ∈ Z xB(t) = 0, vB(t) = 0, wB(t) = 1,
τB(0) = 0, and, hence, τB(t) = t. Thus, the introduced notions of absolute time, absolute
coordinate and absolute spatial velocity implicitly mean an absolutely motionless body
in relation to which objects were considered. The reference frames associated with the
bodies allow us to make these notions relative.
Let us denote (for a pair of bodies A and B) by xAB(τB), vAB(τB), wAB(τB) and
τAB(τB) the coordinate, the spatial velocity, the proper time velocity and the proper
time of the body A at the moment of time τB in the reference frame OB associated with
the body B, respectively. By definition we assume that xBB(τB) ≡ 0, vBB(τB) ≡ 0,
wBB(τB) ≡ 1 and τBB(τB) = τB.
Definition 4. A body B is called an inertial body if vB(t) and wB(t) are both
constants.
The property to be inertial implies uniform changes of not only spatial coordinates
but also time coordinates. For the sake of simplicity consider the case only the inertial
bodies.
The only restriction imposed on the inertial reference frames is the property that
space-time coordinates of same events in different inertial reference frames are connected
by affine transformation. It follows that a body that is inertial in the absolute inertial
reference frame is inertial in any other inertial reference frame.
Remark 1. It follows that τAB(τB) = τAB(0) + τB · wAB and xAB(τB) = xAB(0) +
τB · vAB for inertial bodies A and B.
For any bodies A and B let us denote by LBA : OB → OA the affine mapping that
156
A state of a dynamic computational structure distributed in an environment
connects OB and OA such that an event (x, τB) in OB coincides with the event LBA(x, τB)
in OA.
These assumptions are sufficient to find out LBA. Without loss of generality we assume
that the origins of both reference frames OA and OB are the same: xBA(0) = 0 and
τBA(0) = 0. Then the mapping LBA is linear. Let us work out the form of transformation
matrix LBA =
(
a11 a12
a21 a22
)
.
The direction of a vector ā is the set of vectors {λ · ā|λ > 0}.
Lemma 1. The vectors
(
1
1
)
and
( −1
1
)
are eigenvectors of the mapping LBA.
Proof. The directions of reference frame axes are imaginary directions in the
event space. But the directions of the vectors
(
1
1
)
and
( −1
1
)
in the absolute
reference frame correspond to the two only possible directions of elementary motions
of elementary bodies going from the reference frame origin and therefore they do not
depend on reference frames. It follows that these directions are invariant by any affine
transformation. ¤
Corollary 2. For the matrix LBA holds a11 = a22 and a12 = a21.
Proof. Based on the lemma 3 the corollary statement follows as a result of
straightforward calculations. ¤
Note that the set of directions of the vectors
(
1
1
)
and
( −1
1
)
is also invariant
under the transformation LBA. It will remain invariant, if we let the transformation LBA
permute the directions. In this case we have a11 = −a22 and a12 = −a21. In physics for
these two situations the different words are used, namely the standard and symmetric
configuration. We consider only the standard configuration, that is a11 = a22 and a12 =
a21, because only the standard configuration satisfies by lemma 3 our requirements to
the inertial reference systems.
Theorem 3. It holds
LBA =
(
1/wBA vBA/wBA
vBA/wBA 1/wBA
)
.
Proof.
Since LBA ·
(
xBB(τBA(τA))
τBA(τA)
)
=
(
xBA(τA)
τA
)
, xBA(τA) = vBA(τA) ·τA, τBA(τA) =
wBA(τA) · τA, xBB(τB) ≡ 0, then LBA ·
(
0
1
)
=
(
vBA/wBA
1/wBA
)
. From it follows that
a12 = vBA/wBA and a22 = 1/wBA. ¤
The following corollaries hold for any intertial bodies A, B, C.
Corollary 4. It holds vAB = −vBA and wAB · wBA = 1− v2
AB = 1− v2
BA.
Proof. The equalities can be derived from LAB · LBA =
(
1 0
0 1
)
. ¤
157
Oleksiy Kurganskyy
Corollary 5. (velocity-addition formula) vCA = vBA+vCB
1+vBAvCB
.
Proof. This velocity-addition formula is derived from the equation LCA = LBA ·LCB.
¤
Corollary 6. (“length contraction/extension” formula) Given inertial bodies A, B
and C such that vAC = vBC . Let ∆x = |xAA(τA)− xBA(τA)| be the distance between
A and B in the reference frame OA. Let ∆x′ = |xAC(τC)− xBC(τC)| be the distance
between A and B in the reference frame OC , then ∆x′ = wCA ·∆x.
Figure 5. Distances between two bodies A and B in Corollary 3
Proof. Notice that the values of ∆x and ∆x′ are constants. Without loss of generality
we assume τAC(0) = τBC(0) = 0, xAC(0) = 0, vAC ≥ 0, xBA ≥ 0. Then xBA(τA) ≡ ∆x
and xBC(0) = ∆x′. Let τA be such a moment of time that the events (xBC(0), 0) =
(∆x′, 0) and (xBA(τA), τA) = (∆x, τA) are the same. Then the formula ∆x′ = wCA ·∆x
of “length contraction” follows from LCA ·
(
∆x′
0
)
=
(
∆x
τA
)
and Theorem 3. ¤
As it will be seen, from the example at the end of this section, wCA may take on a
value which is less than 1 as well as more than 1. So it means that in our discrete model
we have contracting length as well as extending length in respect to different inertial
frame system.
Now we give a definition of internal state of a body. Let for bodies A and B there
be a bijection φ : A → B such that for all b ∈ A elementary bodies b and φ(b) are
isomorphic. We say that A at the moment of proper time τA and B at the moment of
proper time τB are affine isomorphic iff {(φ(b), xbA(τA)|b ∈ A}={(b, xbB(τB)|b ∈ B}.
Definition 5. Two inertial bodies are in the same internal state at some moments of
their proper time iff they are affine isomorphic at their respective proper time.
Internal state of an inertial body does not depend on its spatial velocity in the absolute
reference frame. Thus, the external state of an inertial body can be seen as a combination
of two components: the spatial velocity of the body and its internal state.
If we now consider the body as an automata-like computational structure, whose
states are defined as the internal states, the seemingly natural question whether a body
can determine his own absolute velocity is by definition an algorithmically unsolvable
158
A state of a dynamic computational structure distributed in an environment
Figure 6. The time-space diagrams for the collectives of automata from Examples 1 and 2.
problem or a meaningless question. If body states are by definiton the external states, then
the same question is substanceless, since the external state always contains information
about the absolute velocity.
In order to illustrate the concept of affine isomorphism let us consider bodies A1 and
A2 from the Examples 1 and 2. This bodies are affine isomorphic. The corresponding
transformation of the reference frame O2 of A2 to O1 of A1 is:
(
x′
t′
)
=
(
3
2
1
2
1
2
3
2
)(
x
t
)
−
(
1
2
1
2
)
.
The dynamics of the bodies and illustration of the transformation are shown on
the Figure 6. From the value of transformation matrix and Corollary 3 it follows that
v21 = −v12 = 1/3 w21 = 2/3, w12 = 4/3.
4. Final Remarks. Let us compare the obtained results with formulas of special
relativity theory. It is interesting to have a look, from our model viewpoint, at two
equations ∆t′ = ∆t/
√
1− (v/c)2 of time dilation and ∆x′ = ∆x ·
√
1− (v/c)2 of length
contraction of the special relativity theory. Drawing a proper analogy between them and
τAC(τC)− τAC(0) = wAC · τC (Remark 3) and ∆x′ = wCA ·∆x (Corollary 3) respectively
we can see, due to generally asymmetry wAC 6= wCA in our discrete virtual “world”, that
the coefficient 1/γ =
√
1− (v/c)2 reciprocal to Lorentz factor γ has different “physical”
meanings in these formulas. The factor 1/γ has in the first equations a meaning of the
coefficient wAC and in the second equations has a meaning of the coefficient wCA if we
consider a “moving” A with respect to a “rest” C.
5. Final Conclusion. Not difficult to generalize the approach developed in this
work to the case of finite one-dimensional environments, as well as non-inertial-body
case. However, we can show that for the case of two-dimensional discrete environment
(Cartesian product of two one-dimensional environments) the transformation connecting
two inertial reference frames can not be affine in general. This follows from the fact that
the reference frames are three-dimensional in this case, and affine transformation matrix
159
Oleksiy Kurganskyy
must have exactly four eigenvectors (there are so many different directions of elementary
motions in the two-dimensional discrete enironment by Lemma 3). This fact is one of the
most interesting consequences of this work.
We would like to position this paper from the finite automata theory point of view
as an introductory research work on vague fundamental notion of a state for distributed
computational dynamic structure.
Acknowledgements: The author acknowledges the useful discussions on this work with
Dr. V.Kozlovskyy, Dr. I.Grunsky and Dr. I.Potapov.
1. Toffoli T., A pedestrian’s introduction to spacetime crystallography. IBM J. Res. Dev. 48, 1 (Jan.
2004), 13–29.
2. H. Poincaré, Science et méthode (1908).
3. I. S. Grunskyy, A. N. Kurgansky, Dynamics of collective of automata in discrete environment //
Tr. Inst. Prikl. Mat. Mekh, 15, 50–56 (2007) (in Russian).
4. O. Kurganskyy, Dynamics of a “body” in information environment, The 10th International
Conference “Stability, Control and Rigid Bodies Dynamics” (ICSCD’08). - Donetsk, Ukraine, IAMM
NASU, 2008, p.59.
5. O. Kurganskyy, I. Potapov, A measure of state transition of collective of stateless automata in
discrete environment, arxiv.org, 1–13 (2010).
Курганский А.Н.
Состояние динамической вычислительной структуры, распределенной в среде: модель
и её следствия.
В работе коллектив взаимодействующих в дискретной среде автоматов рассматривается как цель-
ный автоматоподобный вычислительный динамический объект. Для таких распределённых в среде
объектов предлагается метод определения их функциональной эквивалентности, инвариантной от-
носительно динамики.
Ключевые слова: коллектив автоматов, клеточные автоматы, конечные автоматы, специ-
альная теория относительности
Курганський О.М.
Стан динамiчної обчислювальної структури, розподiленої в середовищi: модель i її на-
слiдки.
У роботi колектив взаємодiючих автоматiв з одним станом у дискретному середовищi розглядається
як цiльний автоматоподiбний обчислювальний динамiчний об’єкт. Для таких розподiлених по сере-
довищу об’єктiв пропонується метод визначення їхньої функцiональної еквiвалентностi, iнварiант-
ної щодо динамiки.
Ключовi слова: колектив автоматiв, клiтиннi автомати, теорiя cкiнченних автоматiв, спе-
цiальна теорiя вiдносностi
Ин-т прикл. математики и механики НАН Украины, Донецк
topologia@mail.ru
Received 29.11.2010
160
|