Из этого определения непосредственно следует,
копирует свой вход с разделителем #, т.е. по любому входу 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), заданную с помощью оператора минимизации.
Содержание Назад Вперед
