WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

На правах рукописи

УДК 519.71 Кучеренко

Игорь Викторович ОБРАТИМЫЕ КЛЕТОЧНЫЕ АВТОМАТЫ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА — 2012

Работа выполнена на кафедре Математической теории интеллектуаль­ ных систем Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный консультант: доктор физико-математических наук, профессор Кудрявцев Валерий Борисович

Официальные оппоненты: Гашков Сергей Борисович, доктор физико-математических наук, профессор (Московский государственный университет имени М. В. Ломоносова) Карташов Сергей Иванович, кандидат физико-математических наук, доцент (Московский государственный университет приборостроения и информатики)

Ведущая организация: Национальный исследовательский университет «Московский энергетический институт»

Защита диссертации состоится 26 октября 2012 г. в 16 ч. 45 мин. на за­ седании диссертационного совета Д.501.001.84 при Московском государствен­ ном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ М. В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 26 сентября 2012 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор А. О. Иванов

Общая характеристика работы



Актуальность темы Клеточные автоматы (КА) являются дискретными математическими мо­ делями широкого класса реальных систем вместе с протекающими в них про­ цессами. Важное семейство клеточных автоматов образуют обратимые КА, то есть такие, в которых не происходит потери информации в процессе их функционирования. Эти объекты имеют много приложений, в том числе в вопросах защиты информации.

Содержательно клеточный автомат представляет собой бесконечную ав­ томатную схему, построенную следующим образом. Рассмотрим k-мерное ев­ клидово пространство. Разобьем его на гиперкубы с единичным ребром, реб­ ра которых параллельны осям координат. В каждый гиперкуб поместим один и тот же конечный автомат A с m входами и одним выходом. Разветвим вы­ ход автомата и соединим с входами его соседей одинаковым образом для всех гиперкубов в пространстве. Получим бесконечную однородным образом устроенную автоматную схему, которая и называется клеточным автоматом.

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

Понятие клеточного автомата возникло в результате усовершенствова­ ния модели Дж. фон Неймана1 2 3, предложенной им для описания процессов самовоспроизведения в биологии и технике, и в описанном выше виде исполь­ зовалось А. Берксом4, Э. Муром5, В. Б. Кудрявцевым, А. С. Подколзиным, Neumann J., von. Collected works. New York, 1961– 1963.

Neumann J., von. Theory of self-reproducing automata. Edited and completed by Arthur W. Burks.

London, 1966.

Дж. фон Нейман. Теория самовоспроизводящихся автоматов. Мир, Москва, 1971.

Burks A. Essays on Cellular Automata. University of Illinois Press, 1971.

Мур Э. Ф. Математические модели самовоспроизведения. В кн.: Математические проблемы в биологии. Мир, Москва, 1966.

А. А. Болотовым6 и другими исследователями. При этом данное понятие опи­ сывает достаточно широкий класс отображений — Ричардсон Д. показал, что любое вычислимое однородное отображение множества состояний некоторого клеточного автомата в себя само является клеточным автоматом7.

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

При этом на поведение автомата A в состоянии покоя накладывается следу­ ющее ограничение — если сам автомат и все его соседи, соединенные с его входами, находятся в состоянии покоя, то автомат не меняет своего состоя­ ния. Допускающие такое конечное описание состояния КА называются кон­ фигурациями. Клеточный автомат называется обратимым, если любая его конфигурация имеет не более одного прообраза, являющегося конфигураци­ ей. Клеточный автомат называется сильно обратимым, если любое его состо­ яние имеет единственный прообраз.

Первые исследования обратимых клеточных автоматов относятся к ше­ стидесятым годам двадцатого века. Было замечено, что обратимость эквива­ лентна сюръективности глобальной функции переходов клеточного автомата (теорема «о райском саде» Мура-Майхилла8).

Следующим естественным вопросом, возникшим перед исследователями, стала задача эффективного построения обратимых клеточных автоматов и алгоритмического распознавания свойства обратимости для клеточных авто­ матов. При этом в задаче распознавания свойства обратимости клеточный автомат предполагается заданным конструктивным образом — то есть указа­ нием размерности, описания автомата A и способа соединения автоматов в схеме с соседями.

Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур. Наука, Москва, 1990.

Richardson D. Tesselations with local transformations. Journal of Computer and System Sciences (1972) 5.

Myhill G. A. Converse to Moores Garden of Eden theorem. Proc. Amer. Math. Soc. (1963) 14.

Американскими исследователями С. Аморосо и Ю. Н. Патт было уста­ новлено, что для случая одномерного клеточного автомата задача алгорит­ мического распознавания обратимости является разрешимой, и был построен алгоритм распознавания, имеющий экспоненциальную сложность9. Позже в работе К. Сутнера был построен алгоритм полиномиальной (квадратичной) сложности10.

