Внутреннее и внешнее состояния коллектива автоматов в дискретной

ч. 1
ВНУТРЕННЕЕ И ВНЕШНЕЕ СОСТОЯНИЯ КОЛЛЕКТИВА АВТОМАТОВ В ДИСКРЕТНОЙ СРЕДЕ
А.Н.Курганский
Институт прикладной математики и механики НАНУ, Донецк, Украина
Рассматривается коллектив взаимодействующих с геометрической средой автоматов как единый автоматоподобный вычислительный объект. Затруднительно однозначно определить, что является состоянием такого «размытого» по среде объекта. В отличие от конечных автоматов, где мера изменения состояния равна одному состоянию в единицу времени, для распределенного по среде вычислительного объекта возможны разные подходы к определению меры изменения его состояния. В работе предлагается один из подходов, в котором рассматриваются коллективы только элементарных автоматов, то есть автоматов с одним состоянием. Это позволяет определить состояние коллектива автоматов исключительно на основе взаимного расположения составляющих его элементарных автоматов, т.е. на основе его геометрии. Мера изменения состояния коллектива автоматов названа собственным временем этого коллектива.

Предлагаемая работа затрагивает три области исследований: 1) коллективы автоматов в теории конечных автоматов, 2) дискретные модели физических процессов и проецирование физического мира в информационный мир символов и языков с целью компьютерного моделирования физического мира, 3) изучение понятия времени. По всем трем направлениям существуют обширные списки литературы [2,3,4,5], говорящих об их важности.

В основе работы лежит понятие относительности в понимании, изложенном Пуанкаре в [1]. Способ определения языка (скорость, время, система отсчета), на котором происходит взаимодействие между коллективами автоматов, отражает конвенциональную точку зрения Пуанкаре на физические законы. Заключительное сопоставление полученных результатов со специальной теорией относительности показывает, что сформулированные в работе принципы инвариантны относительно языковых средств выражения: семантическая схожесть исходных принципов, использованных нами в формировании языка коллективов автоматов, с принципами языка специальной теории относительности привела к синтаксической близости этих языков.

Через , и обозначим множества натуральных, целых и действительных чисел. Через и обозначим области изменения времени и координат. Средой является бесконечный ориентированный граф, представленный на рисунке:

Он состоит из множества вершин и дуг . Пусть Дуга имеет координату и направление . Координату дуги обозначаем через , а направление через . Дуга также обозначается через . Две дуги с одинаковыми координатами, но разными направлениями, называются противоположными, а дуги, направленные в одну вершину, – встречными. Дуга и встречная ей образуют окрестность дуги .

Положим . Элементарным телом назовем конечный автомат с одним состоянием, которое назовем внутренним. Говорим, что изоморфные автоматы являются автоматами одного вида, неизоморфные – разного. Пусть имеется всего различных видов автоматов, пронумерованных целыми числами от до . Входным сигналом элементарного тела, находящегося на дуге , является упорядоченный набор чисел , где и – число элементарных тел вида , находящихся соответственно на дугах и . Выходной реакцией элементарного тела является движение: прямолинейное или поворот. Если автомат, находящийся в момент на дуге , делает прямолинейное движение, то в момент он находится на дуге , и мы говорим, что он не изменил свое внешнее состояние. Если автомат делает поворот, то в следующий момент времени он находится на противоположной дуге , и мы говорим, что он изменил свое внешнее состояние. По определению выполняются еще два условия: 1) в каждый момент времени одна из противоположных дуг должна быть пустой, 2) если встречная дуга пуста, то элементарное тело движется прямо.

Из определений следует, что множество входных сигналов элементарного тела разбивается на два подмножества и таких, что элементы множества меняют направление его движения, а элементы из нет. Элементарное тело однозначно определяется множеством .

Через обозначаем дугу, на которой находится элементарное тело в момент времени , а через его координату. Пары пространственных координат и времени называем координатами в абсолютной системе отсчета и обозначаем вектор-столбцами. Абсолютной скоростью в момент времени назовем величину . Скорость назовем равномерной, если константа. Элементарное тело может иметь только одну из равномерных скоростей: , , .

