Обратимые клеточные автоматы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

На правах рукописи 005052925 УДК 519"71

Кучеренко Игорь Викторович

ОБРАТИМЫЕ КЛЕТОЧНЫЕ АВТОМАТЫ 01.01.09 — дискретная математика и математическая кибернетика

О 4 ОКТ 2012

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА - 2012

005052925

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

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

профессор Кудрявцев Валерий Борисович

Официальные оппоненты: Гашков Сергей Борисович,

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

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

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

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

доктор физико-математических наук, профессор (Московский государственный университет имени М. В. Ломоносова)

Карташов Сергей Иванович, кандидат физико-математических наук, доцент (Московский государственный университет приборостроения и информатики)

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

«Московский энергетический институт»

профессор

А. О. Иванов

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

Актуальность темы

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

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

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

1 Neumann J., von. Collected works. New York, 1961- 1963.

2 Neumann J., von. Theory of sclf-reproducing automata. Edited and completed by Arthur W. Burks. London, 1966.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9 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, Xй 5, 448-464.

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

11 Kari J. Reversibility of 2D ccllular automata is undecidable. Physica D (1994) 45, 379-385.

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

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

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

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

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

13 Подколзин А. С. О сложности моделирования в однородных структурах. Проблемы кибернетики (1975) 30.

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

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

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

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

Цель работы

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

Научная новизна

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

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

2. Рассмотрено расслоение класса клеточных автоматов с двумя состояниями ячейки (бинарные КА) на классы КА с локальной функцией переходов из некоторого класса Поста. Для решетки замкнутых классов

16 Toffoli Т. Computation and Construction Universality of Reversible Cellular Automata. Journal of Computer and System Sciences (1977) 15, №2, 213-231.

17 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. Исследованы вычислительные возможности множества обратимых клеточных автоматов. Показано, что любой клеточный автомат вкладывается в обратимый КА с увеличением пространства состояний на единицу, но с сохранением числа состояний.

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

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

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

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

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

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

Основные методы исследования

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

Теоретическая и практическая ценность

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

Апробация работы

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

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

Структура и объем диссертации

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

Публикации

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

Краткое содержание работы

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

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

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

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

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

Клеточный автомат а представляет из себя четверку вида {Ък, Еп, V, ср), где — совокупность всех /¿-мерных векторов с целочисленными координатами, Еп — конечное множество из п элементов, природа которых не существенна. Для простоты их можно считать числами из множества {0, 1,..., п — 1}. V = (г>1, У2,..., ьт), т & К,—упорядоченный набор различных ненулевых

векторов из Ък. ср : (Еп)т+1 Еп, с/?(0,0,..., 0) = 0. Элементы множества Ък называются ячейками, Еп — состояниями ячеек, 0 —состояние покоя. При помощи шаблона соседства V каждой ячейке а ставится в соответствие набор векторов У{а) — (а, а + VI, а + у-2,.. ■, а + ут), который называется ее окрестностью. Функция </? называется локальной функцией переходов клеточного автомата. Клеточный автомат, имеющий только два состояния ячейки, называется бинарным.

Функции д Ък ь-> Еп называются состояниями КА. Множество всех состояний обозначается через Еп2 . Основная функция переходов Ф задается как отображение множества всех состояний клеточного автомата а в себя, причем если д = Ф(д'), то для любой ячейки а выполняется д(а) = <р(д'(а),д'(а + У\),д'{а + иг), • ■ • ,д'(а + ьт)). Функционирование КА определяется как последовательность его состояний <7о, <?1,52, ■ • •, получающаяся в результате применения основной функции переходов к некоторому его состоянию до, то есть = Ф(^_1) = Ф((<?о), £ € N. Состояние клеточного автомата, в котором только конечное число ячеек находится в ненулевом состоянии, называется конфигурацией.

При исследовании локальных свойств КА часто приходится рассматривать некоторые подмножества множества ячеек Конечные не пустые множества ячеек клеточного автомата а называются блоками. Конфигурацией блока В называется ограничение некоторого состояния КА на этот блок, то есть функция / : В н-> Еп. Множество всех конфигураций блока В обозначается через Епв. Блок У{В) = и У{а) называется окрестностью блока

сев

В. Ограничение основной функции переходов на блок В приводит к функции Ф|в : Ен-► Епв, которая соответствует изменению конфигурации / блока В в результате функционирования клеточного автомата, а именно Ф|в (/)(а) = <р(/{а), /(а + ы), Да + у2), ..., /(а + <)), Уа € В.

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

