Мера изменения внутреннего состояния коллектива автоматов в дискретной среде
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2008
|
| Schriftenreihe: | Труды Института прикладной математики и механики НАН Украины |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/19990 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Мера изменения внутреннего состояния коллектива автоматов в дискретной среде / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 117-123. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-19990 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-199902011-05-20T12:04:29Z Мера изменения внутреннего состояния коллектива автоматов в дискретной среде Курганский, А.Н. 2008 Article Мера изменения внутреннего состояния коллектива автоматов в дискретной среде / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 117-123. — Бібліогр.: 5 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/19990 519.7 ru Труды Института прикладной математики и механики НАН Украины Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| format |
Article |
| author |
Курганский, А.Н. |
| spellingShingle |
Курганский, А.Н. Мера изменения внутреннего состояния коллектива автоматов в дискретной среде Труды Института прикладной математики и механики НАН Украины |
| author_facet |
Курганский, А.Н. |
| author_sort |
Курганский, А.Н. |
| title |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| title_short |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| title_full |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| title_fullStr |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| title_full_unstemmed |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| title_sort |
мера изменения внутреннего состояния коллектива автоматов в дискретной среде |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2008 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/19990 |
| citation_txt |
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 117-123. — Бібліогр.: 5 назв. — рос. |
| series |
Труды Института прикладной математики и механики НАН Украины |
| work_keys_str_mv |
AT kurganskijan meraizmeneniâvnutrennegosostoâniâkollektivaavtomatovvdiskretnojsrede |
| first_indexed |
2025-07-02T20:43:33Z |
| last_indexed |
2025-07-02T20:43:33Z |
| _version_ |
1836569343963430912 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 16
УДК 519.7
c©2008. А.Н. Курганский
МЕРА ИЗМЕНЕНИЯ ВНУТРЕННЕГО СОСТОЯНИЯ КОЛЛЕКТИВА
АВТОМАТОВ В ДИСКРЕТНОЙ СРЕДЕ
В работе предложен подход к определению меры изменения внутреннего состояния коллектива
автоматов, взаимодействующих с одномерной дискретной средой. Мера изменения внутреннего
состояния коллектива автоматов названа внутренним временем. Численное значение внутреннего
времени выводится из определений скорости перемещения тела и системы отсчета, связанной с
телом.
Введение. Проблематика, касающаяся коллективов автоматов, обширна. На-
пример, в [1] представлена проблематика, связанная с коллективами автоматов в ла-
биринтах. В настоящей работе предлагается подход к определению и количественно-
му измерению изменения внутреннего состояния коллектива автоматов, взаимодей-
ствующих с одномерной дискретной средой, на основе динамических характеристик
таких, как координаты, время и скорость коллектива автоматов. В работе рассмат-
риваются автоматы с одним состоянием, двумя выходными сигналами: прямолиней-
ное движение и поворот, и входными сигналами, характеризующими окрестность
вершины, в которой находится автомат. Коллектив автоматов в работе называется
телом, а автомат – элементарным телом или элементарной частью тела. В рабо-
те вводится понятие внутреннего состояния тела, которое определяется взаимным
расположением в среде составляющих тело элементарных частей, то есть геометри-
ей тела в среде. Таким образом, тело является автоматоподобной вычислительной
моделью. Более строго состояние тела в среде определяется следующим образом.
Среда представляет собой множество точек и тело представляется как подмноже-
ство точек среды. Пусть зафиксировано некоторое семейство отображений среды
в себя. Тогда говорим, что два тела находятся в одном и том же состоянии, если
какое-либо отображение из семейства переводит одно тело в другое. Таким обра-
зом, состояние является инвариантом рассматриваемого семейства преобразований
среды. В нашем случае элементарного тела его внутреннее состояние меняется, если
оно меняет направление движения, то есть делает поворот. Аналогично для произ-
вольного тела: если все его элементарные части перемещаются в прямолинейном
направлении, то тело не меняет своего состояния. Мера изменения состояния тела
называется внутренним временем тела. Определение численного значения внутрен-
него времени является задачей данной работы. Заранее можно сказать, что задача
не имеет однозначного решения и требует определений, фиксирующих точку зрения.
Для ее решения в начале работы вводятся понятия скорости внутреннего времени,
координаты тела, скорости перемещения тела в среде, и ставится вопрос о том, когда
можно говорить о равенстве, точнее, изоморфизме двух тел, имеющих различную
скорость. Ответ на этот вопрос можно дать только формальным определением изо-
117
А.Н. Курганский
морфизма. В работе оно дается с помощью системы отсчета, связанной с телом,
и которая является правилом определения пространственно-временных координат
других тел, рассматриваемых относительно данного. В заключение выводится фор-
мула для внутреннего времени тела.
1. Среда. Через Z обозначаем множество целых чисел, Q – множество раци-
ональных, R – множество действительных. Cредой является, в общем случае, ко-
нечный или бесконечный граф с отмеченными дугами. В статье рассматривается
следующая пространственная одномерная среда. Множеством вершин среды явля-
ется E = {−1, 1} × Z, множество дуг состоит из множества
{((−1, x), (−1, x− 1))|x ∈ Z} ∪ {((1, x), (1, x + 1))|x ∈ Z}
дуг прямолинейного движения и множества
{((−1, x), (1, x))|x ∈ Z} ∪ {((1, x), (−1, x))|x ∈ Z}
дуг поворотов. По определению вершина (i, x) ∈ E имеет пространственную коор-
динату x.
В статье изучается взаимодействие элементарных тел с абсолютной средой. С
этой целью введем дискретную временную координату T , принимающую целочис-
ленные значения. Время T будем называть внешним или абсолютным.
2. Тела. Элементарным телом назовем автомат с одним состоянием. Говорим,
что изоморфные автоматы имеют одинаковые цвета, неизоморфные – разные. Пусть
имеется всего r различных цветов. Входным сигналом элементарного тела, нахо-
дящегося в вершине (i, x) среды, является два набора из r чисел (p1, p2, . . . , pr) и
(q1, q2, . . . , qr), где pk и qk – число элементарных тел цвета k, находящихся соответ-
ственно в вершинах (i, x) и (−i, x) среды. Выходом элементарного тела является
движение: прямолинейное или поворот. Таким образом, в каждый момент времени
каждое элементарное тело получает входной сигнал и согласно ему и своей функции
выходов делает движение по среде. Исключением для всех элементарных тел явля-
ется ситуация, когда в вершине находится одно единственное элементарное тело. В
этом случае оно движется всегда в прямолинейном направлении, то есть не меняет
своего внутреннего состояния. На самом деле при таком определении взаимодей-
ствия нет необходимости в выходных символах автомата. А именно, для каждого
вида элементарных тел множество входных наборов разбивается на два непересе-
кающихся подмножества, и считается, что элементы одного множества никак не
влияют на автомат, а элементы другого меняют направление его движения. Вообще
говоря, мы не акцентируем внимание на данном конкретном определении взаимо-
действия автоматов и среды, это один из возможных примеров. Нам достаточна
общая идея, которая позволяет развить предложенную ниже точку зрения на дина-
мические характеристики тел.
Через x(T ) будем обозначать пространственную координату элементарного тела
в момент времени T , при этом будем при необходимости использовать нижний ин-
декс для указания на элементарное тело. Пары (x, T ) пространственных координат
и внешнего времени будем называть координатами в абсолютной системе отсчета O.
118
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде
Скоростью элементарного тела в абсолютной системе отсчета в момент времени
T назовем величину V (T ) = x(T + 1)− x(T ). Скорость в абсолютной системе отсче-
та мы будем также называть абсолютной. Заметим, что мы сейчас рассматриваем
ситуацию, когда наименьший отличный от нуля промежуток времени равен 1. Ско-
рость назовем равномерной, если V (T ) константа. Очевидно, что элементарное тело
может иметь только одну из следующих равномерных скоростей: V = 1, V = −1,
V = 0.
Определение. Телом называется произвольная совокупность элементарных тел.
Если элементарное тело принадлежит некоторому телу, то будем говорить о нем,
как об элементарной части этого тела.
Пусть τ = {τ i : {−1, 1} × Z → {−1, 1} × Z|i ∈ Z} – семейство отображений
вершин среды в себя такое, что τ i(p, z) = (p, z + i · p).
Определение. Будем говорить, что тело B в момент времени T и тело B′ в
момент времени T ′ находятся в одном состоянии, если существует отображение из
семейства τ , которое переводит одно тело в другое. Таким образом, состояние тела
определяется как инвариант определенного вида преобразований.
Определение. Меру изменения внутреннего состояния тела с течением внешнего
времени назовем внутренним временем тела.
Внутреннее время t = t(T ) произвольного тела является по определению неубы-
вающей функцией. Скоростью внутреннего времени тела в момент внешнего време-
ни T назовем величину W (T ) = t(T )− t(T − 1).
Пусть тело B состоит из n элементарных тел, пронумерованных числами
{1, 2, . . . , n}. Координатой тела B в момент времени T в абсолютной системе от-
счета назовем величину
xB(T ) =
x1(T ) + . . . + xn(T )
n
.
Отсюда скорость определяется через координаты тела в точности, как это сделано
для элементарных тел. Из определений следует, что максимально возможная поло-
жительная скорость тела равна 1, минимально возможная скорость равна −1. Если
тело движется со скоростью 1 или −1, будем говорить, что оно движется с макси-
мальной скоростью. Определение координаты тела является частью абстрактного
языка взаимодействия между телами. Поясним эту фразу следующим образом. Для
двух взаимодействующих тел не имеет смысла понятие координаты тела, поскольку
место положения тела в среде определяется множеством всех координат, соответ-
ствующих его элементарным частям, то есть определение координаты в абсолютной
системе отсчета является условным усреднением, ”абстракцией” с ”точки зрения”
тел. Она позволяет ввести понятие скорости, и при рассмотрении инерциальных
тел, определенных ниже, оправдана привычным смыслом слов.
Определение тела не исключает ситуацию, когда тело состоит из двух тел таких,
что одно из них движется с максимальной скоростью в одном направлении, а другое
с максимальной скоростью в другом. По нашему определению скорость внутреннего
119
А.Н. Курганский
времени и скорость перемещения такого ”растягивающегося” с максимальной скоро-
стью тела равна 0. Мы упростим нашу задачу и будем рассматривать только тела
с постоянной скоростью перемещения, постоянной скоростью внутреннего времени
и такие, постоянная скорость внутреннего времени которых является максималь-
но возможной при данной скорости перемещения и множестве составляющих тело
элементарных тел. Такие тела назовем инерциальными. Для инерциального тела
выполняется x(T ) − x(0) = V T , t(T ) − t(0) = WT , где V – скорость перемещения,
а W – скорость его внутреннего времени. По определению полагаем, что внутрен-
нее время покоящегося инерциального тела совпадает с внешним, то есть из V = 0
следует W = 1.
Из определений следует простая теорема.
Теорема. Скорость внутреннего времени движущегося с максимальной скоро-
стью (не только инерциального) тела равна 0.
Как мы видим, внутреннее время тела зависит от его скорости. Конкретный вид
этой зависимости, вообще говоря, является делом определения. Наша цель опреде-
лить ее так, чтобы она была естественной с точки зрения тел, рассматриваемых
как реализации алгоритмов. Примером естественного и интересного алгоритма для
тела является определение скоростей в абсолютной системе отсчета взаимодейству-
ющих с ним других тел и своей собственной абсолютной скорости. В связи с этой
задачей определения скоростей возникает сразу несколько вопросов. Возможно ли
вообще тело, выполняющее такой алгоритм? Перед тем, как ответить на этот во-
прос, разберемся с тем, например, как должен быть представлен выход алгоритма,
реализуемого телом, другими словами, как определить аналог выходной ленты ма-
шины Тьюринга? Здесь по определению будем считать, что результатом работы
алгоритма является состояние тела. То есть среди всех состояний тела мы выделим
заключительные, которыми будут закодированы результаты работы алгоритма. Да-
лее возникает еще один интересный вопрос. В каких случаях можно говорить, что
два тела с различной скоростью перемещения выполняют один и тот же алгоритм?
Когда можно говорить, что тела находятся в одном и том же состоянии, если они
имеют различные скорости? Здесь возможны два ответа. Если задача движения с
данной скоростью является частью алгоритма и принципиально осуществима в рас-
сматриваемой модели взаимодействия автоматов со средой, то задача определения
собственной скорости является тривиальной, и мы не можем в общем случае срав-
нивать два тела с различной скоростью как две идентичные реализации одного и
того же алгоритма. Этот подход в настоящей работе нас не интересует, и нашей
целью является подходящее определение изоморфности двух тел независимо от их
скорости. В этом случае задача определения собственной абсолютной скорости те-
ряет свой смысл, вернее, с точки зрения автора, пишущего статью, как внешнего
наблюдателя взаимодействия тела и среды, тело имеет абсолютную скорость, но
с точки зрения тела, как внутреннего наблюдателя взаимодействия, это понятие
абсолютной скорости не имеет смысла. Вопрос, удовлетворяет ли введенный нами
пример взаимодействия тел и среды данному требованию, является в настоящей
работе открытым.
120
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде
Для определения идентичности, точнее сказать, изоморфизма двух тел вне за-
висимости от их скорости введем понятие системы отсчета.
3. Системы отсчета. Координаты тела в общем случае не являются целы-
ми числами. Мы расширим абсолютную систему отсчета O, координаты которой
брались из множества Z × Z, до множества координат R × R. Множество R × R
представляет собой линейное пространство, элементы которого мы будем называть
событиями и обозначать вектор-столбцами. Пара
((
1
0
)
,
(
0
1
))
является бази-
сом абсолютной системы отсчета.
Далее в этом разделе будет дано определение инерциальной системы отсчета
OB, связанной с инерциальным телом B, имеющим скорость перемещения V и ско-
рость изменения внутреннего времени W . Например, абсолютная система отсчета
O является инерциальной системой отсчета, связанной с произвольным покоящим-
ся инерциальным телом таким, что его координата x(T ) = 0 и внутреннее время
t(T ) = T + t(0).
Определим смысл вводимого понятия. Инерциальная система отсчета, связанная
с инерциальным телом B, должна определять внешнее время и пространственные
координаты тел, рассматриваемых относительно B. Внутреннее время тела B по
определению является внешним временем в системе отсчета OB. Выше мы опреде-
лили внутреннее время, как некоторую меру изменения состояний тела с течением
внешнего времени в абсолютной системе отсчета. Одно из условий, которым долж-
на удовлетворять инерциальная система отсчета и внутреннее время, заключается
в том, что внутреннее время тел не должно зависеть от системы отчета, а скорость
внутреннего времени в инерциальной системе отсчета должна зависеть только от
скорости перемещения в этой системе отсчета. Установив взаимооднозначное соот-
ветствие между координатами одного и того же события в системах отсчета O и OB,
мы определим тем самым и внутреннее время тела в OB.
Ниже перечислены свойства, которыми должна обладать по определению инер-
циальная система отсчета, связанная с инерциальным телом B:
1) координаты одних и тех же событий в разных инерциальных системах отсчета
должны быть связаны линейным преобразованием,
2) скорость тела B в связанной с ним системе отсчета OB равна 0,
3) внутреннее время тела B в системе отсчета OB является внешним для тел,
рассматриваемых относительно OB,
4) внутреннее время тела не должно зависеть от системы отсчета, относительно
которого оно рассматривается, а скорость внутреннего времени в системе отсчета
должна зависеть только от абсолютного значения скорости перемещения в этой си-
стеме,
5) эталоном скорости в инерциальной системе отсчета по определению является
абсолютное значение максимальной скорости, которое принимается за 1.
Определение. Два инерциальных тела B и C изоморфны, если существует такое
взаимооднозначное, сохраняющее цвета, соответствие ϕ : B → C между их элемен-
тарными частями, что xb(T ) = xϕ(b)(T ) для всех T и b ∈ B, где xb(T ) – координата
121
А.Н. Курганский
в системе отсчета OB, а xϕ(b)(T ) – координата в системе отсчета OC .
Будем говорить, что два инерциальных тела реализуют один и тот же алгоритм,
если в начальный момент времени они изоморфны.
Пусть тело B имеет равномерную скорость перемещения V , скорость изменения
внутреннего времени W , координату 0 и внутреннее время 0 в момент T = 0 в абсо-
лютной системе отсчета. Пусть AB линейное преобразование OB в O, связывающее
координаты тела в абсолютной системе отсчета O и инерциальной системе отсчета
OB. Отсюда, система отчета OB определяется базисом
(
AB
(
1
0
)
, AB
(
0
1
))
. Та-
ким образом, событие
(
x′
T ′
)
в системе отчета OB и событие AB
(
x′
T ′
)
=
(
x
T
)
в системе отчета O совпадают.
Найдем матрицу линейного преобразования AB =
(
a11 a12
a21 a22
)
.
Из условий 2 и 3 для систем отсчета следует, что AB переводит
(
0
1
)
в вектор
(
V
W
1
W
)
. Отсюда a12 = V
W и a22 = 1
W .
Из условия 4 следует, что
(
a11
V
W
a21
1
W
)(
a′11
−V
W
a′21
1
W
)
=
(
1 0
0 1
)
.
Отсюда получаем
AB =
(
1
W
V
W(
1
W 2 − 1
) · W
V
1
W
)
.
Из условия о максимальных скоростях для инерциальных систем отсчета полу-
чаем два равенства:
AB
(
1
1
)
=
(
α
α
)
, AB
( −1
1
)
=
( −β
β
)
,
для некоторых чисел α и β. Откуда в результате простых вычислений получаем
AB =
(
1
W
V
W
V
W
1
W
)
.
Сравнивая две формулы для AB, получаем равенство W 2 = 1 − V 2. Таким об-
разом, мы вывели формулу для скорости внутреннего времени. Еще один пример
меры внутреннего времени для инерциальных тел предложен в [5].
1. Килибарда Г., Кудрявцев В.Б., Ушчумлич Ш.М. Коллективы автоматов в лабиринтах, Дис-
кретная математика, 2003, 15:3, С.3-39.
2. Пуанкаре А. О науке. – М.: Наука, 1983. – 560с.
3. Усманов З. Моделирование времени. – М.: Знание, 1991. – 48с.
122
Мера изменения внутреннего состояния коллектива автоматов в дискретной среде
4. Курганский А.Н. Неотличимость конечных автоматов относительно некоторых сред // Кибер-
нетика и системный анализ. – 2001. – N1. – С.43-55.
5. Грунский И.С., Курганский А.Н. Динамика коллектива автоматов в дискретной среде // Труды
ИПММ НАНУ, 2007, вып.15, С.50-56.
Ин-т прикл. математики и механики НАН Украины, Донецк
math@iamm.ac.donetsk.ua
Получено 30.04.08
123
содержание
Том 16
Донецк, 2008
Основан в 1997г.
содержание
Том 16
Донецк, 2008
Основан в 1997г.
|