Искусство программирования ... RS-триггера?!

В. C. Любченко

Можно скачать текст статьи в формате html (zip архив около 66 кб)

Часть 1. Электронная схема и формальные модели

Часть 2. Программирование
Часть 3. Тест на синхронную работу

И дался Вам этот триггер!
Из переписки.

Даже сложная задача переходит в разряд элементарных, когда становится известным ее решение. Или порой она кажется столь простой, что жаль тратить нее время, но вдруг выясняется, что решить ее не так-то уж и легко! Задача моделирования работы RS-триггера пример того и другого случаев. В [1] она была предложена в качестве теста на проверку параллельных свойств дискретных систем. Но со временем выяснилось, что не всем ясен смысл этого теста, да и сама проблема реализация RS-триггера вызвала определенные трудности. При обсуждении проблемы моделирования триггера многим эта задача кажется элементарной! Но, пожалуй, даже на одной руке много пальцев, чтобы перечислить тех, кто успешно довел ее решение до конца.

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

Чтобы снять многие вопросы проектирования параллельных систем (прежде всего основной - выбор модели), рассмотрим подробно "проблему" и "феномен" триггера. Обсуждение разделим на три части: построение формальной модели, программирование триггера, применение его в качестве теста на исследование параллельных свойств программных систем. Начав обсуждение с довольно абстрактных понятий, мы в конечном итоге не только решим задачу моделирования триггера, но и разберемся, решая, казалось бы, частную задачу, в практических вопросах параллельного программирования. Но начнем мы, естественно, с электронной схемы RS-триггера.

Схема триггера

Электронная схема элемента И-НЕ, входящего в состав триггера, показана на рис 1а, а схема RS-триггера на таких элементах на рис. 1б. Кроме этого, возможна его схема на элементах ИЛИ-НЕ, но для решения поставленных целей, достаточно рассмотреть одну из них. Далее мы будем обсуждать также схему, состоящую из триггера и подключенного к его выходам элемента И-НЕ (на практике такая схема применяется для индикации окончания переходных процессов триггера). На рисунке связи соответствующие ей изображены пунктиром. Так мы рассмотрим работу не только отдельного триггера, но и проблемы, связанные с синхронной работой множества параллельных компонент. Особенность программной реализации будет заключаться в том, что функции индикатора, подключенного к выходам триггера, будут расширены до фиксации всех комбинаций на выходах и подсчета их количества.

Электронная схема отражает количественный состав и информационные связи между элементами триггера. Тип этих связей (перекрестные обратные связи) определяет специфику его работы. Хотя схема триггера проста, но понять и разобрать ее работу в силу этой специфики не так уж и просто. Модель в этом должна нам помочь. И чем больше модель будет походить на реальный объект (а для этого она должна быть параллельной), тем больше будет к ней доверия. По такому же принципу (параллельному), как и модель, должна быть организована и программная реализация триггера. Она должна быть максимально приближенной к ней по структуре, по функционированию, по составу, количеству и виду информационных связей. И в случае успеха триггер может стать основой теста параллельных свойств как языка программирования, используемого для реализации модели, так и среды исполнения, где этот тест будет функционировать. При этом элемент И-НЕ, подключенный к выходам триггера, будет служить не только индикатором прохождения триггера через определенное состояние, но одновременно исполнять роль теста на синхронную работу компонент, которыми в этом случае будут модели элементов И-НЕ.

Соглашения для создания модели

Прежде чем приступить к созданию модели реальной схемы/системы нужно оговорить условия моделирования. Мы будем рассматривать только дискретные модели. А это в большинстве случаев означает не только дискретное представление аналоговых сигналов, но и функционирование в дискретном времени t, принимающем значения t = 0, 1,... Кроме того, для одновременно, т.е. параллельно, работающих компонент дискретное время должно быть едино. Так мы моделируем реальное время, которое, если не очень углубляться в физические законы, едино для всех реальных объектов (как живых, так и не очень).

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