не меняющий своего состояния в процессе функционирования.

Обозначим через Va шаблон соседства вида ((1,0), (1,1), (0,1), (—1,1), (—1,0), (—1,-1), (0,-1), (1,-1)). Для двумерного пространства ячеек и шаблона соседства обозначим через СЛа класс клеточных автоматов вида (Z2, Еп, VD, <р). Назовем CAD классом двумерных клеточных автоматов с квадратным шаблоном соседства.

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

Через СА{к,п) обозначим множество клеточных автоматов вида (Zfc, Еп, V, tp). Назовем СА(к,п) классом клеточных автоматов с фиксированным числом состояний.

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

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

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

В теореме 2 установлено, что конструктивного способа проверки на обратимость для класса ВСА(Рг) не существует. Следующее утверждение дает усиление указанного результата

Теорема 4. Свойство обратимости неразрешимо в классе ВСА(/С) тогда и только тогда, когда К D Di.

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

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

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

2. Ур £ Р Р(р) — конечное множество КА, заданных в виде четверок вида {к,п,У,ф).

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

4. Существует алгоритм, который для любого в 6 £" строит р Е Р, такой что я £ Р{р)-

Обозначим через МВ,САз{р) функцию подсчета числа обратимых К А в классах формально N110Аз ■ Р > N0,

ЫВ,СА3{р) = € Р(р)|в — обратимый КА}|.

Теорема 5. Функция подсчета числа обратимых КА NЯСА$(р) относительно конструктивной параметризации для класса КА Б является вычислимой тогда и только тогда, когда в классе Б свойство обратимости является разрешимым.

Обозначим через УТ набор, состоящий из всех ненулевых векторов (г;1, V2,..., V*,..., ик), которые удовлетворяют условию |г>г| ^ г, г = 1, 2,..., к, и упорядочены лексикографически. Через N ЯС А(^п){г), где ЫИСА^п) : N н» обозначим число обратимых клеточных автоматов вида (Ък, Еп, Уг, ф). Назовем Ы11СА^п)(г) функцией роста числа обратимых клеточных автоматов с фиксированным числом состояний ячейки относительно радиуса шаблона соседства.

Теорема 6. Функция роста числа обратимых клеточных автоматов с фиксированным числом состояний ячейки относительно радиуса шаблона соседства ИЯСА^ф) является вычислимой тогда и только тогда, когда либо к = 1, либо п = 1.

Обозначим через N ЕС А^,*у)(п), где ЫЕСА^^у) : N >—> N0, число обратимых клеточных автоматов вида (%к,Еп,У,(р). Назовем N КС А^у){п) функцией роста числа обратимых клеточных автоматов с фиксированным шаблоном соседства относительно числа состояний ячейки. Шаблон соседства V = (г>1, г>2, • • •, г>т), который удовлетворяет следующему условию

Уг, 1 < г < т, Зс е Е\ {0} : ь1 = с-назовем одномерным шаблоном соседства.

Теорема 7. Функция роста NЯСА^*у){п) числа обратимых клеточных автоматов с фиксированным шаблоном соседства относительно числа состояний ячейки является вычислимой тогда и только тогда, когда либо к = 1, либо шаблон соседства V является одномерным.

Обозначим через ЫЯСА{к, п, V) число обратимых клеточных автоматов вида {Ък,Еп,У,у).

Теорема 8. Справедлива следующая оценка

1 „7П+1|

-(п!)" ^ М11СА(к,п,У) ^-¡—

п (пт!)

