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

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

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

Доказательство этой теоремы - дополнительный материал, который можно при первом чтении опустить.

Доказательство Пусть м.Т.

вычисляет функцию f(x1,…, xn). Пусть также Q ={q0,q1,… ,q k-1 }, qf=q1 и ? = {a0=, a1, … , a R-1= | }. Предположим также, не ограничивая общности, что никогда не пишет пустой символ (как перестроить программу произвольной м.Т., чтобы она удовлетворяла этому условию ?).

Определим кодирование элементов конфигураций

целыми числами. Пусть конфигурация имеет вид K=(w1,qi,aj,w2), где - слово на ленте левее головки, qi - состояние м.Т., aj - наблюдаемый в данной конфигурации символ и w2= aj0aj1 … ajp} - слово на ленте правее головки. Кодом символа aj ? будет число j, кодом состояния qi - число i. Слова w1 и w2 будем рассматривать как числа в R-ичной системе счисления, читаемые в противоположных направлениях (из наших предположений следует, что im 0 при m >0 и jp 0 при p>0) :

Например, если ?= {

, *, |}, то для конфигурации K=(|**,q3,|,* | |) имеем code1(w1)=30 1+31 1+ 32 2= [211]3=22 и code2(w2)=30 1+ 31 2 +32 2= [221]3=25. По программе P определим следующие табличные функции, кодирующие ее команды:

A(i,j) - код символа, который пишет

когда она в состоянии qi видит символ aj;

Q(i,j) - код состояния, в которое переходит

когда она в состоянии qi видит символ aj;

C(i,j) - код направления сдвига головки

когда она в состоянии qi видит символ aj (0 - на месте, 1 - вправо, 2 - влево).

Пусть при i

k или j R эти функции принимают какое-нибудь фиксированное значение (например, 0). Тогда по лемме 18.1 все они примитивно рекурсивны.

Определим функции, которые по кодам компонент одной конфигурации K=(w1,qi,aj,w2) вычисляют коды компонент следующей конфигурации K’=(w1’,qm,ap,w2’).

Покажем, что все эти функции примитивно рекурсивны.
Для q это следует из того, что для любых i, j q(l,i,j,m)=Q(i,j). Определения остальных трех функций зависят от сдвига. При C(i,j)=0 имеем lf(l,i,j,r)=l, rt(l,i,j,r)= r, a(l,i,j,r)=A(i,j).

Если C(i,j)=2, то lf(l,i,j,r)=div(R, l), rt(l,i,j,r)= rR+A(i,j), a(l,i,j,r)=rm(R,l). Если же C(i,j)=1, то lf(l,i,j,r)=lR+A(i,j), rt(l,i,j,r)= div(R, r), a(l,i,j,r)=rm(R,r) Объединяя эти случаи получаем, что

( здесь rm(x,y) - это функция, дающая остаток от деления y на x, а div(x,y) - функция целочисленного деления y на x).

Аналогичные представления справедливы и для функций rt(l,i,j,r) и a(l,i,j,r). Следовательно, все эти функции примитивно рекурсивны.

Пусть из данной конфигурации K через t тактов получается конфигурация Kt. Определим коды компонент Kt как функции от компонент K и t :



Это определение задает функции A(4), Q(4), Lf(4), Rt(4) с помощью совместной рекурсии. Следовательно, по лемме 18.5 они примитивно рекурсивны.

Пусть м.Т. вычисляет функцию f(x), (т.е. n=1). Тогда для начальной конфигурации Kx=K0=(,q0,|,|x-1) code1(w1)=0, code(q0)=0, code(|)=R-1, code2( w2 ) = (R-1)Rx-2+(R-1)R x-3+ … +(R-1)R0=R x-1-1. Положим и Тогда функция задает число шагов до перехода в заключительное состояние на входе x. Эта функция, очевидно, частично рекурсивна. Тогда функция задает код правой части заключительной конфигурации, имеющий вид Rf(x)-1-1. Отсюда получаем, что



и следовательно, функция f(x) частично рекурсивна.