1. Функциональная модель

Обычно под функцией понимают <отображение (преобразование) одного множества X на (в) другое множество Y>[2]. В качестве математической модели дискретных систем можно использовать переключательные или булевы функции (БФ). Область определения и значения БФ - двухэлементные множества вида {0,1}, {истина, ложь}, {true, false} и т.п. При этом обычно элемент x X, принимающий значение 1, <истина>, и т.п., обозначается как x, в противном случае - (иногда мы будем использовать обозначение вида ^x). Примеры булевых функций: одноместных - функция отрицания, двухместных - конъюнкция, дизъюнкция. На основе элементарных одно и двух местных БФ с помощью операции суперпозиции (подстановки значения некоторых БФ в качестве аргументов для других БФ) строятся более сложные БФ (Более подробно о БФ, о способах их представления, минимизации и реализации можно познакомиться, например, в [3].)

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

(1)

1.1. Модель элемента И-НЕ

С учетом задержки, вносимой реальным элементом, в форме явной зависимости от времени функциональная модель элемента И-НЕ может быть задана следующим образом:

(2)

где x1, x2 - значение входов, y -значение выхода элемента, t - дискретное время

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

(3)

Из формул следует, что нулевое значение функция примет только при единичном значении своих аргументов.

1.2. Модель RS-триггера

В отличие от элемента И-НЕ, который при определенном допущении может рассматриваться как комбинационная схема (КС) (схемы, выходное значение которых не зависит от времени), триггер относится к классу так называемых последовательностных схем (ПС). Для ПС значение выхода зависит еще и от некоторого внутреннего состояния элемента. Это задается следующим образом (ср. с выражением (1)):

(4)

где x(t) - одна или некоторое множество обычных или <свободных переменных>, а q(t) - одна или множество <связанных переменных>. Последние и характеризуют некоторое внутреннее состояние модели.

Для системы БФ ее внутреннее состояние может определяться значением одной или нескольких булевых переменных. Функциональная модель триггера с учетом этих рассуждений может быть представлена следующей системой функций:

(5)

В упрощенном виде получим следующую систему БФ,

(6)

В выражении (6) в правой части уравнений находятся переменные, значение которых соответствует текущему моменту времени, а в левой - значения функций (тех же переменных) для следующего момента дискретного времени. Так как процесс вычисления некоторой функции разнесен во времени, а область ее значений совпадает с областью значений входных переменных, то булевские переменные, соответствующие именам функций, могут входить как в левую, так и в правую часть уравнений. При этом в пределах одной БФ имена этих переменных могут даже совпадать.

Заметим, что значения <зависимых переменных>, определяющих состояние системы БФ, вычисленное в текущий момент времени, должно каким-то образом запоминаться для использования в следующий момент времени. Формально в рамках данной модели на этот вопрос ответа нет. Но предполагается, что эта проблема каким-то образом все же решена. В противном случае необходимо признать, что модель триггера на основе системы БФ невозможна. Скорее всего, это так и есть, но почему - станет ясно из рассмотрения других моделей триггера.

2. Модель блок-схем. Схемы программ

Программирование решения, представленного функциональной моделью, требует уточнения, т.е. формулировки алгоритма для программы, вычисляющей функцию. При этом в общем случае программа может быть представлена как конечное множество операторов (функций) над памятью, для которых задан порядок их выполнения. Формальная математическая модель программы тогда может быть представлена так называемой схемой программы[4], определяемой как тройка S = (M, A, G) [5]. Где M - множество ячеек памяти, A - множество операторов программы, G - управление.

Разобьем множество операторов A на два непересекающихся подмножества. Это операторы логического типа - предикаты x_i X и операторы функционального типа - действия y_i Y. Или A = (X,Y), где X = {x_i}, Y = {y_i} и X Y = 0, |A| = |X| + |Y|. Каждому оператору из A ставится в соответствие множество входных ячеек памяти D_a M. Множество выходных ячеек R_a M определено только для операторов функционального типа y_i Y. Значением логического оператора x_i X является константа 0, если вычисленное предикатом условие ложно, и 1, если истинно.

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