где т — число векторов в шаблоне соседства V.

Обозначим через МСА^п){г), где ЫСА^^) : N н-> N0, число клеточных автоматов вида (Ък, Еп, УТ, ф). Назовем ЫСА[к,п){т) функцией роста числа клеточных автоматов с фиксированным числом состояний ячейки относительно радиуса шаблона соседства. С ростом г отношение NЯСА^ ^г) И ЛГСЛ(^1п)(г) стремится к нулю. Тем не менее, имеет место следующее утверждение

Теорема 9. Для логарифма функции роста числа обратимых клеточных автоматов ЫКСА^^г) с фиксированным числом состояний ячейки п, п ^ 2, относительно радиуса шаблона соседства выполняется следующее соотношение

1пЛГЯСА^п){г) > 1п(п!) г"^ 1пЫСА(к%п){г) ^ п1п?г

Обозначим через NCA^y^n), где NCA^,*y) N No, число клеточных автоматов вида (Zk,En,V,<f). Назовем NCA^,*y){n) функцией роста числа клеточных автоматов с фиксированным шаблоном соседства относительно числа состояний ячейки. С ростом п отношение NRCA^ty){n) 11 NCA(k,*,v){n) стремится к нулю. Тем не менее, имеет место следующее утверждение.

Теорема 10. Для логарифма функции роста числа обратимых клеточных автоматов NRCА^„у){п) с фиксированным шаблоном соседства относительно числа состояний ячейки выполняется следующее соотношение

In NRCA(k^v){n)

lim —лтТТЛ -Нг = !■

n—oo \nNCA(k,*y)Kn)

Будем говорить, что клеточный автомат а (Е СА(к,п) вкладывается в КА а' € СА(к',п'), если выполняются следующие условия.

1. к ^ к', п ^ п' (полагаем, что Еп С Еп>).

2. Существует Г : R*-' н-> Т — линейный оператор ранга к, такой, что для любой ячейки а, а £ Ък, выполнено Т(а) S Т,к .

3. Для любого начального состояния /о клеточного автомата а существует начальное состояние /д клеточного автомата о' такое, что для любого момента времени i, t G No, и для любой ячейки а, а 6 выполнено Ма) = ФЧ/о)(а) = Ф'Ч/сЖВД) = П(Т{а)).

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

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

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

Далее мы будем часто использовать несколько типов шаблонов, для которых удобно ввести специальные обозначения. Т-шаблоном радиуса I будем называть двумерный шаблон Цт = ((0,-1), (-/,1), (—/ + 1,1),..., (1,1)). Г-шаблоном диаметра I будем называть двумерный шаблон УГ; = ((0,-1), (1,0), (2,0),..., (/, 0)).

Будем считать, что множество ячеек вложено естественным образом в евклидово пространство М^'. Двумерный шаблон соседства V будем называть полуплоскостным, если все его векторы находятся в некоторой полуплоскости. Формально это означает, что для шаблона V существует ненулевой вектор ги е К2, такой, что Уи € V (ги,у) ^ 0, где (•,•)—евклидово скалярное произведение. Следует отметить, что в силу того, что векторы шаблона V имеют целые координаты, всегда можно выбрать вектор ю из X2. Для простоты будем считать, что IV выбран именно таким образом.