Моделирование структурированных программ машинами Тьюринга

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

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

Доказательство Пусть структурированная программа ? вычисляет арифметическую функцию f(x1, …, xn). Не ограничивая общности, будем считать, что Var? ={x1, …, xn, xn+1, …, xm } и что результирующей переменной является x1.

М.Т. M? , моделирующая ?, будет иметь m-этажную ленту с алфавитом ? ={

, |, *} {, |}m. Обозначим конфигурацию ленты M\Pi, в которой на i-ом этаже, начиная с 1-ой ячейки, записано слева направо ki символов '|' (i = 1, 2, …, m), а далее идут "пустышки " , как (k1, k2, …, km). Тогда состоянию ?: Var{?} N программы ? будет соответствовать конфигурация ленты M?: K? =(?(x1),?(x2),… , ?(xm)).

M? получается с помощью конструкций последовательной композиции, условного оператора и цикла из простых машин Тьюринга, реализующих элементарные присваивания и условия структурированных программ.

Команду xi := 0 (i=1,… , m) программы ? реализует м.Т. Mi0 , обнуляющая i-ый этаж M, т.е. переводящая любую конфигурацию (k1,…, ki-1,ki, k i+1 …, km) в конфигурацию (k1,…, k i-1, 0, ki+1, … , km). Команду xi := xi +1 (i=1,… , m) программы ? реализует м.Т. Mi+1 , добавляющая один символ '|' справа на i-ом этаже, т.е. переводящая любую конфигурацию (k1,…, k i-1, ki, ki+1 … , km) в конфигурацию (k1,…, k i-1, ki+1, ki+1, … , km). Команду xi := xj (i, j=1,… , m) программы ? реализует м.Т. Mij, переписывающая содержимое j-го этажа на i-ый, т.е. переводящая любую конфигурацию (k1,…, ki, …, kj, … , km) в конфигурацию (k1,…, kj, … , kj, … , km).

Условие xi = xj реализуется машиной ? =ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki=kj, и 1 - в противном случае.

Условие xi < xj реализуется машиной ?<ij, которая, работая на конфигурации (k1, …, ki, …, kj, … , km) выдает 0, если ki < kj, и 1 - в противном случае.

Далее по индукции: пусть ?1 и ?2 - структурированные программы, для которых построены соответствующие машины Тьюринга и , а ? - некоторое условие, реализуемое м.Т. M?. Тогда программа ?= ?1 ; ?2 реализуется машиной

программа ?= если ? то ?1 иначе ?2 конец

реализуется машиной M?= if M? then M?1 else M?2 endif, а программа ?= пока ? делай ?1 все реализуется машиной M?= while M? do M?1 enddo.

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

Утверждение 1. Пусть м.Т. M? реализует в соответствии с приведенными определениями структурированную программу ?. Тогда для любого состояния ? программы ? ?(?) = ?1 тогда и только тогда, когда м.Т M?, начав работу в конфигурации K? завершит ее в конфигурации K?1.

Теперь для завершения доказательства теоремы достаточно взять в качестве результирующей следующую м.Т.: M = Mstart; M?; Mend, где м.Т. Mstart переводит одноэтажную начальную конфигурацию в m-этажную конфигурацию (x1, x2,…, xn, 0,…, 0), а м.Т. Mend заключительную m-этажную конфигурацию (x1, 0,…, 0) переводит в одноэтажную заключительную конфигурацию |x1.

Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы

Мы рассмотрели три математические модели для описания алгоритмов и вычисляемых ими функций, отражающие различные аспекты и представления о работе абстрактного вычислителя. Из теорем 8.1, 10.2 и 10.3 непосредственно получаем

Следствие. Классы функций, вычислимых с помощью структурированных программ, машин Тьюринга и частично рекурсивных описаний, совпадают.

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

Тезис Тьюринга-Черча:

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

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