Определение. Телом называется произвольная конечная совокупность элементарных тел. Если элементарное тело принадлежит телу, то говорим о нем, как об элементарной части этого тела. Иногда мы рассматриваем бесконечные совокупности элементарных тел, но эти случаи оговариваются. Если тело представляет собой множество всех элементарных тел среды, то называем его свободным. Определение тела не исключает того, что различные тела могут иметь общие части.

Приведем два примера тел и для иллюстрации последующих определений. В обоих примерах элементарные тела одного вида такого, что входным сигналом элементарного тела в момент времени является пара чисел , где – число элементарных тел в момент на дуге , а – число элементарных тел на встречной дуге. Элементарное тело меняет направление движения тогда и только тогда, когда . В обоих примерах со средой взаимодействует счетное множество элементарных тел. Пронумеруем их целыми числами.

Пример 1. В момент времени элементарное тело находится на дуге , если четное, иначе на дуге . Тогда .

Пример 2. Элементарное тело в момент времени имеет координату . При этом, если , то оно имеет направление , иначе . Тогда .

Определение. Пусть тело состоит из пронумерованных элементарных тел . Абсолютной (средней) координатой тела в момент назовем величину , а его абсолютной скоростью в момент величину . Например, тела и имеют равномерные абсолютные скорости соответственно и .

Координаты тела в общем случае не являются целыми числами. Расширим систему отсчета , координаты которой брались из множества , до множества координат . Пусть и , тогда элементарное тело в момент времени имеет координату и находится на дуге . Если , то говорим, что тело находится в момент времени в вершине среды. Можно говорить, что поведение элементарных тел полностью определяется в вершинах графа среды.

Пусть , , тогда для произвольного тела обозначим . Если произвольное преобразование системы отсчета, то .

Тело, взаимодействуя с другими телами, испытывает влияние с их стороны и само влияет на них. Естественно такое влияние описать состояниями тел. Наша цель определить состояние тела через взаимное расположением в среде его элементарных частей. Если взаимное расположение частей меняется, то характер этого изменения может быть разным, поскольку изменения могут затронуть все тело целиком или только его часть. Отсюда возникает вопрос о мере изменения состояния тела. Итак, нам надо 1) дать определение состояния тела и 2) ввести меру изменения состояния тела с течением абсолютного времени . Меру назовем собственным временем тела. Независимо от того, как мы определим , величину назовем скоростью собственного времени тела в момент времени .

Определение. Тело инерциальное, если и константы.

В силу определений, для любого элементарного тела справедливо: , где , – путь, пройденный за время . Элементарное тело тратит абсолютное время либо на перемещение, либо на смену своего внешнего состояния, то есть на собственное время.

Определение. Для произвольного тела .

Определение. Для произвольного тела .

Таким образом, тело не меняет свое внешнее состояние, если все его элементарные части не меняют свое внешнее состояние.

Теорема. Если , то .

Доказательство следует из того, что при максимальной скорости невозможны изменения внешнего состояния элементарных частей тела.

Введение состояний позволяет рассматривать тела как автоматоподобные модели алгоритмов. Но определение внешнего состояния имеет недостатки. Поскольку два тела с различной абсолютной скоростью заведомо находятся в различных внешних состояниях, то о них трудно пока говорить, как о реализациях возможно одного и того же алгоритма. Чтобы уметь говорить о телах как об одном алгоритме, даже если они перемещаются с различной скоростью, мы введем понятие внутреннего состояния тела, которое будет получено путем расщепления внешнего на две компоненты: скорости тела и его внутреннего состояния.

Рассмотрим два экземпляра и среды . Пусть и абсолютные системы отсчета соответственно в средах и . Пусть и произвольные тела, , соответственно в средах и Говорим, что в среде аффинно изоморфно в среде , если существует аффинное преобразование системы отсчета такое, что . Тела и из примеров выше являются аффинно изоморфными. Соответствующее аффинное преобразование имеет вид:

Аффинно изоморфные тела рассматриваются нами как тела, перемещающиеся с различной скоростью и реализующие один и тот же алгоритм. Аффинный изоморфизм является частным случаем ситуации, представленной дальше понятием внутреннего состояния тела.

Введем понятие инерциальной системы отсчета , связанной с инерциальным телом . Примером такой системы отсчета служит абсолютная система отсчета , условно связанная с произвольным покоящимся инерциальным телом таким, что , , , и, следовательно, , где – собственное время . Системы отсчета, связанные с произвольным инерциальным телом, позволяют сделать эти понятия относительными.

