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

Теорема 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), которые вычислимы на м.Т.

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

• 
  используя
  
  строит по входу вида
  
  конфигурацию на ленте
  
• 
  используя
  
  строит по входу вида
  
  конфигурацию
  
• 
  на входе вида
  
  выдает в качестве результата
  
• ? на входе вида
  
  проверяет условие y
  
  u.

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

Минимизация. Пусть 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), заданную с помощью оператора минимизации.


Содержание раздела

---

---