Заметим, что в идеале предикаты, только читают, а действия читают и изменяют данные. Это замечание важно для случая параллельного исполнения операторов, т.к. при выполнении этих условий на параллельный запуск предикатов по сути ограничений нет, а действия, исполняемые параллельно, не должны конфликтовать по операции изменения/записи данных.

Управление G - компонента, которой нет у функциональной модели. Это основа программы. От модели управления во многом зависят возможности языка программирования. В большинстве широко известных языков программирования управление может быть отнесено к модели блок-схем (БС) или в формулировке схем программ - классу стандартных схем программ[4]. Для стандартных схем программ алгоритм решения задачи в графическом виде может быть представлен в форме известной всем блок-схемы. При этом условным вершинам (ромбам) будут соответствовать операторы-предикаты, функциональным (прямоугольникам) - действия.

Схема программы - весьма гибкая модель. Манипулируя ее компонентами, мы можем получать самые разные программные модели. Например, если память - лента, операции - передвижение головки и изменение ленты, управление - автомат, то получаем машину Тьюринга. Усложним структуру памяти, расширим операции до реализации концепции "шаг в шаг" [6], но не тронем управление, оставив его автоматом, получим автоматную модель любого языка, которому соответствуют введенные для схемы программы операции и память. Ну и т.д. и т.п.

2.1. Модель элемента И-НЕ

Различные варианты моделей элемента И-НЕ в виде БС представлены на рис. 2. Каждая из них отражает какой-либо уровень детализации работы элемента. Модель на рис. 2а соответствует функциональной модели. Подобная БС возможна для языка программирования, который реализует необходимые функциональные операторы. Здесь оператор y сразу соответствует логической функции И-НЕ. Но оператору на языке высокого уровня соответствует свой алгоритм и, как правило, множество операторов на уровне машинного языка. Например, на ассемблере алгоритму логической функции двух аргументов И-НЕ будет соответствовать алгоритм близкий к БС, показанной на рис. 2б. Одновременно эти блок-схемы отражают уровни иерархии или вложенности, допустимой в рамках модели БС. Например, блок-схема на рис 2.а может вызывать подпрограмму, представленную алгоритмом на рис. 2б и т.д. Уровень такой вложенности может быть достаточно большой.

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

На рис 2с. доведена до логического конца идея, позволяющая создать "реальную" модель элемента И-НЕ. Но наш элемент представляет собой часть триггера и поэтому данная БС отражает лишь гипотетически возможную программу (на уровне БС, конечно). Но зато она идеально, в рамках принятых соглашений по моделированию, описывает работу элемента.

2.2. Модель RS-триггера

Класс стандартных схем или в нашей формулировке модель блок-схем - это последовательная модель. Она не рассчитана на описание параллелизма. С ее помощью достаточно легко описать работу одиночного объекта (отдельный элемент И-НЕ), но создать модель, структурно аналогичную триггеру, и просто и сложно. Просто, т.к. соответствующее решение напрашивается само собой, но при этом мы должны выйти за рамки модели БС, а сложно, т.к. есть определенные сомнение в работоспособности такого параллельного расширения БС.

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

Блок-схема последовательного варианта триггера показана на рис. 3. Пока оставим в стороне вопрос "искусства" ее создания. Скажем лишь, что она правильно отражает все режимы работы триггера. Это доказуемо, в том числе и математически (как? - тема отдельного разговора). Но сразу обратим внимание, что даже внешне, мы имеем значительно более сложный алгоритм по сравнению с алгоритмами составляющих триггер компонент. И уже из этого можно предположить, что его проектирование - задача много сложнее, чем создание БС отдельного элемента И-НЕ.

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

3. Автоматная модель

