Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Машина поста - Успенский В.А.

Успенский В.А. Машина поста — М.: Наука, 1988. — 96 c.
ISBN 5-02-013735-9
Скачать (прямая ссылка): mashinaposta1988.djvu
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 38 >> Следующая

29
таких состояний из класса Ет в которых каретка стоит справа от массива.
На рис. 19 показан общий вид состояния из класса Сп, а на рис. 20 - общий
вид состояния из класса С'.
Задача 3 (короткая формулировка). Написать такую программу машины Поста,
которая для любого п, будучи применена к произвольному состоянию
I
1
Рис. 19. Общий вид состояния из класса Сп. Здесь k^O
I
3
Рис, 20. Общий вид состояния из класса СЛ. Здесь k^O
из класса С", дает результативную остановку в каком-то состоянии из
класса Еп+ь
Задача 3' (короткая формулировка). Написать такую программу машины Поста,
которая для любого п, будучи применена к произвольному состоянию из
класса С', дает результативную остановку в каком-то
состоянии из класса Еп+
Очевидно, что каждую программу, являющуюся решением задачи 3, можно
превратить в решение задачи 3', если всюду знак =>- заменить на знак -<=,
а знак -<= заменить на знак =^. Такой же операцией любое решение задачи
3' превращается в решение задачи 3. Поэтому достаточно решить только одну
из этих задач. Вот одно из решений задачи 3:
Программа III
1. =^2 3. <=4 /1 4. V5
5. стоп.
к свиции ^ ....
vlvR tavivi I I И

/?+/ секции
к секции
Ш 1 ШЕ Яу1у
у
20
Попробуйте доказать, что задача 3 не допускает бо*< лее коротких решений.
Сколько существует решений этой задачи длины 5?
§ 4. Прибавление единицы в еще более сложном случае
В этом параграфе мы рассмотрим в качестве класса исходных (начальных)
состояний объединение всех классов В0, Со, В\у Сь В2у С2, ?з, С3, ... из
предыдущего параграфа. Этот класс будет, следовательно, состоять из всех
таких - и только таких - состояний машины, в каждом из которых каретка
стоит либо против какой-то из секций исходного массива, либо же левее
массива.
Обозначим через Dn совокупность всех таких состояний из класса Еп, в
которых обозреваемая кареткой секция либо отмечена, либо расположена
левее всех отмеченных секций. Очевидно, что при каждом п класс Da есть
объединение классов Вп и Сп.
Задача 4. Написать такую программу машины Поста, которая для любого п,
будучи применена к произвольному состоянию из класса Dny дает
результативную остановку в каком-то состоянии из класса Еп+\.
Задачу 4 можно свести к задачам 2 и 3, т. е. можно указать способ, как из
произвольных решений задач 2 и 3 получить некоторое решение задачи 4.
Укажем такой способ. Пусть S - произвольный список команд машины Поста, a
k - произвольное целое число. Через S \-\-k] будем обозначать список,
полученный из Е путем прибавления числа k ко всем номерам и всем отсылкам
команд из S. Например, Ii[+7] - это такой список:
8. -ф= 9
9. V Ю
10. стоп.
Пусть теперь II - произвольная программа, являющаяся решением задачи 2, а
III - произвольная программа, являющаяся решением задачи 3. Пусть I есть
длина программы II. Составим теперь такой список команд;
2 н [+1]
1# -\2 ш [+/+1]
31
Легко проверить, что этот список команд является программой машины Поста,
причем такой программой, которая удовлетворяет условиям задачи 4. В самом
деле, всякое состояние из класса Dn принадлежит либо Вп, либо Сп. В
первом случае "срабатывает" список II [+1], во втором - список 1Щ+/4- !]•
Однако изложенный способ не обязан давать (и, как мы сейчас увидим,
действительно не дает) крат* чайшее решение задачи 4 - даже если исходить
из кратчайших решений задач 2 и 3. Посмотрим, что получится, если
применить этот способ к программам IIi и III. Мы получим такое решение
задачи 4;
Программа IV10 /6
1. ? 6. =>7
'\2
2. <= 3 7.
'\2
9. V Ю
СТОП.
4. Vo ю.
5. стоп
Ясно, что эту программу можно сократить, не меняя при этом совершаемой ею
работы, путем объединения в одну двух команд остановки, или, как мы будем
говорить, путем поглощения одной из этих команд другой. Проще поглотить
команду № 10 командой № 5. Для этого достаточно заменить отсылку 10 во
всех командах, где она встречается, - в нашем случае только в команде № 9
- на отсылку 5 и затем вычеркнуть команду № 10 *).
Мы получим программу IV9, в которой можно теперь поглотить команду № 9
командой № 4. Для этого достаточно заменить в команде № 8 отсылку 9 на
отсылку 4 и затем вычеркнуть команду № 9. После произведенных двух
поглощений получим новое решение задачи 4 в виде программы IV8,
*) Если бы мы хотели поглотить команду № 5 командой № Ю, то надо было бы
заменить отсылку 5 на отсылку 10 во всех командах, где она встречается (в
данном случае в команде № 4), затем вычеркнуть команду № 5, после чего
уменьшить на 1 все номера команд, следующих за вычеркиваемой, и все
отсылки, совпадающие с этими номерами.
32
Программа IV8
5t стоп 6. =>7
2. <= 3
8. <=4
4. V 5
Замечание. В общем случае поглощение (в данной программе) команды № а
командой № р состоит в последовательном выполнении трех операций. Во-пер-
вых, всюду отсылка а заменяется на отсылку р; во-вторых, команда № а
вычеркивается; в-третьих, во всех командах образовавшегося списка числа а
+ 1, а + 2, а + 3, ... (которые могут быть как номерами, так и отсылками)
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 38 >> Следующая