В упомянутой работе С. Аморосо и Ю. Н. Патт была высказана гипо­ теза, что для многомерных КА свойство обратимости также разрешимо, и даже было предложено попытаться обобщить на них технику одномерного случая. Однако, долгое время прогресса в решении задачи распознавания свойства обратимости многомерных КА не было. Только в девяностые годы финским исследователем Ж. Кари было установлено, что эта задача явля­ ется алгоритмически неразрешимой11. При этом проводились попытки иссле­ довать свойство обратимости двумерных КА на множестве конфигураций, помещающихся в некоторый квадрат. В работе французского исследователя Б. Дюранда было установлено, что задача распознавания обратимости в этой слабой постановке является co-NP-полной.

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

Простейший, а одновременно и один из самых практически ценных, спо­ соб конструктивного моделирования называется взаимным моделированием КА. Этот метод работает для КА одной размерности. Суть его состоит в сле­ дующем — пространство ячеек моделирующего клеточного автомата разбива­ Amoroso S., Patt Y. N. Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. Journal of Computer and System Sciences (1972) 6, № 5, 448–464.

Sutner K. Linear cellular automata and De Bruijn automata. In: Cellular Automata: a parallel model Delorme M., Mazoyer J., Eds.. Kluwer, 1998, 303–319.

Kari J. Reversibility of 2D cellular automata is undecidable. Physica D (1994) 45, 379–385.

Durand B. Inversion of 2D cellular automata: some complexity results. Theoretical Computer Science (1994) 134, № 2, 387–401.

ется на прямоугольные блоки, и состояния ячеек моделируемого КА ассоци­ ируются с некоторым подмножеством состояний этого блока. Через каждые T тактов своего функционирования моделирующий КА должен вычислять следующее состояние ячейки моделируемого КА. Если T = 1 говорят о мо­ делировании без задержки, если T > 1 — о моделировании с задержкой в T тактов.

Детально свойства подобного моделирования были исследованы в рабо­ тах профессора механико-математического факультета МГУ Подколзина А.

С. Им было установлено, в частности, что возможности моделирования без задержки весьма бедны13. Относительно же моделирования с задержкой су­ ществуют универсальные КА, то есть моделирующие все КА одной с ними размерности14. Было установлено существование некоторых простых универ­ сальных клеточных автоматов, в частности, были построены универсальный одномерный КА и универсальный двумерный КА с двумя состояниями ячей­ ки и восемью векторами в шаблоне соседства. В некотором смысле, вся теория клеточных автоматов сводится к изучению свойств этих конкретных КА.

Еще одним известным универсальным клеточным автоматом является игра Конуэя «Жизнь». Этот КА является, пожалуй, самым изученным из всех клеточных автоматов. Для него было построено огромное количество конфигураций, обладающих различным, порой весьма причудливым поведе­ нием. Это исследование позволило доказать универсальность данного клеточ­ ного автомата15.





Еще одной интересной задачей, касающейся внутреннего моделирования, является задача моделирования одних классов КА в других, в частности за­ дача моделирования в обратимых КА. Первый результат о таком моделирова­ нии был получен американским математиком Т. Тофолли, который показал, что произвольный клеточный автомат может быть смоделирован в сильно обратимом клеточном автомате с существенным увеличением числа состоя­ Подколзин А. С. О сложности моделирования в однородных структурах. Проблемы кибернетики (1975) 30.

Подколзин А. С. Об универсальных однородных структурах. Проблемы кибернетики (1978) 34.

Berlecamp E., Conway V., Elwyn R. and Guy R. Winning way for your mathematical plays. Academic Press, 1982, volume 2.

ний и возрастанием размерности на единицу16. В комбинации с результатом А. С. Подколзина этот факт позволяет утверждать наличие универсального двухмерного сильно обратимого КА (универсального для одномерных КА), что в некотором смысле противоречит гипотезе фон Неймана о необходимо­ сти необратимости для универсальных вычислений.

Отметим, что при моделировании по Тофолли размерность КА растет на единицу. Оказалось, что рост размерности не случаен. Любой необратимый КА не может быть смоделирован в сильно обратимом такой же или меньшей размерности. Этот результат был установлен в работе П. Хертлинга17.

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

Научная новизна Результаты работы являются новыми и состоят в следующем.

1. Получен критерий разрешимости свойства обратимости для классов клеточных автоматов размерности k с фиксированным числом состо­ яний ячейки n.

