1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

Пусть k > 1. Не существует (k+1)-местной п.р.ф., универсальной для семейства всех k-местных п.р.ф.Доказательство. Допустим, напротив, F (x0 , x1 , . . . , xk ) — п.р.ф., универсальная длясемейства всех k-местных п.р.ф., т. е. {F (0, x1 , . . .

, xk ), F (1, x1 , . . . , xk ), . . .} — классвсех k-местных п.р.ф. Определим k-местную функцию:f (x1 , . . . , xk ) = F (x1 , x1 , x2 , . . . , xk ) + 1.Тогда f (x1 , . . . , xk ) — п.р.ф. Следовательно, в силу универсальности F найдется n ∈ω такой, что для всех x1 , . . . , xk ∈ ω выполняется F (n, x1 , . . . , xk ) = f (x1 , . . . , xk ).Рассмотрим значения x1 = n, x2 = . . . = xk = 0. Тогда получаем:F (n, n, 0, .

. . , 0) = f (n, 0, . . . , 0) = F (n, n, 0, . . . , 0) + 1.Противоречие.Предложение 62. Пусть k > 1. Не существует (k+1)-местной р.ф., универсальной для семейства всех k-местных р.ф.Доказательство. Повторяет доказательство предложения 61.Замечание. Условие k > 1 в формулировках предложений 61 и 62 присутствуетне случайно. Для семейства всех 0-местных п.р.ф. (которое совпадает с семействомвсех 0-местных р.ф.) существует универсальная п.р.ф. — это, очевидно, 1-местнаяфункция F (x) = x.Диагональный метод доказательства предложения 61 существенно опирается напредположение о примитивной рекурсивности функции F (x0 , x1 , .

. . , xk ). Если этопредположение ослабить и считать, что F (x0 , x1 , . . . , xk ) — рекурсивная, то диагональные рассуждения уже ни к чему не приводят, т. е. не доказывают отсутствияр.ф., универсальной для семейства всех п.р.ф. Более того, справедливо следующееутверждение, которое мы приводим без доказательства.Предложение 63. Существует (k+1)-местная р.ф., универсальная для семействавсех k-местных п.р.ф.Полное доказательство предложения 63 изложено в [5]. В основе этого доказательства лежат теорема Робинсона о том, что все 1-местные п.р.ф. можно получить82Глава IV. Теория вычислимости√ 2¦из функций s(x) = x+1 и q(x) = x−[ x] операциями сложения, суперпозиции и итерирования функций, и теорема о рекурсивности функций, полученных из некоторыхп.р.ф. с помощью рекурсии 2-й ступени.Из предложения 63 вытекает важное следствие, утверждающее, что класс всехп.р.ф.

не совпадает с классом всех р.ф. Напомним, что справедливы следующиетеоретико-множественные включения:ПРФ ⊆ РФ ⊆ ЧРФ.Каждое из этих включений — строгое. Второе включение является строгим, поскольку, очевидно, существуют не всюду определенные ч.р.ф. Например, нигде не определенная функция f = µx[s(x) = 0] является ч.р.ф. Докажем, что первое включениеявляется строгим.Следствие 64. Существует рекурсивная функция, не являющаяся примитивнорекурсивной.Доказательство. Пусть F (x, y) — р.ф., универсальная для семейства всех 1-местныхп.р.ф., которая существует в силу предложения 63. Если бы F (x, y) была примитивнорекурсивной, то она была бы п.р.ф., универсальной для семейства всех 1-местныхп.р.ф., что невозможно в силу предложения 61.Существует другой известный пример рекурсивной функции, которая не являетсяпримитивно рекурсивной, — это так называемая функция Аккермана.

Определениеи свойства функции Аккермана можно найти в [5].Вопрос о существовании универсальной функции можно исследовать не толькодля семейств всех k-местных ч.р.ф., р.ф. или п.р.ф. Для дальнейших целей нампотребуется универсальная функция для семейства всех полиномов.Предложение 65. Существует 2-местная вычислимая функция, универсальнаядля семейства всех полиномов от одной переменной с натуральными коэффициентами.Доказательство.