Модель конечного автомата (КА) - другая модель управления схемы программ. Все остальное, память и операторы, можно оставить фактически тем же, что и у БС. Но при этом изменится форма ее представления. Теперь графическая форма - это граф переходов (ГП) конечного автомата. Кроме того, для КА удобна табличная форма описания - таблица переходов (ТП). При этом текстовый эквивалент КА реализуется с использованием обычных программных средств. Это может быть интерпретация ТП, как, например, это сделано в библиотеке FSA [7], или перевод в форму эквивалентную БС с использованием обычных управляющих конструкций языка программирования, как, например, в SWITCH-технологии [8].

Итак, абстрактный конечный автомат [9] - это кортеж или вектор S = (Q, Z, W, , , q₀), у которого

• Q = {q₀, q₁, : q_k} - множество состояний;
• Z = { z₀, z₁, : z_k } - множество входных сигнале;
• W = { w₀, w₁, : w_l } - множество выходных сигналов;
• : QZQ - функция переходов;
• : QZY - функция выходов;
• q₀ - начальное состояние.

Если функции и заданы на всем множестве QZ, автомат называется полностью определенным, в противном случае - частичным. В зависимости от вида функций и выделяют два основных типа (рода) автоматов: автоматы Мили и автоматы Мура. Закон функционирования используемой в FSA модели автомата Мили задается уравнениями:

q(t+1) = (q(t), z(t))	(7)
w(t) = (q(t), z(t))	(8)

Для удобного и детального моделирования программ "автоматной схемой" программ нужно перейти от абстрактного автомата к структурному автомату[9]. В нем учитывается состав входных и выходных сигналов, определяемых как входные и выходные наборы. Входным наборам соответствуют ситуации программы, представляющие собой конъюнкции, вычисляемые с помощью предикатов, а выходные наборы определяют множество выполняемых действий. Причем, если значение предиката P_i(x) (о понятии предиката см. дополнительно [4]) в конкретной ситуации истинно, то это обозначается как xi, в противном случае - i.

Рассмотрим на примере моделей элемента И-НЕ и триггера автоматную форму управления G схемы программы. А т.к. модель конечного автомата и модель БС эквивалентны друг другу (существует процедура перехода от БС к КА, рассмотренная в [9]), то ее можно получить, используя модели в форме БС. Кстати, обратная процедура не всегда однозначна, но тоже выполнима. Она аналогична процедуре перехода от таблиц решений (ТР) к БС [10] с учетом, что любая ТР это автомат с одним состоянием.

3.1. Модель элемента И-НЕ

Автоматные модели элемента И-НЕ, соответствующие моделям БС на рис.2, представлены на рис.4. На рис. 2 точки БС, соответствующие состояниям автомата, помечены одноименными символами - St, 00, S1, S0 (о самой процедуре разметки БС см. [9]). Начальное состояние КА (на БС - start) на графе переходов изображено кружком с утолщенной границей, конечное состояние, если оно есть (на БС - end), - состоянием с именем 00. Условным и операторным вершинам блок-схемы поставлены в соответствие предикаты и действия автомата с такими же именами. Входные наборы и выходные наборы определяются, исходя из путей между соседними отметками БС.

Заметим, что у графа на рис. 4с, как у БС на рис. 2с, нет конечного состояния. Т.е. это бесконечный или зацикленный автомат. "Бесконечность" не противоречит определению КА, т.к. у него обязательно присутствие только начального состояния.

3.2. Модель RS-триггера

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

Параллельная автоматная модель RS-триггера может быть такой, как показано на рис. 5а. На рисунке пунктирными дугами обозначены связи (синхронизация) между компонентными автоматами с помощью внутренних состояний. В представленной модели каждый элемент триггера представлен отдельным автоматом, а состояния выходов триггера (точнее, выходов элементов И-НЕ) моделируются состояниями компонентных автоматов. Подчеркнем, что такой подход позволил сэкономить на переменных, моделирующих сигналы на выходах элементов, и на действиях по их установке!

