Файл: Кравченко Р.Г. Основы кибернетики учеб. пособие.pdf

ритм Ак, преобразующий исходные данные щ в результат Pj, можно свести к вычислению функции tp&, указывающей номер результата j по номеру совокупности исходных данных i:

/ = фь(0-

Так как индексы / и i являются целыми числами, то они

нечной (простирается в бесконечность как последовательность натуральных чисел). В каждой из ячеек может быть записан нуль или единица. Над лентой перемещается головка Т, управ­ ляемая автоматом L, обладающим конечной памятью. Автомат L работает тактами. На его вход поступает информация о символе (О или 1), считываемая головкой с ленты. Под влиянием команд, получаемых с автомата L каждый такт, головка может оста­ ваться на месте или передвигаться на одну ячейку вправо или

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

Действие машины Тьюринга однозначно определяется исход­ ным заполнением ячеек ленты и оператором преобразования управляющего автомата, который может быть задан таблицей переходов. Обозначим через Si(5o = 0, Si =l ) символ, считывае­ мый головкой; через Rj{Ro — стоп, Ri — влево, Дг — вправо) — команду на перемещение головки и через <?*.(^ = 1, 2,..., п) — состояние управляющего автомата. Тогда определенным значе­ ниям Si и qu соответствует определенная совокупность значений трех величин: 5j, R и q, обозначающих соответственно, какой символ S запишет головка на ленту, какова будет команда R на перемещение головки и в какое новое состояние q перейдет

автомат L. Следует иметь

в состоянии покоя q*. Таким образом, придя в состояние q*, машина Тьюринга дальнейшую работу прекращает.

Пусть, например, таблица переходов автомата L имеет сле­ дующий вид (табл. 5).

Тогда, если в начальный момент автомат находится в состоя­ нии qt, а головка расположена над ячейкой, в которой записан символ 1, то головка будет перемещаться вправо до тех пор, пока не обнаружит ячейку с символом 0, заменит его символом 1 и остановится. Если начальное состояние машины соответствует изображенному на рис. 36, а, то по данным табл. 5 система пе­ рейдет в состояние, соответствующее рис. 36, б, и остановится.

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

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

178

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

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

Понятие о самоизменении и самоорганизации в автоматах.

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

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

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

При рассмотрении нами произвольного дискретного автомата неявно предполагалось, что при подаче на его вход какого-либо слова у из алфавита (множества) У и получения соответствую­ щего выходного слова дс[лг=ф(г/)] в алфавите X автомат снова возвращался в начальное состояние z0. Таким образом, в момент подачи каждого нового входного слова у автомат всегда оказы­ вается в одном и том же исходном состоянии Zq. Благодаря этому индуцируемое автоматом отображение <р является жест­ ким, неизменным в том смысле, что результат преобразования отображением <р любого входного слова у зависит лишь от са­ мого слова у, а не от того, в какой момент оно было подано на вход автомата.

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

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

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

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

Система автоматического регулирования. Системы автомати­ ческого регулирования (САР) состоят, по крайней мере, из трех основных элементов: измерительного устройства /, управляю­ щего устройства К, исполнительного устройства, реализующего управляющее воздействие R. Эти элементы, присоединенные

180