Если f (x) = an xn + an−1 xn−1 + . . . + a1 x + a0 — полином, ai ∈ ω,n ∈ ω, то сопоставим ему код(f ) =< a0 , a1 , . . . , an >= pa00 +1 · pa11 +1 · . . . · pann +1 , гдеp0 = 2, p1 = 3, p2 = 5, . . . — перечисление простых чисел в порядке возрастания.Заметим, что если k = код(f ), то степень полинома f находится с помощью вы¦¦числимой функции lh(k)−1 = µi[ex(i, k) = 0]−1, а i-й коэффициент f находится с¦помощью вычислимой функции (k)i = ex(i, k)−1.Определим двухместную вычислимую функцию¦1lh(y)−F (y, x) =X(y)i · xi .i=0Тогда, с одной стороны, если у функции F (y, x) зафиксировать значение y, тополучится некоторый полином от переменной x с натуральными коэффициентами.С другой стороны, если f — произвольный полином, то F (код(f ), x) = f (x).

Такимобразом, F — искомая универсальная функция.§ 21. Универсальные функции83Теперь мы более детально изучим свойства универсальной функции для семейства всех одноместных частично вычислимых функций. Для данного семейства мы,используя кодирование машин Шёнфилда, построили универсальную клиниевскуюфункцию æn (x). Клиниевская универсальная функция обладает важным свойством— она сама является частично вычислимой функцией от переменных n, x.

Но, кроме частичной вычислимости, функция æn (x) обладает еще другим, пожалуй, болееважным свойством — для клиниевской нумерации одноместных ч.в.ф. справедлива теорема о параметризации: для любой двухместной ч.в.ф. f (n, x) существуетразнозначная в.ф. s(n) такая, что f (n, x) = æs(n) (x).Это наблюдение лежит в основе следующего определения.Определение. Двухместная ч.в.ф. ψn (x) называется сильно универсальной, еслидля любой ч.в.ф. f (n, x) существует разнозначная в.ф. s(n) такая, что f (n, x) =ψs(n) (x).Предложение 66.

Любая сильно универсальная ч.в.ф. является универсальной длясемейства всех одноместных ч.в.ф.Доказательство. Пусть ψn (x) — сильно универсальная ч.в.ф., f (x) — произвольнаяодноместная ч.в.ф. Рассмотрим двухместную ч.в.ф. F (n, x) = f (x). В силу сильнойуниверсальности найдется разнозначная в.ф. s(n) такая, что ψs(n) (x) = F (n, x) =f (x). В частности, для любого m = s(n) имеет место ψm (x) = f (x). Таким образом,ψn (x) — универсальная для семейства всех одноместных ч.в.ф.Предложение 67. Существует двухместная ч.в.ф., которая является универсальной для семейства всех одноместных ч.в.ф., но не является сильно универсальной.Доказательство.

Определим двухместнуюне определено,ψx (y) = (x)0 − 1,æ(x)1 (y),частичную функциюесли y = 0 и (x)0 = 0,если y = 0 и (x)0 > 0,если y > 0.Докажем, что ψx (y) частично вычислима. Для этого заметим, что для произвольныхx, y, z ∈ ω имеет место:³´ ³´ψx (y) ↓= z ⇐⇒ (x)0 >0 & y=0 & z=(x)0 − 1 ∨ y>0 & æ(x)1 (y) ↓ & z=æ(x)1 (y)³´³´⇐⇒ (x)0 > 0 & y = 0 & z = (x)0 − 1 ∨ ∃t y > 0 & T1 ((x)1 , y, t) & z = U (t) .Отсюда в силу теоремы об эквивалентных определениях в.п.