На рис 5б представлена последовательная или однокомпонентная автоматная модель триггера. Она получена алгебраическим "умножением" компонентных автоматов сети (это не столь просто, как 2*2, но чем-то похоже!). Полученная в результате этой операции однокомпонентная автоматная модель наглядно отражает весь процесс смены состояний выходов триггера как в статике, так и в динамике (например, при переключении между его устойчивыми состояниями виден переход через состояние 11). Из нее видны и условия вхождения триггера в режим генерации: установка (с последующей фиксацией) значений входов в состояние 11.

4. Сети Петри

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

Сеть Петри представляет собой ориентированный граф [11]

N = (T, P, F, M₀),

Где T - конечное множество вершин, называемых переходами; P - конечное множество вершин, называемых местами; F: PTPT{0, 1} - функция инцидентности, указывающая наличие дуг, связывающих места с переходами и переходы с местами; M₀:P{0, 1, 2, : } - начальная разметка.

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

О сетях Петри написано много. Об их недостатках в сравнении с автоматами см. в [8]. Их приложение к теории и практике параллельного программирования достаточно подробно описано в [11]. Подробнее о самой модели и ее возможностях можно прочитать в [12].

4.1. Модель элемента И-НЕ

На рис. 6 показана модель элемента И-НЕ в форме сети Петри. Ее места моделируют состояние выхода элемента. Наличие фишки соответствует наличию на выходе сигнала (на рисунке имена состояний выхода элемента проставлены рядом с соответствующими местами). Заранее зная, что моделируемый элемент будет взаимодействовать с другой сетью Петри, мы один из входов элемента моделируем состояниями соседней сети. Другой вход - потенциальный. В будущем это будет вход R или S триггера. Его состояния, как и состояния выходов, моделируются специально для этого введенными местами. На графе они изображены в форме эллипсов. Присутствие фишки здесь означает наличие на входе/выходе сигнала. Имя сигнала проставлено внутри места.

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

4.2. Модель RS-триггера

Модель RS-триггера в виде сети Петри можно создать на основе модели его базового элемента. Это сделать довольно просто, но будет ли она правильной это еще надо доказать! Пример такой композиции показан на рис. 7. Легко видеть, что это две копии сетей Петри элементов со связями между ними, соответствующими схеме триггера. На графе связи изображены пунктирными линиями. Соответственно выделены и части модели, соответствующие элементам И-НЕ триггера.

Чтобы понять правильно ли сеть Петри моделирует работу триггера, нужно провести анализ сети. Один из методов состоит в построении дерева достижимости. Оно показывает все маркировки, достижимые из начальной маркировки [12]. Отметим, что на графе начальная маркировка соответствует нулевым состояниям выходов триггера.

Мы не будем строить дерево маркировок и последовательную модель триггера в форме сети Петри. Во-первых, все это нужно для понимания работы параллельной модели, но такие эталонные варианты уже есть. Это последовательные модели в виде БС или КА. Во-вторых, например, последовательную модель нужно строить или интуитивно, на основе знания работы триггера, или с использованием математических методов, позволяющих строить правильные композиции моделей. Но даже в достаточно обширной и объемной литературе по сетям это прописано, к сожалению, не столь детально, да и делается не так просто, как того хотелось бы.

Кстати, возможно, что модель на рис.7 не отражает режим генерации триггера, т.к. синхронный переход из мест 11 в места 00 требует наличия двух фишек в местах 11. Это можно организовать, дублированием дуги из перехода, находящегося на пути из места 0 в 1 модели элемента И-НЕ (на рисунке дополнительные дуги изображены пунктиром)? Но как это повлияет тогда на маркировку сети в других режимах работы триггера? Это вопрос к специалистам по данной модели.

5. Рекурсивная модель