Далее нами будет использоваться один подкласс КА специального вида. Пусть состояния клеточного автомата ц представляют из себя пары вида (.х,у), х € Ещ, у 6 ЕП2. Тогда локальную функцию переходов <р можно рассматривать как вектор-функцию {'ф,ф). Будем называть КА // клеточным автоматом с переменной структурой (КАПС), если вторая компонента состояния ячейки не меняется в процессе функционирования ц, то есть ф{{хо, Уо), (Х1, Уг), ■ ■ ■, (хт, ут)) = у0. Для удобства, значение второй компоненты состояния ячейки будем называть основанием, а первой — активным состоянием. Записывать КАПС \х будем в виде пятерки (Ък, ЕЩ,ЕП2, У,ф). В случае, если пх = 2, будем называть КАПС бинарным.

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

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

соседства через УСАХ(2, •).

Теорема 13 .В классе клеточных автоматов УСАХ(2, •) свойство обратимости разрешимо.

Обозначим класс двумерных бинарных линейных КАПС с бинарным основанием и Т-шаблоном соседства (1?, Е2, УТ, ф) через УСАТ(2,2).

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

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

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

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

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

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

Обозначим через СА{2,2, т, <р) множество двумерных бинарных клеточных автоматов с фиксированной локальной функцией переходов ¡р, зависящей от т + 1 переменных. Будем задавать индивидуальные клеточные автоматы из множества СА(2,2,т,ф) набором из т двумерных ненулевых целочисленных векторов V (их шаблоном соседства). Задача алгоритмического распознавания свойства обратимости заключается в построении машины Тьюринга, которая на наборе V = ((жь г/1), (х2, У2), • ■ ■, (хт,Ут)), записанном на ее ленте в виде последовательности из 2 • т натуральных чисел

хи Уіі хг, У2і ■ ■ ■ ут в унитарной записи (отдельные числа разделяются одиночной буквой "О"; в начальном состоянии на всей "свободной" части ленты записана буква "О", головка находится над самой левой буквой "1" конфигурации), останавливается, при этом в ячейке ленты, находящейся под головкой в момент остановки, должна находиться буква "1", если клеточный автомат а = (1?, Е2, V, ср) обратим, или "О", если а не обратим.

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

Теорема 17. Существует булева функция <р(хо, х\,..., хт) с 91 переменной (т = 90) такая, что в классе СА(2,2,т,ір) свойство обратимости алгоритмически не разрешимо.

Теорема 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 automata. 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.

Заказ № 82-А/09/2012 Подписано в печать 24.09.2012 Тираж 100 экз. Усл. п.л. 1

ООО "Цифровичок", тел. (495) 649-83-30 О^п www.cfr.ru ; е-таіі: zak@cfr.ru

Введение

Глава 1. Обратимые клеточные автоматы в функциональных классах.

1.1. Введение.

1.2. Основные результаты главы.

1.3. Неразрешимость свойства обратимости клеточных автоматов в двумерном случае.

1.4. Клеточные автоматы с фиксированным числом состояний ячейки

1.5. Бинарные клеточные автоматы с локальной функцией переходов из класса Поста.

1.6. Невычислимость функции числа обратимых клеточных автоматов относительно конструктивной параметризации.

1.7. Оценки числа обратимых клеточных автоматов. Вычислительные возможности обратимых клеточных автоматов.

Глава 2. Обратимые клеточные автоматы в геометрических классах

2.1. Введение.

2.2. Основные результаты главы.

2.3. Клеточные автоматы с одномерным шаблоном соседства

2.4. Бинарные клеточные автоматы с переменной структурой и полуплоскостным шаблоном соседства.

2.5. Бинарные клеточные автоматы с переменной структурой и Т-шаб-лоном соседства.

2.6. Клеточные автоматы с Г-шаблоном соседства.

2.7. Клеточные автоматы с фиксированным шаблоном соседства

Глава 3. Монофункциональные классы булевых клеточных автоматов с неразрешимым свойством обратимости.

3.1. Введение.

3.2. Основные результаты главы.

3.3. Оценка числа состояний головки МТ с неразрешимой проблемой остановки на унитарных словах.

3.4. Построение монофункционального класса КА с неразрешимым свойством обратимости.

Актуальность темы

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

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

Понятие клеточного автомата возникло в результате усовершенствования модели Дж. фон Неймана [32], [33], [14], предложенной им для описания процессов самовоспроизведения в биологии и технике, и в описанном выше виде использовалось А. Берксом [25], Э. Муром [13], В. Б. Кудрявцевым, А. С. Подколзиным, А. А. Болотовым [1] и другими исследователями. При этом данное понятие описывает достаточно широкий класс отображений — Ричардсон Д. показал, что любое вычислимое однородное отображение множества состояний некоторого клеточного автомата в себя само является клеточным автоматом [34]. т

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

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

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

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

В упомянутой работе [23] была высказана гипотеза, что для многомерных К А свойство обратимости также разрешимо, и даже было предложено попытаться обобщить на них технику одномерного случая. Однако, долгое время прогресса в решении задачи распознавания свойства обратимости многомерных КА не было. Только в девяностые годы финским исследователем Ж. Кари было установлено, что эта задача является алгоритмически неразрешимой [27]. При этом проводились попытки исследовать свойство обратимости двумерных К А на множестве конфигураций, помещающихся в некоторый квадрат. В работе французского исследователя Б. Дюранда было установлено, что задача распознавания обратимости в этой слабой постановке является со-МР-полной [26].

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

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

Детально свойства подобного моделирования были исследованы в работах профессора механико-математического факультета МГУ Подколзина А. С. Им было установлено, в частности, что возможности моделирования без задержки весьма бедны [16]. Относительно же моделирования с задержкой существуют универсальные К А, то есть моделирующие все К А одной с ними размерности [17]. Было установлено существование некоторых простых универсальных клеточных автоматов, в частности, были построены универсальный одномерный КА и универсальный двумерный КА с двумя состояниями ячейки и восемью векторами в шаблоне соседства. В некотором смысле, вся теория клеточных автоматов сводится к изучению свойств этих конкретных КА.

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

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

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

Цель работы

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

Научная новизна

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

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

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

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

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

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

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

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

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

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

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

Основные методы исследования

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

Теоретическая и практическая ценность

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

Апробация работы

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

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

Структура и объем диссертации

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

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

2. Кудрявцев В. Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. Наука, Москва, 1985.

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

4. Кучеренко И. В. О разрешимости обратимости клеточных автоматов. Интеллектуальные системы (2004) 8, № 1-4, 465-482.

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

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

7. Кучеренко И. В. Об условиях разрешимости обратимости булевых клеточных автоматов. Интеллектуальные системы (2007) 11, №1-4, 721-726

8. I. V. Kucherenko. On the number of reversible homogeneous structures. Discrete Mathematics and Applications (2003) 13, №3, 301-305.

9. I. V. Kucherenko. On the structure of the set of reversible cellular automata. Discrete Mathematics and Applications (2007) 17, №5, 495-515.

10. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Москва, Мир, 1979.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва, Мир, 1982.

12. Мальцев А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

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

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

15. Ope О. Теория графов. Наука, Москва, 1980.

16. Подколзин А. С. О сложности моделирования в однородных структурах. Проблемы кибернетики (1975), 30.

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

18. Рогожин Ю. В. Семь универсальных машин Тьюринга. Математические исследования (1982) 69, 76-90.

19. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. Вильяме, Москва, 2002, ISBN 0-201-44124-1.

20. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Наука, Москва, 1966.

21. Яблонский C.B. Введение в дискретную математику. Высшая школа, Москва, 2002.

22. Яблонский C.B., Лупанов О.Б. Дискретная математика и математические вопросы кибернетики. Москва, Наука, 1974, том 1.

23. 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.

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

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

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

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

28. 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.

29. Hopcroft J. E., Motwani R., Ullman J. D. Intoduction to Automata Theory, Languages, and Computation (2nd ed.) Addison-Wesley, 2000, ISBN 0-201-44124-1.

30. Myhill G. A. Converse to Moore's Garden of Eden theorem. Proc. Amer. Math. Soc. (1963) 14.

31. Neary T., Woods D. Four Small Universal Turing Machines, Fundamenta Informaticae (2009) 91, 105-126.

32. Neumann J., von. Collected works. New York, 1961-1963.

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

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

35. Rogozhin Y. Small universal Turing machines. Theoretical Computer Science (1996) 168, №2, 215-240.

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

37. Toffoli T. Computation and Construction Universality of Reversible Cellular Automata. Journal of Computer and System Sciences (1977) 15, №2,303 319.213.231.