Файл: Касаткин, В. Н. Семь задач по кибернетике.pdf

Убедимся в эффективности алгоритма на примере.

ма, что нам и удается два раза. После этого работа алго­ ритма завершается и результатом является слово

бором только палочек). Сконструировать нормальный ал­ горитм, применение которого»'к данному слову, состоящему из четного числа палочек, приводило бы к слову *, а при­ менение этого же алгоритма к слову, состоящему из нечет­ ного числа палочек, к слову +.

Решением, или лучше сказать одним из решений, мо­ жет быть такое:

11->*

I+

*-)—>- -ф-

** —> *

Для желающих попробовать свои силы в разработке алгоритмов предлагается такая задача:

В алфавите, включающем в себя цифры троичной системы счисления, дано некоторое число. Требуется построить нормальный алгоритм, при­ менение которого к данному числу приведет к образованию нового числа, которое будет наименьшим из всех чисел, какие только можно составить из всех цифр, входящих в данное число.

49

Рассказ-задача 7

АЛГОРИТМ НАД АЛГОРИТМАМИ

Перейдем от рассмотрения отдельных алгоритмических систем — системы Эмиля Поста, Аллана Тьюринга и Ан­ дрея Маркова — к изучению их взаимосвязи.

Выше не раз подчеркивалось, что какая-либо задача, решенная в одной из рассматриваемых систем, всегда бу­ дет решена и в любой другой из числа рассмотренных. Это значит, что всякой программе для решения конкрет­ ной задачи на машине Поста можно поставить в соответст­ вие хотя бы один нормальный алгоритм для решения той же задачи или построить машину Тьюринга, которая так­ же успешно будет решать этот же класс задач. Это утвер­ ждение справедливо для любой из рассмотренных нами алгоритмических систем.

Как же найти эти новые алгоритмы?

Можно заняться решением задачи заново, не обращаясь к уже имеющемуся алгоритму в какой-либо иной алго­ ритмической системе. Можно попробовать поступить ина­ че: взять алгоритм, разработанный для решения этого класса задач в какой-либо из изученных нами алгоритми­ ческих систем, например текст программы для машины Поста, и попробовать формально, совершенно не вникая в суть задачи, так его преобразовать, чтобы получить ис­ комое решение задачи уже в другой алгоритмической сис­ теме.

Мы избираем второй путь, будем искать способы, пользуясь которыми мы сможем формально получить ал­ горитм в любой из изученных нами систем без обращения к условию задачи. Исходным материалом для получения нового алгоритма будет только текст алгоритма в какойлибо из изученных систем.

Начнем с отыскания способа конструирования нор­ мального алгоритма, исходя из текста данной программы для машины Поста.

50

Пусть нам дана программа, работая по которой, маши­

Малой Академии наук «Искатель». Приводимый ниже вари­ ант решения принадлежит девятикласснику Володе Кисляковскому.

Как и всегда, конструирование нормального алгоритма следует начинать с определения алфавита. Условимся

V V

Рис. 29

о следующем: каждому состоянию информационной ленты будем ставить в соответствие слово, записанное с помощью

51

Итак, алфавит:

/І {1, 0, й|, о2, <?3, ... , оп].

Команду «стереть метку» т. J k будем моделировать подстановкой

а„,1

Аналогично, двумя Же подстановками, моделируем сдвиг вправо т. -> k

aml - ûfeO->0ak

Команда условной передачи управления т.Р-^^моде-

\«

лируется также двумя подстановками:

ûm0 -> akQ >■ ûnl

И последняя команда, команда mJ, тоже моделирует­ ся двумя, но уже заключительными, подстановками:

ат0^. О

52

Итак, что же мы смоделировали? Во-первых, — со­ стояние ленты, во-вторых, — каждую команду в отдельнос­ ти. Теперь необходимо смоделировать каретку и найти способ получения нормального алгоритма из отдельных подстановок и пар подстановок.

Посмотрите, как оригинально моделирует каретку Во­ лодя. Показываем на примере.

V V V V V V

Рис. 30

Пусть дано состояние машины, изображенное нарис. 30. Этому состоянию ставим в соответствие слово

«¿1101111.

Еще пример. Дано состояние машины (рис. 31). Этому состоянию машины ставим в соответствие слово

11 «¿ 01111.

V V V V V V

Рис. 31

Алгоритм в целом будем конструировать по следующе­ му правилу:

1.Каждой команде машины Поста ставим в соответ­ ствие ее модель, которая представляет собой либо одну, либо две подстановки.

2.Состояние машины моделируем словом, составлен­

ным из букв 1 и 0. Букву «¿ помещаем внутри слова (или в каком-либо другом месте) так, чтобы та буква, под ко­ торой расположена каретка, оказалась соседней справа от буквы «х.

53

Применив эту рекомендацию для конструирования ал­ горитма, исходя из вышеприведенной программы, полу­ чим таблицу команд для машины с соответствующими им подстановками (табл. 3). Интересно, что столбец подста­ новок образовал нормальный алгоритм.

Проверим работу полученного алгоритма на примере. Пусть исходное состояние машины такое, как показано

на рис. 32. Моделью будет слово

аг 10000111.

V V V V

Рис. 32

К этому слову применяем первую подстановку:

а4 1 ->- а20

и получаем слово

а200000111.

54