Наверное, разнообразие моделей столь же оправдано и неискоренимо, как и разнообразие естественных языков и языков программирования. Рекурсивная модель, которую реализует Лисп, относится к классу функциональных моделей, которая была рассмотренных первой. Программы на Лисп относятся к тому роду объектов, которые сложно описать - их нужно видеть воочию. И, возможно, изучать как произведения искусства - искусства программирования! К этому сложно привыкнуть, но, привыкнув, по мнению поклонников Лиспа, уже трудно мыслить по-иному.

В [13] приводится выражение, что "все языки программирования можно грубо разбить на два класса. В одном находится Лисп, в другом - все остальные". Сравнивая листинг программы на Лиспе с текстом программы на любом "обычном" языке в этом убеждаешься наглядно. Пытаясь вникнуть в смысл ее работы (алгоритма) - это начинаешь понимать.

Диапазон применения Лиспа сравним, по крайней мере, по приводимым в литературе примерам, с любыми другими языками программирования. В том числе, естественно, и с формальными моделями, которые им соответствуют. В этот диапазон входит и моделирование дискретных систем. В [14] говорится, что "с помощью символьной обработки и методов искусственного интеллекта особенно удобно моделировать многие дискретные системы." Не подвергая сомнению сказанное, попробуем все же разобраться насколько это соответствует действительности на примере триггера. Для чего рассмотрим пример его реализации непосредственно на языке Лисп. Листинг программы в этом случае, действительно, удобнее и нагляднее и скажет больше, чем попытка изобразить суть рекурсивного алгоритма в каком-либо графическом виде.

5.1. Модель RS-триггера

В листинге 1. представлена модель триггера, и элемента И-НЕ, которые создал Е. Трифонов (e-mail: trif@dvo.ru). Простота очевидна, но понять смысл их работы обычному программисту, к которым отношу и себя, несмотря на это, сложно. Но, может быть, это дело привычки?

Тем не менее, независимо от формы программа должна моделировать то, что есть на самом деле. Она должна подтвердить, что на Лисп "удобно моделировать многие дискретные системы". В "удобстве" (в первую очередь, конечно, для пишущих на Лиспе) ей отказать сложно. А вот насколько верно эта программа отражает реалии - должен показать эксперимент.

(defun nand (x y)                
  (not (and x y)))                          
;;;                        
(defun rs-trigger (r s q q-complement)        
  (list (nand s (nand q r))            
(nand r (nand s q-complement)))) 

Листинг 1. Программа моделирования RS-триггера на языке Лисп