2. Рассмотрено расслоение класса клеточных автоматов с двумя состоя­ ниями ячейки (бинарные КА) на классы КА с локальной функцией пе­ реходов из некоторого класса Поста. Для решетки замкнутых классов Toffoli T. Computation and Construction Universality of Reversible Cellular Automata. Journal of Computer and System Sciences (1977) 15, № 2, 213–231.

Hertling P. Embedding cellular automata into reversible ones. In: Unconventional Models of Computation C.S. Claude, J.Casti, and M.J. Dinneen, Eds., Springer-Verlag, 1998, 243–256.

Поста проведена классификация классов КА на те, в которых свойство обратимости разрешимо, и те, для которых это не так.

3. Исследован вопрос вычислимости числа обратимых клеточных автома­ тов в классе КА относительно конструктивной параметризации. Полу­ чен критерий вычислимости функции роста числа обратимых клеточ­ ных автоматов с фиксированным числом состояний ячейки относитель­ но радиуса шаблона соседства и критерий вычислимости функции роста числа обратимых клеточных автоматов с фиксированным шаблоном со­ седства относительно числа состояний ячейки.

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

5. Исследованы вычислительные возможности множества обратимых кле­ точных автоматов. Показано, что любой клеточный автомат вкладыва­ ется в обратимый КА c увеличением пространства состояний на едини­ цу, но с сохранением числа состояний.

6. Доказана разрешимость свойства обратимости в классе клеточных ав­ томатов с одномерным шаблоном соседства.

7. Рассмотрен специальный подкласс класса клеточных автоматов — кле­ точные автоматы с переменной структурой (КАПС). Во множестве дву­ мерных бинарных линейных КАПС были выделены два граничащих между собой класса, в одном из которых свойство обратимости разре­ шимо, а в другом — нет. На шаблон соседства первого класса наклады­ вается следующее ограничение: все его векторы находятся в некоторой полуплоскости, если к шаблону соседства добавить всего лишь один вектор, который нарушает описанное выше ограничение, то свойство обратимости становится неразрешимым.

8. Построен наиболее простой с геометрической точки зрения класс кле­ точных автоматов, проблема распознавания свойства обратимости в ко­ тором неразрешима. В этом классе все соседи ячейки, от которых она зависит, за исключением одной ячейки, сосредоточены на одной пря­ мой, и число состояний ячейки равно числу n. Установлено, что уже для n = 16 свойство обратимости неразрешимо.

9. Получен критерий разрешимости свойства обратимости в классе кле­ точных автоматов с фиксированным шаблоном соседства.

10. Рассмотрены классы бинарных двумерных клеточных автоматов, име­ ющих фиксированную локальную функцию переходов (в таком классе варьируются исключительно векторы в локальном шаблоне соседства);

такие классы названы монофункциональными. Построен монофункци­ ональный класс двухмерных бинарных КА, в котором задача распозна­ вания свойства обратимости является алгоритмически не разрешимой, и локальная функция переходов зависит от 91 переменной.

Основные методы исследования В работе используются методы теории автоматов, теории алгоритмов, теории вычислимости, теории графов, булевой алгебры, комбинаторики, ма­ тематического анализа, алгебры.

Теоретическая и практическая ценность Работа носит теоретический характер. Полученные в работе результаты и развитые техники представляют интерес для специалистов в теории авто­ матов, математической логике и теории алгоритмов. Исследованные в работе классы клеточных автоматов могут быть использованы при разработке алго­ ритмов шифрования.

Апробация работы Результаты диссертации неоднократно докладывались на семинарах ме­ ханико-математического факультета МГУ им. М. В. Ломоносова: на семина­ ре «Кибернетика и информатика» под руководством профессора В. Б. Куд­ рявцева (2002–2012 гг.), на семинаре «Теория автоматов» под руководством профессора В. Б. Кудрявцева (2004–2012 гг.), на семинаре «Математика. Ки­ бернетика. Информатика.» под руководством профессора В. Б. Кудрявцева, профессора С. В. Алешина, доцента А. А. Часовских и старшего преподава­ теля Г. И. Сыркина (2008 г.), на семинаре «Дискретный анализ» под руко­ водством профессора С. В. Алешина, профессора В. А. Буевича и старшего научного сотрудника М. В. Носова (2006 г.), на семинаре «Математические вопросы кибернетики» под руководством профессора О. Б. Лупанова (20г.).