Для произвольных инерциальных тел и обозначим через , , и соответственно координату, скорость перемещения, скорость собственного времени и собственное время тела в момент времени в системе отсчета , связанной с телом . Cобственное время тела по определению является внешним временем в системе отсчета , то есть , , .

Определение. Пусть инерциальные тела и такие, что . Говорим, что внутреннее состояние тела в момент его собственного времени совпадает с внутренним состоянием тела в момент его собственного времени , если . Внутреннее состояние не зависит от скорости тела и является аналогом внешнего состояния, но относительно собственной системы отсчета, а не абсолютной. Таким образом, внешнее состояние тела представляется как сочетание двух компонент: скорости тела и его внутреннего состояния.

Перечислим ниже свойства, которым по определению удовлетворяют инерциальные системы отсчета.

Свойство 1. Пространственно-временные координаты одних и тех же событий в разных инерциальных системах отсчета связаны аффинным преобразованием. Для произвольных инерциальных тел и обозначим через аффинное преобразование, связывающее и таким образом, что всякое событие в системе отсчета совпадает с событием в системе отсчета .

Свойство 2. Так как внутреннее состояние по определению не зависит от скорости, то в любой инерциальной системе отсчета максимальная скорость в обоих направлениях равна или в зависимости от направления. Это то же самое, что сохраняет вид уравнения (иначе, ) «мировой линии» тела , двигающегося с равномерной максимальной скоростью, если . Без ограничения общности нашего одномерного случая полагаем, что положительные направления во всех системах отсчета совпадают.

Введенных условий достаточно, чтобы найти . Не ограничивая общности, полагаем и , чтобы преобразование было линейным. Найдем матрицу этого преобразования .

Поскольку и , , , то . Отсюда , .

Из свойства 2 получаем два равенства: и для некоторых чисел и . Откуда в результате простых вычислений получаем .

Теорема. Выполняются равенства и .

Доказательство. Следует из . Ч.т.д.

Теорема. .

Доказательство. Следует из . Ч.т.д.

Рассмотрим два инерциальных тела и , схематически представленных на рисунке:

Пусть и . Рассмотрим произвольный момент времени . Пусть моменты внутреннего времени тела и такие, что и . Из равенств и следует . Расстоянием между двумя телами и в системе отсчета тела момент времени назовем величину . Из этого определения и предыдущей формулы следует, что расстояния и между телами и соответственно в системах отсчета и в момент внутреннего времени тела связаны формулой . Другими словами, верна

Теорема. Пусть длина некоторого объекта в системе отсчета тела равна и длина того же объекта в системе отсчета тела равна . Тогда

Интересно рассмотреть две формулы из специальной теории относительности: и . Проводя аналогию с изложенными выше результатами, получаем, что коэффициент в первой формуле имеет физический смысл коэффицента , а во второй формуле смысл коэффициента .

В продолжении работы предполагается связать введенные динамические свойства дискретных тел в информационной среде с проблемами в области исследований алгоритмической сложности процессов обработки информации.

Список литературы

1. 
   Пуанкаре А. О науке. - М.: Наука, 1983. - 560 с.
   
2. 
   Г. Килибарда, В.Б. Кудрявцев, Ш.М. Ушчумлич Коллективы автоматов в лабиринтах, Дискретная математика, 2003, 15:3, 3-39.
   
3. 
   Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973. - 408 с.
   
4. 
   Усманов З. Моделирование времени. - М.: Знание, 1991. - 48 с.
   
5. 
   Кандрашова Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах / Под ред. Д.А. Поспелова. – М.: Наука. Гл. ред. физ.-мат. лит., 1989. – 328 с.
   
6. 
   Грунский И.С., Курганский А.Н. Динамика коллектива автоматов в дискретной среде // Труды ИПММ НАНУ, 2007, вып. 15, c. 50 – 56
   
7. 
   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.
   
8. 
   А.Н.Курганский Мера изменения внутреннего состояния коллектива автоматов в дискретной среде // Труды ИПММ НАНУ, 2008, вып. 16, c. 117-123.
   

ч. 1