Автоматные счетчиковые машины (190,00 руб.)

Стр.1

Стр.2

Стр.3

Министерство образования и науки Российской Федерации Ярославский государственный университет им. П.Г. Демидова Е.В. Кузьмин, В.А. Соколов Автоматные счетчиковые машины Монография Ярославль 2 0 1 2

Стр.1

УДК 519.7 ББК З97+В1 К89 Рецензенты: доктор технических наук, профессор Д.О. Бытев; кафедра теории и методики обучения информатике ЯГПУ им. К.Д. Ушинского Кузьмин, Е.В. Автоматные счетчиковые машины: монография / К89 Е.В. Кузьмин, В.А. Соколов; Яросл. гос. ун-т. им. П. Г. Демидова. — Ярославль: ЯрГУ, 2012. — 160 с. ISBN 978-5-8397-0893-8 Монография посвящена автоматным счетчиковым машинам и тем формальным языкам, которые способны распознавать/задавать эти абстрактные математические машины. Приведенные здесь результаты представляют интерес как для теории формальных моделей вычислений, так и для теории формальных языков, поскольку автоматные счетчиковые машины (и соответственно их языки) занимают особое положение в иерархии формализмов в границах от конечных автоматов до машин Тьюринга (счетчиковых машин Минского). Свойства автоматных счетчиковых машин изучаются с привлечением теории правильных квазипорядков и теории вполне структурированных систем переходов, которые оказываются полезными для решения задач анализа семантических свойств различных формальных моделей, являющихся более слабыми по вычислительной мощности (выразительной способности), чем машины Тьюринга. Предназначена для специалистов в области формальных языков и моделей вычислений.Может быть использована студентами старших курсов, магистрантами и аспирантами, специализирующимися в области теоретической информатики и прикладной математики. Рис. 50. Библиогр.: 40 назв. ОГЛАВЛЕНИЕ Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Гл а в а 1. Счетчиковые машины. . . . . . . . . . . . . . . . . . . . . . . 6 1.1.Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.Алгоритмические проблемы. . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3. Счетчиковые машины Минского . . . . . . . . . . . . . . . . . . . . . 19 Гл а в а 2. Двухсчетчиковые машины . . . . . . . . . . . . . . . . . . . 36 2.1.Неразрешимые проблемы и метод сведения . . . . . . . . . . . . . 36 2.2.Двухголовочные автоматы. . . . . . . . . . . . . . . . . . . . . . . . . . 52 Гл а в а 3. Однорегистровые машины . . . . . . . . . . . . . . . . . . . 59 3.1.Однорегистровые машины . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.2. Теоремы по проблеме «входа» . . . . . . . . . . . . . . . . . . . . . . . 71 3.3. Теоремы по проблеме «выхода» . . . . . . . . . . . . . . . . . . . . . . 78 3.4.О вычислимых функциях . . . . . . . . . . . . . . . . . . . . . . . . . . 83 УДК 519.7 ББК З97+В1 Гл а в а 4. Структурированные системы переходов. . . . . . . . . 89 4.1.Квазипорядок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.2. Структурированные системы переходов . . . . . . . . . . . . . . . . 93 4.3.Автоматные системы переходов . . . . . . . . . . . . . . . . . . . . . . 103 ISBN 978-5-8397-0893-8 Гл а в а 5. Автоматные счетчиковые машины. . . . . . . . . . . . . 109 5.1. Слабые счетчиковые машины . . . . . . . . . . . . . . . . . . . . . . . 109 5.2.Автоматные счетчиковые машины . . . . . . . . . . . . . . . . . . . . 119 5.3.Автоматные трехсчетчиковые машины. . . . . . . . . . . . . . . . . 128 - Е.В. Кузьмин, В.А. Соколов, 2012 - Ярославский государственный университет им. П. Г. Демидова, 2012 c c Гл а в а 6. Языки автоматных счетчиковых машин . . . . . . . . 135 6.1.Автоматная счетчиковая машина-распознаватель . . . . . . . . . 135 6.2.Проблемы пустоты и распознавания слов. . . . . . . . . . . . . . . 137 6.3. Свойства замкнутости. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.4.Проблемы включения и равенства языков . . . . . . . . . . . . . . 149 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

