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

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

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

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

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

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

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

узлов (команд) № 19, 20, 21, 22;
8-й блок - назовем его "блоком остановки" - состоит из узла (команды) №
23.
Для каждого разбиения данной программы на блоки можно составить свою так
называемую блок-схему данной программы. Для этого надо каждый блок
изобразить в виде прямоугольника и провести от прямоугольника,
изображающего блок а, к прямоугольнику, изображающему блок (3, столько
стрелок, сколько их идет от узлов блока а к узлам блока р. Блок-схема
программы V для выбранного нами разбиения на блоки приведены на рис. 22
(внутри каждого прямоугольника вписан номер и название соответствующего
блока),
39
Имея перед глазами блок-схему какой-либо программы, можно наглядно
представить себе ее работу в форме последовательного выполнения команд то
одного блока, то другого. Блок, содержащий команду № 1, будем называть
начальным, а блок, содержащий команду остановки,- заключительными для
простоты будем считать,
что заключительный блок ничего больше не содержит. Вместо того чтобы
говорить "выполнение команд данного блока",условимся для краткости
говорить просто "выполнение данного блока", Первым всегда будет
выполняться начальный блок. При выполнении какого-
л.
либо незаключительного блока могут произойти три случая: 1) во время
выполнения блока произойдет безрезультатная остановка;
2) выполнение блока никогда не окончится, т. е. каждый раз после
выполнения какой-то команды надо будет снова выполнять команду того же
блока; 3) выполнение блока окончится, т. е. после выполнения некоторой
команды надо будет переходить к выполнению некоторой команды другого
блока. Короче, попав в незаключительный блок, мы либо "застрянем" в нем
навсегда* либо по одной из отходящих от него стрелок выйдем в некоторый
другой блок.
Иногда можно сразу, по виду диаграммы, выделить некоторые блоки, в
которых заведомо невозможно застрять (если только исключить случай
безрезультатной остановки, которая может произойти в любой момент). Для
блок-схемы на рис. 22 такими будут, как следует из диаграммы на рис. 21,
блоки 2-й и 4-й. Поэтому выполнение программы V будет происходить
следующим образом: сперва выполняется 1-й блок; его выполнение либо
никогда не кончается, либо кончается, и тогда выполняется 2-й блок.
Выполнение 2-го блока кончается обязательно, и после него выполняется
либо 3-й блок, яибо 6-й; после 3-го (если его выполнение заканчивается)-
4-й; после 4-го - либо 5-й, либо 7-й; после 5-го
Рис. 22
40
(если его выполнение заканчивается) - 2-й; после 2-го снова либо 3-й,
либо 6-й; и так далее. Выполнение 6-го (равно как и 7-го) блоков может
закончиться, а может и не закончиться; если оно закончится, то
выполняется
8-й блок, и машина останавливается.
Теперь мы можем, наконец, решить для нашей программы задачу анализа. Мы
ограничимся при этом случаем, когда начальное состояние принадлежит (при
некотором п) классу Еп. При помощи блок-схемы в следующем параграфе будет
показано, что в применении к такому начальному состоянию программа
приводит к результативной остановке в состоянии из класса Еп+\.
Тем самым решается следующая (поставленная в § 5 предыдущей главы) общая
задача о прибавлении единицы:
написать программу машины Поста, которая для любого п, будучи применена к
произвольному состоянию из Еп (взятому в качестве начального), дает
результативную остановку в каком-то состоянии из класса Еп+\т
Именно, программа V длины 23 оказывается решением этой задачи. Автору не
удалось построить более короткую программу, которая бы служила решением
той же задачи. В то же время автор не знает, как доказать, что найденная
программа - самая короткая из возможных. Может быть, кому-нибудь из
читателей удастся сделать то или другое?
§ 2. Анализ программы прибавления единицы
Итак, перейдем к анализу программы V из § 1, т. е. к выяснению того, как
она работает. Как мы договорились, в качестве начального состояния мы
выбираем какое-то состояние, принадлежащее какому-то из классов Еп(п= О,
1, 2, ...). Обозначим через Нп класс тех состояний из класса ЕПу при
котором как обозреваемая секция, так и соседняя с нею секция справа обе
пусты.
Приступаем к выполнению программы V. Сначала выполняется первый блок.
Сейчас мы покажем, что выполнение его закончится (т. е. мы выйдем из него
во второй блок); одновременно мы увидим, какое состояние машины возникнет
после его выполнения# Рассмотрим три случая.
Случай 1. В начальном состоянии как обозреваемая секция, так и соседняя с
ней слева секция обе пусты. В этом слу** чае последовательно сработают
команды № 1, 2, 4, после чего выполнение блока окончится, причем машина
придет в состояние из класса Нп.
Случай 2. В начальном состоянии обозреваемая секция пуста, но соседняя с
ней слева секция отмечена. Это значит, что интересующий нас массив длины
п + 1 находится слева от обозреваемой секции и, следовательно, справа от
нее все секции пусты*
41
В этом случае последовательно сработают команды № !, 2, 4, 3, 4, после
Предыдущая << 1 .. 7 8 9 10 11 12 < 13 > 14 15 16 17 18 19 .. 38 >> Следующая