Введение в схемы, автоматы и алгоритмы


           

Из этого определения непосредственно следует,


копирует свой вход с разделителем #, т.е. по любому входу w выдает w # w.

Через E обозначим м.Т., которая ничего не делает.

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


в
, где z= g(x1,… ,xn, y)

? на входе вида w # v проверяет непустоту v (т.е. условие v > 0).



Таким образом, при v=g(x1,…,xn,y) машина ? проверяет условие g(x1,…,xn,y)
0.

по входу вида
стирает #w и прибавляет к y единицу, т.е. выдает результат:


Наконец,
по входу
выдает |y, стирая ненужные блоки символов.

Ясно, что каждая из перечисленных м.Т.
,
,
,
и ? легко реализуема. Построим теперь с их помощью следующую м.Т.




Из этого определения непосредственно следует, что
вычисляет функцию fn(x1,…, xn), заданную с помощью оператора минимизации.


Содержание  Назад  Вперед