Они докладывались также на следующих конференциях: X междуна­ родная конференция «Интеллектуальные системы и компьютерные науки» (Москва, 2011 г.), X международный семинар «Дискретная математика и ее приложения» (Москва, 2010 г.), международная конференция студентов, ас­ пирантов и молодых ученых «Ломоносов» (Москва, 2007 г., 2008 г., 2009 г.), научная конференция «Ломоносовские чтения» (Москва, 2007 г., 2008 г., 20г.), международная конференция «Современные проблемы математики, меха­ ники и их приложения» (Москва, 2009 г.), IX международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, 2006 г.), XIV международная конференция «Проблемы теоретической кибернетики», по­ священная 80-летию со дня рождения С. В. Яблонского (Пенза, 2005 г.), XXVI конференция молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова (Москва, 2004 г.), VIII международный семинар «Дис­ кретная математика и ее приложения» (Москва, 2004 г.), конференция «Мате­ матика и безопасность информационных технологий (МаБИТ-03)» (Москва, 2003 г.), V международный конгресс по математическому моделированию (V ICMM) (Дубна, 2002 г.).

Структура и объем диссертации Диссертация состоит из введения и трех глав. Объем диссертации 1страниц. Список литературы содержит 37 наименований.

Публикации Основные результаты диссертации опубликованы в 18 работах автора, список которых приведен в конце автореферата [1–18].

Краткое содержание работы Во введении показана актуальность тематики работы, изложены цели, методы и результаты исследования. Приведен список работ автора, описана структура диссертации и дается ее краткое содержание.

Первая глава работы посвящена исследованию обратимых клеточных автоматов в классах КА с функциональными ограничениями. Основные ре­ зультаты первой главы представлены теоремами 1–11. Первый раздел гла­ вы — вводный, во втором формулируются основные результаты главы. Тре­ тий раздел посвящен доказательству теоремы 1 о неразрешимости свойства обратимости клеточных автоматов в двумерном случае. В четвертом разде­ ле доказывается теорема 2, дающая критерий неразрешимости обратимости в классе клеточных автоматов с фиксированным числом состояний ячейки.

Пятый раздел посвящен доказательству теорем 3 и 4 о классах бинарных клеточных автоматов с локальной функцией переходов из класса Поста. В шестом разделе доказывается критерий невычислимости функции числа об­ ратимых клеточных автоматов относительно конструктивной параметриза­ ции (теорема 5), затем с помощью этого критерия доказываются результаты о невычислимости для случая фиксированного числа состояний и случая фик­ сированного шаблона соседства (теоремы 6 и 7). Последний раздел главы по­ священ доказательствам результатов об оценках числа обратимых клеточных автоматов (теоремы 8, 9, 10) и их вычислительных возможностях (теорема 11).

Вторая глава посвящена исследованию обратимых клеточных автоматов в классах КА с геометрическими ограничениями. Результаты второй главы составляют теоремы 12–16. Первый раздел главы — вводный, во втором фор­ мулируются основные результаты главы. В третьем разделе доказывается теорема 12 о разрешимости свойства обратимости в классе клеточных ав­ томатов с одномерным шаблоном соседства. Следующие два раздела главы посвящены доказательству результатов о клеточных автоматах с перемен­ ной структурой (КАПС). В четвертом разделе доказывается теорема 13 о разрешимости свойства обратимости в классе двумерных бинарных КАПС с полуплоскостным шаблоном соседства. В пятом разделе доказывается теоре­ ма 14 о неразрешимости свойства обратимости в классе двумерных бинарных КАПС с Т-шаблоном соседства. В шестом разделе приводится доказательство теоремы 15 о неразрешимости свойства обратимости в классе клеточных ав­ томатов с Г-шаблоном соседства. В седьмом разделе приводится доказатель­ ство теоремы 16 о неразрешимости свойства обратимости в классе клеточных автоматов с фиксированным шаблоном соседства.

Третья глава посвящена монофункциональным классам булевых клеточ­ ных автоматов с неразрешимым свойством обратимости. Так же как и в предыдущих главах, первые два раздела посвящены введению и формули­ ровкам результатов. В третьем разделе доказывается теорема 18 об оценке числа состояний головки машины Тьюринга (МТ) с неразрешимой проблемой остановки на унитарных словах. В четвертом разделе проводится построе­ ние монофункционального класса булевых двумерных КА с неразрешимым свойством обратимости, локальная функция переходов в котором имеет переменную. Это построение дает доказательство теоремы 17.

Приведем необходимые определения и сформулируем теоремы, составля­ ющие основные результаты работы.

Клеточный автомат представляет из себя четверку вида (Zk, En, V, ), где Zk — совокупность всех k-мерных векторов с целочисленными координата­ ми, En — конечное множество из n элементов, природа которых не существен­ на. Для простоты их можно считать числами из множества {0, 1,..., n - 1}.