Можно ли доказать этот тезис как теорему? Нет, поскольку в его формулировке речь идет о неточных понятиях "всякого алгоритма" и "вычислимой функции", которые не могут быть объектами математических рассуждений. На чем же тогда основана уверенность в справедливости тезиса Тьюринга-Черча? В первую очередь, на опыте. Все известные алгоритмы, придуманные за многие века математиками, могут быть заданы с помощью машин Тьюринга. Для всех многочисленных моделей алгоритмов, появившихся за последние 70 лет (некоторые из них мы упоминали в начале лекции), была доказана их равносильность машинам Тьюринга.

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

Чтобы показать связь теории алгоритмов с "практическим" программированием, рассмотрим некоторые алгоритмичские проблемы, связанные со структурированными программами.

Зафиксируем конечный алфавит A={a0, a1,…, am-1}, включающий все символы латинского алфавита, цифры, знак пробела (пусть это будет a0), знаки ';', '=', '<', ':=' , а также знаки-ключевые слова если, то, конец, пока, делай и все. Тогда каждая структурированная программа ? представляет собой некоторое слово в алфавите A. Не ограничивая общности, будем считать, что это слово начинается не с пробела, т.е. i1 >0. Тогда слово w? однозначно определяет натуральное число n?, m-ичной записью которого оно является, т.е. Назовем это число номером программы ?. По тексту программы ? ее номер n? определяется однозначно. Рассмотрим теперь обратное соответствие. Конечно, не каждое число является номером некоторой структурированной программы. Поэтому сопоставим каждому числу n N структурированную программу ?n следующим образом: если n=n? для некоторой программы ?, то ?n=?, иначе, т.е. когда n не является "естественным" номером никакой программы, сопоставим ему в качестве ?n

некоторую никогда не останавливающуюся программу P (например, программу ?5(1): x1 := x1; пока x1=x1 делай x1:=x1 все из примера 7.5).

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

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

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

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

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

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

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

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

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

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

m раз копирует вход

отделяя одну копию от другой символом #;на полученном слове вида запускает параллельную композицию машин и получает конфигурацию вида где yi=fi(x1,…,xn) (i [1,m]).заменяет все символы 0023 на *;затем запускает программу м.Т. на получившемся после этапа 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), заданную с помощью оператора минимизации.

и минимизации, действительно правильно реализуют

Задача 10.1. Докажите, что машины Тьюринга и определенные в доказательстве теоремы 10.1 для примитивной рекурсии и минимизации, действительно правильно реализуют указанные операторы.
Задача 10.2. Постройте машины Тьюринга Mi0 , Mi+1, Mij, ? ij =, ? ij<, Mstart и Mend, определенные в доказательстве теоремы 10.2.
Задача 10.3.
Докажите утверждение 1, сформулированное в доказательстве теоремы 10.2, используя индукцию по построению программы ? и соответствующей м.Т. M?.
Задача 10.4. В доказательстве теоремы 10.3 рассмотрен случай, когда м.Т. вычисляет функцию от одного аргумента f(x) . Покажите, что теорема верна и в общем случае для функций f(x1,…,xn) при любом n.
Задача 10.5.
Докажите, что отношение алгоритмической сводимости m является рефлексивным и транзитивным.
Задача 10.6.
Доказать алгоритмическую неразрешимость следующих проблем.
По произвольной программе ? определить, является ли вычисляемая ей функция ??,y(x) постоянной константой.По произвольной программе ? и числам a и b проверить равенство ??,y(a)=b.По произвольной программе ? определить, является ли множество значений вычисляемой ею функции ??,y(x) бесконечным.По произвольной паре программ ? и ?' проверить, что для всех x имеет место неравенство ??,y(x) > ??',y(x).
Задача 10.7. Докажите, что
пересечение двух разрешимых множеств является разрешимым множеством.объединение двух разрешимых множеств является разрешимым множеством.
Задача 10.8.
Докажите, что для двух разрешимых множеств A и B их "сумма" A+B={ x+y | x A, y B} также является разрешимым множеством.
Задача 10.9. Пусть A - разрешимое множество, а g(x) и h(x) являются о.р.ф. Докажите, что функция

также является общерекурсивной.

---

---