множеств заключаем,что график функции ψx (y) вычислимо перечислим. Следовательно, ψx (y) частичновычислима.Докажем, что ψx (y) — универсальная. Пусть æe (y) — произвольная одноместнаяч.в.ф. Если æe (0) ↑, то, положив n =< 0, e >, заключаем, что ψn (y) = æe (y). Еслиже æe (0) ↓ и æe (0) = m, то, определив n =< m + 1, e >, получаем, что ψn (y) = æe (y).Что и требовалось доказать.Допустим теперь, что ψx (y) — сильно универсальная. Рассмотрим двухместнуюклиниевскую ч.в.ф. æx (y). В силу сильной универсальности ψ заключаем, что существует разнозначная в.ф. s(x) такая, что ψs(x) (y) = æx (y).

Тогда имеет место эквивалентность¡¢æx (0) ↓ ⇐⇒ ψs(x) (0) ↓ ⇐⇒ s(x) 0 > 0.84Глава IV. Теория вычислимости¡¢Множество {x ∈ ω | s(x) 0 > 0} очевидно вычислимо. Однако множество {x ∈ ω |æx (0) ↓} в силу теоремы Райса невычислимо. Противоречие. Таким образом, ψx (y)не является сильно универсальной.Итак, совокупность всех универсальных ч.в.ф можно разбить на две непустыечасти.

Первая часть — это все сильно универсальные функции, сюда попадает клиниевская универсальная функция æn (x). Вторая часть — это все слабо универсальныефункции, т. е. функции, которые являются универсальными, но не являются сильноуниверсальными. Оказывается, все функции из первой части в определенном смысле эквивалентны друг другу, и доказательству этого свойства посвящен следующийпараграф.§ 22.Единственность сильно универсальной функцииЕдинственный пример сильно универсальной функции, который нам пока известен,— это клиниевская универсальная функция æn (x). Мы определили ее, используя технику кодирования вычислений на машинах Шёнфилда. Вообще говоря, клиниевскуюуниверсальную функцию можно было построить другим способом, используя терминологию машин Тьюринга или нормальных алгорифмов Маркова.

Кроме этого,можно было использовать другую кодировку кортежей, команд и машин. Каждыйиз описанных способов в результате приводит к той или иной сильно универсальной функции. Поэтому возникает естественное опасение: возможно, какая-нибудьуниверсальная функция из данного многообразия более приемлема, чем остальные.Насколько различными могут получиться универсальные функции?Оказывается, все универсальные функции, для которых справедлива теорема опараметризации, т. е. все сильно универсальные функции, практически не отличаются в алгоритмическом смысле.

Каждую сильно универсальную функцию можно получить из любой другой с помощью вычислимого изоморфизма. Можно дажеутверждать, что с точностью до вычислимого изоморфизма сильно универсальнаяфункция единственна, а построенная нами конкретная функция æn (x) ничем не хужеи не лучше остальных.Для доказательства теоремы о вычислимом изоморфизме сильно универсальныхфункций нам потребуются следующие три леммы.Лемма 68.

Пусть ψn (x) — сильно универсальная функция. Тогда для любой ч.в.ф.f (x, y, z) существует разнозначная в.ф. g(x, y) такая, что f (x, y, z) = ψg(x,y) (z).Доказательство. Рассмотрим двухместную ч.в.ф. f 0 (t, z) = f ((t)0 , (t)1 , z). В силусильной универсальности ψ существует разнозначная в.ф. s(t) такая, что f 0 (t, z) =ψs(t) (z). Подставим t =< x, y >, получим f (x, y, z) = f 0 (< x, y >, z) = ψs(<x,y>) (z).Обозначим g(x, y) = s(< x, y >). Так как s и < ·, · > — разнозначные, то gтоже разнозначная. Так как s и < ·, · > — вычислимые, то g тоже вычислимая.Следовательно, g — искомая.Лемма 69. Пусть ψn (x) — сильно универсальная функция.

Характеристики

Список файлов лекций