V = (v1, v2,..., vm), m N, — упорядоченный набор различных ненулевых векторов из Zk. : (En)m+1 En, (0, 0,..., 0) = 0. Элементы множества Zk называются ячейками, En — состояниями ячеек, 0 — состояние покоя. При помощи шаблона соседства V каждой ячейке ставится в соответствие на­ бор векторов V () = (, + v1, + v2,..., + vm), который называется ее окрестностью. Функция называется локальной функцией переходов клеточ­ ного автомата. Клеточный автомат, имеющий только два состояния ячейки, называется бинарным.

Функции g : Zk En называются состояниями КА. Множество всех k состояний обозначается через EnZ. Основная функция переходов зада­ ется как отображение множества всех состояний клеточного автомата в себя, причем если g = (g), то для любой ячейки выполняется g() = (g(), g( + v1), g( + v2),..., g( + vm)). Функционирование КА опреде­ ляется как последовательность его состояний g0, g1, g2,..., получающаяся в результате применения основной функции переходов к некоторому его состоя­ нию g0, то есть gt = (gt-1) = t(g0), t N. Состояние клеточного автомата, в котором только конечное число ячеек находится в ненулевом состоянии, называется конфигурацией.

При исследовании локальных свойств КА часто приходится рассматри­ вать некоторые подмножества множества ячеек Zk. Конечные не пустые мно­ жества ячеек клеточного автомата называются блоками. Конфигурацией блока B называется ограничение некоторого состояния КА на этот блок, то есть функция f : B En. Множество всех конфигураций блока B обозна­ чается через EnB. Блок V (B) = V () называется окрестностью блока B B. Ограничение основной функции переходов на блок B приводит к функ­ ции |B : EnV (B) EnB, которая соответствует изменению конфигурации f блока B в результате функционирования клеточного автомата, а именно |B (f)() = (f(), f( + v1), f( + v2),..., f( + vm)), B.

Клеточный автомат, основная функция переходов которого инъективна на множестве всех конфигураций, называется обратимым. По теореме Мура­ Майхилла множество обратимых клеточных автоматов совпадает с множе­ ством КА, основная функция переходов которых является сюръективной.

Тривиальным примером обратимого клеточного автомата является КА I, не меняющий своего состояния в процессе функционирования.

Обозначим через V шаблон соседства вида ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)). Для двумерного пространства ячеек и шаб­ лона соседства V обозначим через CA класс клеточных автоматов вида (Z2, En, V, ). Назовем CA классом двумерных клеточных автоматов с квадратным шаблоном соседства.

Теорема 1. В классе клеточных автоматов CA свойство обратимости алгоритмически неразрешимо.

Через CA(k, n) обозначим множество клеточных автоматов вида (Zk, En, V, ). Назовем CA(k, n) классом клеточных автоматов с фиксированным числом состояний.

Теорема 2. В классе клеточных автоматов CA(k, n) свойство обратимо­ сти алгоритмически неразрешимо тогда и только тогда, когда n > 1 и k > 1.

Обозначим через BCA(K) класс бинарных клеточных автоматов (БКА) с локальными функциями переходов, принадлежащими некоторому классу Поста K. Назовем нетривиальным БКА, локальная функция перехода кото­ рого существенно зависит как минимум от двух переменных.

Теорема 3. Нетривиальные обратимые БКА содержатся в тех и только тех классах BCA(K), для которых справедливо K L4.

В теореме 2 установлено, что конструктивного способа проверки на об­ ратимость для класса BCA(P2) не существует. Следующее утверждение дает усиление указанного результата Теорема 4. Свойство обратимости неразрешимо в классе BCA(K) тогда и только тогда, когда K D1.

Обозначим через S некоторое рекурсивное множество КА, заданных в виде четверок вида (k, n, V, ). Мы будем разбивать S на параметрическое семейство множеств. Обозначим через P множество значений параметров.

Рассмотрим отображение F, ставящее в соответствие значению параметра p P множество F (p) S. Будем называть параметризацию конструктив­ ной, если F удовлетворяет следующим ограничениям.

1. P — рекурсивное множество.

2. p P F (p) — конечное множество КА, заданных в виде четверок вида (k, n, V, ).

3. Существует алгоритм вычисления F (p).

4. Существует алгоритм, который для любого s S строит p P, такой что s F (p).

Обозначим через NRCAS(p) функцию подсчета числа обратимых КА в классах F (p), формально NRCAS : P N0, NRCAS(p) = |{s F (p)|s — обратимый КА}|.

