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

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

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

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

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

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

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

записывающей головкой) <
*) Поэтому анекдотически выглядят такие, например, рекомендации
относительно ознакомления с машинами этого типа: "для того, чтобы лучше
представить действительную работу машины, интересующийся должен
обратиться к технической литературе" (Попов А. И. Введение в
математическую логику. - Л.: Изд-во ЛГУ, 1959. -С. 91).
2) Устройство, позволяющее моделировать работу машины Поста в случае
небольших программ и небольших объемов вычислений, изготовлено в 1970 г.
в Симферопольском государственном университете- см.: Касаткин В. Н, Семь
задач по кибернетике.- Киев: Вища школа, 1975. - С. 26,
7
Лента бесконечна и разделена на секции одинакового размера: для
наглядности ленту будем считать располо-* женной горизонтально (рис. 1).
Бесконечность ленты находится в противоречии со сделанным выше
утверждением, что машину Поста можно было бы в принципе построить. Дело в
том, что мы объявили ленту бесконечной лишь для простоты изложения. С тем
же успехом можно было бы предпо-ложить, что лента не бесконечная, а лишь
неограниченно
Рис 1. Лента машины Поста разделена на секции и неограниченно
простирается влево и вправо
растущая в обе стороны: например, можно было бы счи-тать, что лента
наращивается на одну секцию, как только каретка доходит до конца ленты и
должна двигаться дальше (о движении каретки смотри ниже), или считать,
что за каждую единицу времени слева и справа нарастает по одной секции.
Нам, однако, будет удобнее считать, что все секции слева и справа уже
наросли, и тем самым, хотя и в ущерб реальности, полагать ленту
бесконечной в обе стороны.
Порядок, в котором расположены секции ленты, по-добен порядку, в котором
расположены все целые числа. Поэтому естественно ввести на ленте
"целочисленную
-1-1 0 11 5 4 S $
Рис. 2
систему координат", занумеровав секции целыми чис* лами ..., -3, -2, -1,
0, 1, 2, 3, ... (рис. 2).
Мы будем считать, что система координат жестко сопоставлена с лентой, и
получим таким образом возможность указывать какую-либо секцию ленты,
называя ее порядковый номер, или координату. (Иногда, впрочем, бывает
удобно наряду с основной, "постоянной" системой координат, ввести еще
вспомогательную, "временную", сдвинутую по отношению к первоначальной.)
В каждой секции ленты может быть либо ничего не записано (такая секция
называется пустой), либо
8
записана метка V (тогда секция называется отмеченной) (рис. 3).
Информация о том, какие секции пусты, а какие отмечены, образует
состояние ленты. Иными словами, состояние ленты - это распределение меток
по ее секциям1). Как мы далее увидим, состояние ленты меняется в процессе
работы машины.
Каретка может передвигаться вдоль ленты влево и вправо. Когда ока
неподвижна, она стоит против ровно
Ш
м Ivlvl
Рис. 3. В каждой секции ленты либо не записано ничего, либо
записана метка
одной секции ленты (рис. 4, а\ на этом и следующих чертежах каретка
изображена в виде зачерненного квад* рата); говорят, что каретка
обозревает эту секцию, или держит ее в поле зрения.
Информация о том, какие секции пусты, а какие от*> мечены и где стоит
каретка, образует состояние машины
1
а)
i
Рис. 4. Когда каретка неподвижна, она стоит против одной из секций ленты
так, как показано на рис. а), а не так, как показано на рис. б).
Ситуация, изображенная на рис. б), может возникнуть
только в процессе движения каретки
Поста. Таким образом, состояние машины слагается из состояния ленты и
указания номера той секции, которую обозревает каретка. За единицу
времени (которую мы будем называть шагом) каретка может сдвинуться на
одну секцию влево или вправо. Кроме того, каретка может поставить
(напечатать) или уничтожить (стереть) метку в той секции, против которой
она стоит,
1) На точном математическом языке состояние ленты - это функция,
которая каждому числу (номеру секции) ставит в соответствие либо метку,
либо, скажем, слово "пусто"
9
а также распознать, стоит или нет метка в обозреваемой ею секции. Чем
определяются действия каретки, а также, что значит "распознать" в
применении к каретке, будет объяснено в § 3.
§ 2. Программа машины Поста
Работа машины Поста состоит в том, что каретка передвигается вдоль ленты
и печатает или стирает метки. Эта работа происходит по инструкции
определенного вида, называемой программой. Для машины Поста возможно
составление различных программ. Посмотрим, как устроена программа.
Каждая программа машины Поста состоит из команд. Командой машины Поста
будем называть выражение, имеющее один из следующих шести видов (буквы i,
/, /ь ]2 означают всюду натуральные числа 1, 2, 3, 4, 5, ,,, ):
Первый вид. Команды движения вправо,
i. =>- j
Второй вид. Команды движения влево.
и -<= \
Третий вид. Команды печатания метки.
и V /
Четвертый вид. Команды стирания метки.
i. li
Пятый вид. Команды передачи управления.
А \к
Шестой в ид. Команды остановки.
/. стоп.
Например,
137. => 1
является командой движения вправо,
/32
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 38 >> Следующая