Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет
им. П.Г. Демидова
Е. В. Кузьмин
Счетчиковые машины
Под редакцией
доктора физико-математических наук,
профессора В. А. Соколова
Учебное пособие
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по специальности Математическое обеспечение
и администрирование информационных систем
Ярославль 2 0 1 0
Стр.1
УДК 519.7
ББК З817я73
К89
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2010 года
Рецензенты:
кандидат педагогических наук, доцент О.В. Карташева;
кафедра прикладнойматематикиивычислительнойтехникиЯГТУ
Кузьмин, Е.В. Счетчиковые машины: учеб. пособие / Е. В. Кузьмин;
К89 под ред. доктора физико-математических наук, профессора В.А. Соколова;
Яросл. гос. ун-т. им. П. Г. Демидова. — Ярославль: ЯрГУ, 2010. — 128 с.
ISBN 978-5-8397-0732-0
Посвящено теории счетчиковых машин, представляющих собой абстрактные
математические модели вычислений. Затрагивает интересные факты из теорий
вычислимости и сетей Петри, не вошедшие в известные классические монографии.
Основное внимание уделяется счетчиковым машинам «малой размерности», т. е.
машинам, содержащим один, два или три счетчика. Наибольший интерес представляют
занимающие центральное положение в этом пособии результаты исследований
Р. Шреппеля о «чистой» вычислительной способности двухсчетчиковых
машинМинского и результаты Дж. Хопкрофта иЖ.-Ж. Пансио о полулинейности
множества достижимости двумерных систем векторного сложения с состояниями.
Предназначено для студентов старших курсов, обучающихся по специальности
010503.65 Математическое обеспечение и администрирование информационных
систем (дисциплина «Дополнительные главы информатики», блок СД), очной
формы обучения. Также может быть использовано магистрантами и аспирантами,
специализирующимися в области теоретической информатики и прикладной
математики.
Рис. 33. Библиогр.: 32 назв.
УДК 519.7
ББК З817я73
ISBN 978-5-8397-0732-0
Ярославский государственный университет им. П. Г. Демидова, 2010
c
Стр.2
ОГЛАВЛЕНИЕ
Предисловие ... ... .. ... ... .. ... ... .. ... ... .. ... ... . . 5
Глава 1. Машины Тьюринга и вычислимость .. .. . . . . .. . 7
1.1.Машины Тьюринга . .. . . . . . . . . . .. .. . . . . .. .. . . . . .. . 8
1.2.Пример машины Тьюринга . ... ... .. ... ... .. ... . .. .. 11
1.3.Алгоритмические проблемы. ... ... . . ... ... .. ... ... .. 14
1.4.Проблема остановки . ... .. ... . .. .. ... ... .. ... ... .. 16
1.5.Проблема зацикливания . . . . .. ... .. ... ... .. ... ... . . 19
1.6. Комментарии к главе. ... . . . .. ... .. ... ... .. ... . .. .. 20
Глава 2. Счетчиковые машины.. ... . . ... ... .. ... ... .. 22
2.1. Счетчиковые машины Минского ... . . ... ... .. ... . .. .. 23
2.2. Комментарии к главе. ... . . . .. ... .. ... ... .. ... . .. .. 37
Глава 3. Двухсчетчиковые машины .. .. . . . . .. .. . . . . . . . 38
3.1.Неразрешимые проблемы и метод сведения ... .. ... . .. .. 38
3.2.Проблемы ограниченности.. ... ... . . . .. ... . . ... ... . . 46
3.3. Комментарии к главе. ... . . . .. ... .. ... ... .. ... . .. .. 50
Глава 4. Однорегистровые машины .. .. . . . . .. .. . . . . . . . 54
4.1.Однорегистровые машины .. ... . .. .. ... ... .. ... ... .. 54
4.2. Теоремы по проблеме «входа» .. ... . . ... ... .. ... ... .. 66
4.3. Теоремы по проблеме «выхода» . ... .. ... . .. .. ... ... . . 73
4.4.О вычислимых функциях . . . .. ... . . . .. ... .. ... ... . . 78
4.5. Комментарии к главе. ... . . . .. ... .. ... ... .. ... . .. .. 83
Глава 5. Односчетчиковые машины . . . ... ... .. ... . .. .. 84
5.1.Основные определения .. .. ... . .. .. ... . .. .. ... ... .. 84
5.2. Свойства односчетчиковых машин .. .. ... ... . . . .. ... . . 86
5.3. Комментарии к главе. ... . . . .. ... .. ... ... .. ... . .. .. 89
Стр.3
4
Оглавление
Глава 6. Линейные и полулинейные множества . ... ... .. 90
6.1.Основные понятия и определения .. .. ... ... .. ... ... .. 90
6.2. Конусы и полулинейность . . ... ... .. ... ... .. ... ... .. 94
6.3. Комментарии к главе. ... .. ... ... .. ... ... .. ... ... .. 95
Глава 7. Системы векторного сложения ... ... .. ... ... .. 96
7.1.Предварительные сведения . ... ... .. ... ... .. ... ... .. 97
7.2. Системы векторного сложения.. ... .. ... ... .. ... ... .. 97
7.3. Системы векторного сложения с состояниями . . . ... ... .. 104
7.4. Комментарии к главе. ... .. ... ... .. ... ... .. ... ... .. 117
Глава 8. Арифметика Пресбургера . . . ... ... .. ... ... .. 118
8.1.Формулы арифметики Пресбургера . . . ... ... .. ... ... .. 118
8.2. Теорема об элиминации кванторов . . . . .. ... . . ... ... .. 120
8.3. Комментарии к главе. ... .. ... ... .. ... ... .. ... ... .. 123
Литература . ... ... .. ... ... .. ... ... .. ... ... .. ... ... .. 125
Стр.4
Предисловие
Пособие посвящено теории счетчиковых машин, представляющих
собой абстрактные математические модели вычислений. Затрагивает
интересные факты из теории вычислимости и теории сетей Петри,
не вошедшие в широко известные работы «Вычисления и автоматы»
М. Минского [11], «Сети Петри» В. Е. Котова [5] и «Теория сетей
Петри и моделирование систем» Дж. Питерсона [12]. Таким образом,
настоящее пособие можно считать небольшим дополнением к этим
классическим монографиям.
После того, как будут даны понятия, определения и первоначальные
знания, наличие которых обязательно для работ по этой тематике,
основное внимание концентрируется на счетчиковых машинах «малой
размерности», т. е. машинах, содержащих один, два или три счетчика.
Наибольший интерес представляют занимающие центральное положение
в этом пособии результаты исследований Р. Шреппеля [31] о «чистой»
вычислительной способности двухсчетчиковых машин Минского
и Дж. Хопкрофта и Ж.-Ж. Пансио [23] о полулинейности множества
достижимости двумерных систем векторного сложения с состояниями.
Пособие организовано следующим образом.
В первой главе дается определение машины Тьюринга как формализации
интуитивного понятия алгоритма и приводится ее пример. С точки
зрения понятия «массовых алгоритмических проблем» обсуждаются
разрешимые и неразрешимые проблемы для машин Тьюринга. Приводятся
доказательства теорем о неразрешимости проблем «остановки»
и «зацикливания».
Во второй главе описывается другой вид абстрактных универсальных
математических машин — счетчиковые машины Минского. Показывается,
что любую машину Тьюринга можно смоделировать машиной
Минского всего лишь с тремя счетчиками. Более того, любая трехсчетчиковая
машина Минского моделируется машиной Минского с двумя
счетчиками при условии специальной кодировки входа и выхода, что
позволяет сделать вывод о равномощности двухсчетчиковых машин
Минского и машин Тьюринга. Однако возникает вопрос о возможности
реализациивходных ивыходныхкодировок такжеспомощью
двухсчетчиковой машины. Эти задачи известны как проблема «входа»
ипроблема «выхода».
Стр.5
6
Предисловие
В третьей главе на основе «базовых» неразрешимых проблем остановки
и зацикливания, которые двухсчетчиковые машины наследуют
от машин Тьюринга, с помощью метода сведения доказывается неразрешимость
ряда классических проблем для двухсчетчиковых машин
Минского.
Четвертаяглава посвящена (описанным вовторойглаве) проблемам
«входа» и «выхода» для двухсчетчиковых машин Минского, которые
для удобства исследования этих проблем приводятся к виду однорегистровых
машин. Показывается, что решения проблемы «входа»
не существует, а проблема «выхода» затрагивает некоторые сложные
вопросы теории чисел.
В пятой главе рассматриваются односчетчиковые машины Минского,
которые, несмотря на наличие всего лишь одного счетчика, имеют
широкий спектр применения. Доказывается, что в отличие от машин
сб´
ольшим количеством счетчиков для односчетчиковых машин Минского
разрешимы такие классические проблемы, как достижимость
заданной конфигурации, ограниченность, пустота, включение и равенство
множеств достижимых конфигураций двух машин. Разрешимость
перечисленных проблем является следствием того, что полное поведение
(конечное или бесконечное) односчетчиковой машины может быть
представлено за полиномиальное время от размера машины в удобном
(для дальнейших исследований) конечном виде.
Шестая глава является вспомогательной к следующей главе. Здесь
определяются понятия линейных, полулинейных множеств и конусов.
Описываются основные свойства этих понятий.
В седьмой главе рассматривается разновидность систем векторного
сложения, которая предполагает наличие конечного управления, —
системы векторного сложения с состояниями. Показывается, что множество
достижимости для любой системы векторного сложения с
состояниями, размерность которой не превосходит двух, представляет
собой вычислимое полулинейное множество. Поскольку представление
полулинейного множества в терминах периодов и предпериодов
может быть задано формулой арифметики Пресбургера, следствием
этого является разрешимость для таких систем проблем достижимости,
эквивалентности и включения. Приводится пример трехмерной системы
векторного сложения с состояниями, которая имеет неполулинейное
множество достижимости. Из чего следует, что для систем более
высокой размерности необходимы другие подходы к решению рассматриваемых
проблем.
Восьмая глава посвящена арифметике Пресбургера.
Стр.6
Учебное издание
КУЗЬМИН Егор Владимирович
СЧЕТЧИКОВЫЕ МАШИНЫ
Учебное пособие
Научный редактор В.А. Соколов
Редактор, корректор М.В. Никулина
Компьютерный набор и верстка Е.В. Кузьмин
Бум. офсетная. Гарнитура «Times New Roman».
Усл. печ. л. 7, 44. Уч.-изд. л. 6, 0.
Тираж 75 экз. Заказ
Подписано в печать 2010. Формат 60×84/16.
.
Оригинал-макет подготовлен
в редакционно-издательском отделе
ЯрГУ им. П.Г. Демидова.
Отпечатано на ризографе.
Ярославский государственный университет им. П.Г. Демидова
150000, Ярославль, ул. Советская, 14
Стр.128