Теорема 5. Функция подсчета числа обратимых КА NRCAS(p) относи­ тельно конструктивной параметризации для класса КА S является вы­ числимой тогда и только тогда, когда в классе S свойство обратимости является разрешимым.

Обозначим через Vr набор, состоящий из всех ненулевых векторов (v1, v2,..., vi,..., vk), которые удовлетворяют условию |vi| r, i = 1, 2,..., k, и упорядочены лексикографически. Через NRCA(k,n)(r), где NRCA(k,n) :

N N0, обозначим число обратимых клеточных автоматов вида (Zk, En, Vr, ). Назовем NRCA(k,n)(r) функцией роста числа обратимых клеточных автоматов с фиксированным числом состояний ячейки относительно радиуса шаблона соседства.

Теорема 6. Функция роста числа обратимых клеточных автоматов с фик­ сированным числом состояний ячейки относительно радиуса шаблона сосед­ ства NRCA(k,n)(r) является вычислимой тогда и только тогда, когда либо k = 1, либо n = 1.

Обозначим через NRCA(k,*,V )(n), где NRCA(k,*,V ) : N N0, число об­ ратимых клеточных автоматов вида (Zk, En, V, ). Назовем NRCA(k,*,V )(n) функцией роста числа обратимых клеточных автоматов с фиксированным шаблоном соседства относительно числа состояний ячейки. Шаблон сосед­ ства V = (v1, v2,..., vm), который удовлетворяет следующему условию i, 1 i m, c R {0} : vi = c · v1, назовем одномерным шаблоном соседства.

Теорема 7. Функция роста NRCA(k,*,V )(n) числа обратимых клеточных автоматов с фиксированным шаблоном соседства относительно числа со­ стояний ячейки является вычислимой тогда и только тогда, когда либо k = 1, либо шаблон соседства V является одномерным.

Обозначим через NRCA(k, n, V ) число обратимых клеточных автоматов вида (Zk, En, V, ).

Теорема 8. Справедлива следующая оценка 1 m nm+1! (n!)n NRCA(k, n, V ), n (nm!)n где m — число векторов в шаблоне соседства V.

Обозначим через NCA(k,n)(r), где NCA(k,n) : N N0, число клеточ­ ных автоматов вида (Zk, En, Vr, ). Назовем NCA(k,n)(r) функцией роста числа клеточных автоматов с фиксированным числом состояний ячейки от­ носительно радиуса шаблона соседства. С ростом r отношение NRCA(k,n)(r) и NCA(k,n)(r) стремится к нулю. Тем не менее, имеет место следующее утвер­ ждение Теорема 9. Для логарифма функции роста числа обратимых клеточных автоматов NRCA(k,n)(r) с фиксированным числом состояний ячейки n, n 2, относительно радиуса шаблона соседства выполняется следующее соотношение ln NRCA(k,n)(r) ln(n!) lim.

ln NCA(k,n)(r) n ln n r Обозначим через NCA(k,*,V )(n), где NCA(k,*,V ) : N N0, число кле­ точных автоматов вида (Zk, En, V, ). Назовем NCA(k,*,V )(n) функцией ро­ ста числа клеточных автоматов с фиксированным шаблоном соседства отно­ сительно числа состояний ячейки. С ростом n отношение NRCA(k,*,V )(n) и NCA(k,*,V )(n) стремится к нулю. Тем не менее, имеет место следующее утвер­ ждение.

Теорема 10. Для логарифма функции роста числа обратимых клеточных автоматов NRCA(k,*,V )(n) с фиксированным шаблоном соседства относи­ тельно числа состояний ячейки выполняется следующее соотношение ln NRCA(k,*,V )(n) lim = 1.

n ln NCA(k,*,V )(n) Будем говорить, что клеточный автомат CA(k, n) вкладывается в КА CA(k, n), если выполняются следующие условия.

1. k k, n n (полагаем, что En En ).

2. Существует T : Rk Rk, T — линейный оператор ранга k, такой, что для любой ячейки , Zk, выполнено T () Zk.

3. Для любого начального состояния f0 клеточного автомата существует начальное состояние f0 клеточного автомата такое, что для любого момента времени t, t N0, и для любой ячейки , Zk, выполнено ft() = t(f0)() = t(f0)(T ()) = ft(T ()).

Теорема 11. Любой k-мерный клеточный автомат вкладывается в k + 1-мерный обратимый КА c количеством состояний, равным числу состоя­ ний исходного клеточного автомата.

Рассмотрим класс клеточных автоматов с одномерным шаблоном сосед­ ства.

Теорема 12. В классе клеточных автоматов с одномерным шаблоном со­ седства свойство обратимости алгоритмически разрешимо.

