Мониторинг обменных курсов валют
18c0693f

Вычислимость частично рекурсивных функций по Тьюрингу


Теорема 10.1. Для всякой ч.р.ф. f существует м.Т.

вычисляющая функцию f.

Доказательство. Доказательство проведем индукцией по определению частично рекурсивной функции f.

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

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

Суперпозиция. Пусть Fm и fn1,…, fnm

- ч.р.ф., вычислимые на м.Т.

соответственно. Пусть функция Gn получена из них с помощью суперпозиции: Gn=[Fm;fn1,…, fnm]. Тогда м.Т.

вычисляющая G, работает следующим образом:

  1. m раз копирует вход
    отделяя одну копию от другой символом #;
  2. на полученном слове вида
  3. запускает параллельную композицию машин
    и получает конфигурацию вида
    где yi=fi(x1,…,xn) (i
    [1,m]).
  4. заменяет все символы 0023 на *;
  5. затем запускает программу м.Т.
    на получившемся после этапа 3) входе вида
    и вычисляет требуемое значение

Если обозначить м.Т., выполняющую копирование на этапе (1), через Копm, а м.Т., выполняющую замену # на * на этапе (3), через Зам*#, то требуемую для суперпозиции м.Т.

можно представить как

Примитивная рекурсия. Пусть функция Fn+1(x1,… ,xn,y) получена с помощью оператора примитивной рекурсии из функций gn(x1,…, xn) и fn+2(x1,… ,xn, y, z), которые вычислимы на м.Т.

и
. Определим вспомогательные м.Т.:

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

Минимизация. Пусть fn(x1,…, xn) = ? y [ gn+1(x1,…, xn,y)=0] и м.Т.

вычисляет функцию gn+1. Определим следующие вспомогательные м.Т.:

приписывает аргумент 0 ко входу, т.е. вход вида
переводит в конфигурацию на ленте
(напомним, что при унарном кодировании 0 соответствует пустой символ).


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




Самый выгодный курс обмена валюты