(defun test (q q-complement)                    
    (flet ((digitize (boolean) (if boolean 1 0)))            
      (dolist (s '(nil t))                        
(dolist (r '(nil t))                            
  (let* ((qv (rs-trigger r s q q-complement))            
(nq (digitize (first qv)))                        
(nqc (digitize (second qv))))                    
(format t "~D ~D  |  ~D ~D~%" (digitize s) (digitize r) nq  nqc))))))    

Листинг 2. Программа моделирования RS-триггера на языке Лисп

Анализ программы (см. листинг 1) показывает, что результат достигается за счет повторного рекурсивного вызова функций, моделирующих элемент И-НЕ. Из-за определенного стереотипа "обычного" мышления, возможно, это сразу увидеть не удастся, но по истечении какого-то времени все, действительно, становится простым и ясным (может, все же стоит согласиться с поклонниками Лиспа?).

Пока мы отложим обсуждение результатов эксперимента, сказав лишь, что они достаточно показательны. Взамен этого, для еще одной демонстрации программ на Лисп приведем вариант модели (листинг 2) с двоичной, а не символьной, кодировкой сигналов (в чистом виде Лисп - язык обработки символьных данных). Насколько она проста и ясна - судить программистам (но, заметим, скобок стало уже заметно больше).

Выводы

Может ли машина мыслить? Вместо ответа на столь прямо поставленный вопрос Тьюринг предложил "игру", (см., например, [13]), которая, как предполагается, позволяет пролить свет на эту проблему. Суть ее в том, что если эксперт, тестирующий два объекта, один из которых человек, а другой машина, задавая им любые вопросы, не сможет распознать , то это позволяет сделать вывод об определенном уровне интеллекта машины (по крайней мере, сравнимом с интеллектом эксперта!). Но пока вопрос Тьюринга <существуют ли машины, способные успешно играть в эту игру?> ждет своего ответа, мы уже сейчас можем поиграть в игру: <есть ли системы, правильно реализующие параллельные процессы?>. Но для этого, как и в случае первой игры, нужно заранее подготовить список каверзных вопросов с уже известными ответами.

В сравнении с первой проблемой такой список сформировать проще. Один из вопросов предполагаемого списка мы выше и рассмотрели. Моделирование триггера - то, что нужно задать параллельной системе, может быть, в первую очередь. Как она его реализует, с помощью какой модели - это ее решение, как и тех кто эксплуатирует тестируемую систему/модель. Главное, что мы знаем правильный ответ. В конце концов, вторым эталонным объектом в игре может быть реальный триггер, собранный на реальных элементах, диаграмму работы которого можно сравнить с диаграммой работы параллельной модели.

Выше было предложено несколько моделей триггера. Автор с полной ответственностью отвечает за правильную работу автоматных моделей и моделей триггера в форме БС. Остальные модели - предположительно правильные. Насколько они правильны, мы выясним, создавая их программные аналоги (для рекурсивной модели программа уже имеется).

А пока мы ищем ответ на поставленные вопросы о мыслительных возможностях вычислительных машин, о себе мы можем сказать однозначно - мы мыслим по-разному! Разнообразие приведенных моделей это демонстрирует. Учтите, что мы еще не рассмотрели "разнообразие мышления" в рамках моделей! И надо ли удивляться тому, что при всей мощи современной вычислительной техники (в сравнении, конечно, с не столь давними временами), вычислительные машины мыслить так и не научились. А может у них свой взгляд на этот процесс, и мыслят они как-то по-иному?

Литература

1. Любченко В.С. Фантазия или программирование? "Мир ПК", №10/97, с.116-119.
2. Толковый словарь по вычислительным системам/Под ред. В. Иллингоута и др.: Пер. с англ. А.К. Белоцкого и др.; Под ред. Масловского. - М.: Машиностроение, 1991. - 560 с.
3. Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебное пособие для студентов вузов. - М.: <Высшая школа>, 1972. - 344 с.
4. Котов В.Е. Введение в теорию схем программ. Новосибирск.: Наука, 1978. -258с.
5. Карп P.M., Миллер Р.Е. Параллельные схемы программ. - В кн. Кибернетический сборник (новая сер.). М.: Мир, 1975, вып.13, с. 5-61.
6. И.П. Соловьев. Формальные спецификации вычислительных систем. Машины абстрактных состояний (машины Гуревича). Учебно-методическое пособие. СПбГУ, 1998. - 31 с.
7. Любченко В.С. О бильярде с Microsoft C++ 5.0. <Мир ПК>, № 1/98, с.202-206.
8. А.А. Шалыто. SWITCH-технология. Алгоритмизация и программирование задач логического управления. - СПб.: Наука, 1998. - 628 с.
9. Баранов С.И. Синтез микропрограммных автоматов. -Л.: Энергия, 1979 -232 с.
10. Хамби Э. Программирование таблиц решений. М.: Мир, 1976. - 86 с.
11. Элементы параллельного программирования/В.А. Вальковский, В.Е. Котов, А.Г. Марчук, Н.Н. Миренков; Под ред. В.Е. Котова. - М.: Радио и связь, 1983. - 240с.
12. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер с англ. - М.: Мир, 1984. - 264с.
13. Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. Т.1: Введение в язык Лисп и функциональное программирование. Пер. с финск. - М.:Мир, 1990. - 447 с.
14. Нивергельт Ю., Фаррар Дж., Рейнголд Э. Машинный подход к решению математических задач: Пер. с англ. - М: Мир, 1977. - 352 с.