Стр.2

Предисловие 5 Предисловие Монография посвящена автоматным счетчиковым машинам и тем формальным языкам, которые способны распознавать/задавать эти абстрактные математические машины. Приведенные здесь результаты представляют интерес как для теории формальных моделей вычислений, так и для теории формальных языков, поскольку автоматные счетчиковые машины (и соответственно их языки) занимают особое положение в иерархии формализмов в границах от конечных автоматов до машин Тьюринга (счетчиковых машин Минского). Свойства автоматных счетчиковых машин изучаются с привлечением теории правильных квазипорядков и теории вполне структурированных систем переходов, которые оказываются полезными для решения задач анализа семантических свойств различных формальных моделей, являющихся более слабыми по вычислительной мощности (выразительной способности), чем машины Тьюринга. Основные новые результаты, приведенные в этой монографии, касаются главным образом языков автоматных счетчиковых машин и представляют собой следующее. В монографии определен и исследован класс языков, допускаемых автоматными счетчиковыми машинами. Доказано, что этот класс замкнут относительно операций объединения, пересечения, конкатенации, бесконечной итерации, гомоморфизма и обратного гомоморфизма, т. е. является полным абстрактным семейством языков. Также установлено, что класс языков автоматных счетчиковых машин (ЯАСМ) замкнут относительно полной подстановки, но незамкнут относительно дополнения и операции обращения. Доказано, что для класса ЯАСМ разрешимы проблемы пустоты и распознавания слова языка, заданного автоматной счетчиковой машиной, но неразрешимы проблемы включения и равенства языков. Проведено сравнение с другими классами языков — регулярными, контекстно-свободными, контекстно-зависимыми языками и языками сетей Петри. Установлено, что класс АСМ-языков включает в себя регулярные языки, несравним по включению с классом контекстно-свободных языков и классом языков сетей Петри, но полностью входит в класс контекстно-зависимых языков. Кроме результатов, связанных с автоматными счетчиковыми машинами, в монографии приводятся предварительные сведения по теории счетчиковых машин — абстрактных математических моделей вычислений. Затрагиваются интересные факты из теории вычислимости. Например, в первой главе дается определение машины Тьюринга как формализации интуитивного понятия алгоритма и приводится ее пример. С точки зрения понятия «массовых алгоритмических проблем» обсуждаются разрешимые и неразрешимые проблемы для машин Тьюринга. Приводятся доказательства теорем о неразрешимости проблем «остановки» и «зацикливания». Далее описывается другой вид абстрактных математических машин — счетчиковые машины Минского. Показывается, что любую машину Тьюринга можно смоделировать машиной Минского всего лишь с тремя счетчиками. Более того, любая трехсчетчиковая машина Минского моделируется машиной Минского с двумя счетчиками при условии специальной кодировки входа и выхода, что позволяет сделать вывод о равномощности двухсчетчиковых машин Минского и машин Тьюринга. Однако возникает вопрос о возможности реализации входных и выходных кодировок также с помощью двухсчетчиковой машины. Эти задачи известны как проблема «входа» и проблема «выхода». Во второй главе на основе «базовых» неразрешимых проблем остановки и зацикливания, которые двухсчетчиковые машины наследуют от машин Тьюринга, с помощью метода сведения доказывается неразрешимость ряда классических проблем для двухсчетчиковых машин Минского. На примере класса двухголовочных автоматов демонстрируется, каким образом счетчиковые машины могут использоваться для доказательства алгоритмической неразрешимости свойств различных формализмов и абстрактных математических машин. Третья глава посвящена (описанным ранее) проблемам «входа» и «выхода» для двухсчетчиковых машин Минского, которые для удобства исследования этих проблем приводятся к виду однорегистровых машин. Показывается, что решения проблемы «входа» не существует, а проблема «выхода» затрагивает некоторые сложные вопросы теории чисел.

Стр.3