Далее мы будем часто использовать несколько типов шаблонов, для ко­ торых удобно ввести специальные обозначения. Т-шаблоном радиуса l будем называть двумерный шаблон Vl = ((0, -1), (-l, 1), (-l + 1, 1),..., (l, 1)).

Г-шаблоном диаметра l будем называть двумерный шаблон V = ((0, -1), l (1, 0), (2, 0),..., (l, 0)).

Будем считать, что множество ячеек вложено естественным образом в евклидово пространство Rk. Двумерный шаблон соседства V будем называть полуплоскостным, если все его векторы находятся в некоторой полуплоско­ сти. Формально это означает, что для шаблона V существует ненулевой век­ тор w R2, такой, что v V (w, v) 0, где (·, ·) — евклидово скалярное произведение. Следует отметить, что в силу того, что векторы шаблона V имеют целые координаты, всегда можно выбрать вектор w из Z2. Для про­ стоты будем считать, что w выбран именно таким образом.

Далее нами будет использоваться один подкласс КА специального ви­ да. Пусть состояния клеточного автомата µ представляют из себя пары вида (x, y), x En, y En. Тогда локальную функцию переходов можно 1 рассматривать как вектор-функцию (, ). Будем называть КА µ клеточ­ ным автоматом с переменной структурой (КАПС), если вторая компонен­ та состояния ячейки не меняется в процессе функционирования µ, то есть ((x0, y0), (x1, y1),..., (xm, ym)) = y0. Для удобства, значение второй компо­ ненты состояния ячейки будем называть основанием, а первой — активным состоянием. Записывать КАПС µ будем в виде пятерки (Zk, En, En, V, ). В 1 случае, если n1 = 2, будем называть КАПС бинарным.

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

Будем называть бинарный клеточный автомат с переменной структурой линейным, если для любого фиксированного значения переменных основания его локальная функция переходов является линейной функцией. Обозначим класс двумерных бинарных линейных КАПС c полуплоскостным шаблоном соседства через VCA (2, ·).

Теорема 13. В классе клеточных автоматов VCA (2, ·) свойство обрати­ мости разрешимо.

Обозначим класс двумерных бинарных линейных КАПС с бинарным ос­ нованием и Т-шаблоном соседства (Z2, E2, E2, V, ) через VCA(2, 2).

Теорема 14. В классе клеточных автоматов VCA(2, 2) свойство обрати­ мости алгоритмически неразрешимо.

Теорема 13 позволяет предположить, что свойство обратимости разреши­ мо в классах КА с шаблонами, близкими к полуплоскостному. Как оказалось, уже в простейшем случае это предположение оказывается неверным.

С помощью преобразований КА, сохраняющих свойство обратимости, из теоремы 14 автором получено следующее утверждение. Обозначим CA (n) — множество двухмерных КА с n состояниями ячейки и Г-шаблоном соседства V.

Теорема 15. В классе CA (16) свойство обратимости алгоритмически неразрешимо.

Обозначим через CA(k, *, V ) класс k-мерных клеточных автоматов с фиксированным шаблоном соседства V.

Теорема 16. В классе клеточных автоматов CA(k, *, V ) свойство обрати­ мости разрешимо тогда и только тогда, когда шаблон соседства V явля­ ется одномерным.

Обозначим через CA(2, 2, m, ) множество двумерных бинарных клеточ­ ных автоматов с фиксированной локальной функцией переходов , завися­ щей от m + 1 переменных. Будем задавать индивидуальные клеточные ав­ томаты из множества CA(2, 2, m, ) набором из m двумерных ненулевых целочисленных векторов V (их шаблоном соседства). Задача алгоритмиче­ ского распознавания свойства обратимости заключается в построении маши­ ны Тьюринга, которая на наборе V = ((x1, y1), (x2, y2),..., (xm, ym)), запи­ санном на ее ленте в виде последовательности из 2 · m натуральных чисел x1, y1, x2, y2,..., xm, ym в унитарной записи (отдельные числа разделяются одиночной буквой “0”; в начальном состоянии на всей “свободной” части ленты записана буква “0”, головка находится над самой левой буквой “1” конфигура­ ции), останавливается, при этом в ячейке ленты, находящейся под головкой в момент остановки, должна находиться буква “1”, если клеточный автомат = (Z2, E2, V, ) обратим, или “0”, если не обратим.

Автором был получен следующий результат.

Теорема 17. Существует булева функция (x0, x1,..., xm) с 91 перемен­ ной (m = 90) такая, что в классе CA(2, 2, m, ) свойство обратимости алгоритмически не разрешимо.

Теорема 17 получается сведением проблемы обратимости КА к проблеме остановки МТ в специальной постановке.

Теорема 18. Существует машина Тьюринга с 61 состоянием головки и тремя символами на ленте, для которой не разрешима проблема останов­ ки на словах, представляющих из себя наборы из одних единиц, при распо­ ложении головки в начальный момент времени над самой левой единицей слова.

Данная постановка была выбрана так, чтобы максимально уменьшить число переменных функции . Доказательство теоремы 18 получено автором.

Благодарности Автор выражает благодарность своему научному руководителю акаде­ мику Кудрявцеву Валерию Борисовичу за постановку задачи и постоянное внимание к работе.

Публикации автора по теме диссертации 1. Кучеренко И. В. О структуризации класса обратимых клеточных ав­ томатов. Дискретная математика (2007) 19, № 3, 102–121.

2. Кучеренко И. В. Об условиях разрешимости обратимости булевых кле­ точных автоматов. Интеллектуальные системы (2007) 11, № 1–4, 765–768.

3. Кучеренко И. В. О структуризации класса обратимых бинарных кле­ точных автоматов. Интеллектуальные системы (2005) 9, № 1–4, 445–456.

4. Кучеренко И. В. О разрешимости обратимости клеточных автоматов.

Интеллектуальные системы (2004) 8, № 1–4, 465–482.

5. Кучеренко И. В. О числе обратимых однородных структур. Дискрет­ ная математика (2003) 15, № 2, 123–127.

6. I. V. Kucherenko. On the structure of the set of reversible cellular auto­ mata. Discrete Mathematics and Applications (2007) 17, № 5, 495–515.

7. I. V. Kucherenko. On the number of reversible homogeneous structures.

Discrete Mathematics and Applications (2003) 13, № 3, 301–305.

8. Кучеренко И. В. О минимизации монофункциональных классов бинар­ ных клеточных автоматов с неразрешимым свойством обратимости. В кн.:

Материалы X международной конференции «Интеллектуальные системы и компьютерные науки». Механико-математический факультет МГУ, Моск­ ва, 2011, 151–153.

9. Кучеренко И. В. О распознавании свойства обратимости для моно­ функциональных классов бинарных клеточных автоматов. В кн.: Сборник трудов X международного семинара «Дискретная математика и ее прило­ жения». Механико-математический факультет МГУ, Москва, 2010, 370–373.

10. Кучеренко И. В. О разрешимости свойства обратимости для двумер­ ных бинарных клеточных автоматов. В кн.: Тезисы международной конфе­ ренции «Современные проблемы математики, механики и их приложения».

Механико-математический факультет МГУ, Москва, 2009, 361–362.

11. Кучеренко И. В. О разрешимости свойства обратимости для клас­ сов многослойных двумерных бинарных клеточных автоматов. В кн.: Тези­ сы докладов международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009». Механико-математический факультет МГУ, Москва, 2009, 37–38.

12. Кучеренко И. В. О Постовской отделимости разрешимости обратимо­ сти клеточных автоматов. В кн.: Тезисы докладов международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2008».

Механико-математический факультет МГУ, Москва, 2008, 26–27.

13. Кучеренко И. В. О разрешимости обратимости для однородных струк­ тур. В кн.: Материалы XIV международной конференции «Проблемы теоре­ тической кибернетики». Механико-математический факультет МГУ, Моск­ ва, 2005, 83–84.

14. Кучеренко И. В. Об обратимых клеточных автоматах. В кн.: Матери­ алы VIII международного семинара «Дискретная математика и ее прило­ жения». Механико-математический факультет МГУ, Москва, 2004, 183–186.

15. Кучеренко И. В. О свойстве обратимости бинарных клеточных авто­ матов. В кн.: Тезисы докладов XXVI конференции молодых ученых механико­ математического факультета МГУ им. М. В. Ломоносова. Механико-мате­ матический факультет МГУ, Москва, 2004, 71.

16. Кучеренко И. В. О свойстве обратимости бинарных клеточных авто­ матов. В кн.: Труды XXVI конференции молодых ученых механико-матема­ тического факультета МГУ им. М. В. Ломоносова. Механико-математиче­ ский факультет МГУ, Москва, 2004, 155–157.

17. Кучеренко И. В. Обратимые клеточные автоматы. В кн.: Материалы конференции «Математика и безопасность информационных технологий (МаБИТ-03)». МЦНМО, Москва, 2004, 270–271.

18. I. V. Kucherenko. Estimate of the Number of Reversible Homogeneous Structures. In: V International congress of mathematical modeling (V ICMM).

Book of abstracts. Янус-К, Москва, 2002, Т. 2, 100.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.