1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 19
Текст из файла (страница 19)
. , fk (n)i, где n ∈ ω. Если Tk (e, (n)1 , . . . , (n)k , (n)0 ) ложно,то hf1 (n), . . . , fk (n)i = a ∈ A и все доказано. Пусть Tk (e, (n)1 , . . . , (n)k , (n)0 ) истинно.Тогда по определению T -предиката Клини z = (n)0 является кодом вычисления попрограмме с кодом e и входом x = h(n)1 , . . . , (n)k i, причем этот z является единственным, удовлетворяющим этому условию. Следовательно, z = µy[Tk (e, x, y)]. Отсюда заключаем, что значение f (x) = U (µy[Tk (e, x, y)]) определено. Таким образом,hf1 (n), .
. . , fk (n)i = h(n)1 , . . . , (n)k i = x ∈ dom(f ) = A.Переформулируем отдельно теорему об эквивалентных определениях в.п. множеств для 1-местных отношений, добавив еще одно, четвертое эквивалентное условие.Следствие 51. Для произвольного множества A ⊆ ω следующие условия эквивалентны:1) A вычислимо перечислимо.2) Существует вычислимое отношение R ⊆ ω 2 такое, чтоx ∈ A ⇐⇒ ∃yR(x, y).3) Существует частично вычислимая функция f (x) такая, что A = dom(f ).4) Существует частично вычислимая функция f (x) такая, что A = range(f ).Доказательство.
Эквивалентность условий (1), (2) и (3) доказана в теореме 50. Покажем, что условие (4) эквивалентно условиям (1)–(3).Пусть A удовлетворяет условию (3), т.е. A = dom(f ) для некоторой ч.в.ф. f (x).Определим частично вычислимую функцию g(x) = x + o(f (x)). Тогда range(g) =dom(g) = dom(f ) = A, т. е. A удовлетворяет условию (4).Пусть теперь A удовлетворяет условию (4), т.
е. A = range(f ), где f — ч.в.ф.Тогда f вычислима на некоторой машине Шёнфилда с кодом e. По теореме Клинио нормальной форме f (x) = U (µt[T1 (e, x, t)]), где U и T1 — вычислимые. Отсюдаполучаем:¡¢y ∈ A ⇐⇒ ∃x(f (x) ↓= y) ⇐⇒ ∃x∃t T1 (e, x, t) & U (t) = y .Закодируем пару hx, ti одним числом z =< x, t >. Тогда имеет место эквивалентность¡¢y ∈ A ⇐⇒ ∃z T1 (e, (z)0 , (z)1 ) & U ((z)1 ) = y .Поскольку отношение R = {hy, zi | T1 (e, (z)0 , (z)1 ) & U ((z)1 ) = y} является вычислимым, то отсюда следует, что A удовлетворяет условию (2).Выясним теперь, как соотносятся между собой семейство всех в.п. множеств исемейство всех вычислимых множеств.78Глава IV. Теория вычислимостиПредложение 52. Если A ⊆ ω k вычислимо, то A вычислимо перечислимо.Доказательство.
Пусть A вычислимо, следовательно, функция XA (x1 , . . . , xk ) вычислима. Определим частичную функцию f (x) = µy[|XA (x) − 1| = 0]. Тогда f —ч.в.ф. и dom(f ) = A. Следовательно, в силу пункта (3) теоремы 50 A являетсяв.п. множеством.Утверждение, обратное к предложению 52, вообще говоря, неверно.Предложение 53. Существует в.п. множество K ⊆ ω, которое не является вычислимым.Доказательство. Рассмотрим множество K = {x ∈ ω | æx (x) ↓}. По теореме 47оно не вычислимо. Докажем, что K вычислимо перечислимо. По теореме Клини онормальной форме æx (y) = U (µt[T1 (x, y, t)]).
Тогда имеем:x ∈ K ⇐⇒ æx (x) ↓ ⇐⇒ U (µt[T1 (x, x, t)]) ↓ ⇐⇒ ∃t T1 (x, x, t).Отсюда по пункту (2) теоремы 50 заключаем, что K вычислимо перечислимо.Далее мы исследуем свойства замкнутости семейства в.п. множеств относительно теоретико-множественных операций. Напомним, что для вычислимых множествсправедливо следующееПредложение 54.
Пусть A, B ⊆ ω k — вычислимые множества. Тогда множестваA ∪ B, A ∩ B и ω k \ A тоже вычислимы.Доказательство. См. доказательство предложения 21.Для семейства в.п. множеств замкнутость относительно объединения и пересечения остается справедливой. Однако, в отличие от вычислимых множеств, в.п. множества незамкнуты относительно дополнения.Предложение 55. Пусть A, B ⊆ ω k — вычислимо перечислимые множества. Тогда множества A ∪ B и A ∩ B тоже вычислимо перечислимы.Доказательство. Пусть P, R ⊆ ω k+1 такие вычислимые множества, чтоx ∈ A ⇐⇒ ∃yP (x, y),x ∈ B ⇐⇒ ∃yR(x, y).Тогда для объединения получаем:³´³´x ∈ A ∪ B ⇐⇒ ∃yP (x, y) ∨ ∃yR(x, y) ⇐⇒ ∃y P (x, y) ∨ R(x, y) ⇐⇒ ∃yQ(x, y),где Q(x, y) = P (x, y) ∨ R(x, y) — вычислимый предикат.
Следовательно, A ∪ B вычислимо перечислимо.Для пересечения имеем:³´³´x ∈ A ∩ B ⇐⇒ ∃yP (x, y) & ∃zR(x, z) ⇐⇒ ∃y∃z P (x, y) & R(x, z) ⇐⇒³´⇐⇒ ∃t P (x, (t)0 ) & R(x, (t)1 ) ⇐⇒ ∃tQ(x, t),где Q(x, t) = P (x, (t)0 ) & R(x, (t)1 ) — вычислимый предикат. Следовательно, A ∩ Bвычислимо перечислимо.§ 20. Вычислимо перечислимые множества79Теорема 56 (теорема Поста). Множество A ⊆ ω k вычислимо тогда и только тогда, когда A и ω k \ A вычислимо перечислимы.Доказательство. (=⇒) Следует из замкнутости вычислимых множеств относительно дополнения и предложения 52.(⇐=) Пусть P, R ⊆ ω k+1 такие вычислимые множества, чтоx ∈ A ⇐⇒ ∃yP (x, y),x∈/ A ⇐⇒ ∃yR(x, y).Определим вычислимую функцию f (x) = µy[P (x, y) ∨ R(x, y)]. Тогда получаем: x ∈A ⇐⇒ ∃yP (x, y) & ∀y¬R(x, y) ⇐⇒ P (x, f (x)).
Поэтому XA (x) = XP (x, f (x))является вычислимой функцией. Таким образом, A вычислимо.Следствие 57. Существует множество A ⊆ ω такое, что A вычислимо перечислимо, но ω \ A не является вычислимо перечислимым.Доказательство. Рассмотрим множество K = {x ∈ ω | æx (x) ↓}. По предложению53 K — в.п. Если бы ω \ K было в.п., то по теореме Поста K было бы вычислимым,что невозможно.Теорема 58 (теорема о графике). Частичная функция f (x1 , .
. . , xk ) является частично вычислимой тогда и только тогда, когда ее графикΓf = {hx1 , . . . , xk , yi | hx1 , . . . , xk i ∈ dom(f ), f (x1 , . . . , xk ) = y}является вычислимо перечислимым.Доказательство. (=⇒) Пусть f — ч.в.ф. По теореме Клини о нормальной формеf (x1 , . . . , xk ) = U (µt[Tk (e, x1 , . . . , xk , t)]), где e — код программы для машины Шёнфилда, вычисляющей f .
Тогда получаем¡¢f (x) ↓= y ⇐⇒ ∃t Tk (e, x, t) & U (t) = y ⇐⇒ ∃tR(x, y, t),где R = {hx, y, ti | Tk (e, x, t) & U (t) = y}. Поскольку отношение R является вычислимым, то в силу пункта (2) теоремы 50 заключаем, что Γf — в.п.(⇐=) Пусть Γf — в.п. В соответствии с пунктом (2) теоремы 50 существует вычислимое отношение R ⊆ ω k+2 такое, что справедлива эквивалентность hx, yi ∈ Γf ⇐⇒∃zR(x, y, z).
Отсюда заключаем:x ∈ dom(f ) ⇐⇒ ∃yhx, yi ∈ Γf ⇐⇒ ∃y∃zR(x, y, z) ⇐⇒⇐⇒ ∃tR(x, (t)0 , (t)1 ) ⇐⇒ µt[R(x, (t)0 , (t)1 )] определено.³´Поэтому f (x) = µt[R(x, (t)0 , (t)1 )] является ч.в.ф.0В заключение параграфа мы определим нумерацию всех в.п. подмножеств ω, которая является аналогом клиниевской нумерации всех одноместных ч.в.ф. В частности, для данной нумерации справедливы собственные варианты s-m-n-теоремы,теоремы о неподвижной точке и теоремы Райса.80Глава IV. Теория вычислимостиОпределение. Для каждого n ∈ ω введем обозначение Wn = dom(æn ). Число nназывается в.п.-индексом множества Wn .
В силу пункта (3) следствия 51 заключаем,что отображение n 7→ Wn является нумерацией семейства всех в.п. подмножеств ω.Эта нумерация называется клиниевской нумерацией в.п. множеств.наОпределение. Пусть S – некоторое семейство подмножеств ω. Нумерация ν : ω −→S называется вычислимой, если множество {hx, yi|x ∈ ν(y)} вычислимо перечислимо.Предложение 59. Клиниевская нумерация в.п. множеств является вычислимой.наДоказательство. Пусть S0 — семейство всех в.п. подмножеств ω, ν0 : ω −→ S0 —клиниевская нумерация, т. е. ν0 (n) = Wn .
Тогда для любых x, y ∈ ω имеем:x ∈ ν0 (y) ⇐⇒ x ∈ Wy ⇐⇒ x ∈ dom(æy ) ⇐⇒⇐⇒ æy (x) ↓ ⇐⇒ U (µt[T1 (y, x, t)]) ↓ ⇐⇒ ∃tT1 (y, x, t).Отсюда в силу вычислимости T -предиката Клини и в силу пункта (2) теоремы 50заключаем, что {hx, yi | x ∈ ν0 (y)} вычислимо перечислимо.Следующее утверждение говорит о том, что клиниевская нумерация являетсянаибольшей среди всех вычислимых нумераций (относительно предпорядка сводимости нумераций).Предложение 60.
Любая вычислимая нумерация семейства подмножеств ω сводится к клиниевской.Доказательство. Пусть S — некоторое семейство подмножеств ω, ν : ω → S —вычислимая нумерация. Пусть далее S0 — семейство всех в.п. подмножеств ω, ν0 :ω → S0 — клиниевская нумерация.Так как ν вычислима, то существует вычислимое множество R ⊆ ω 3 такое, чтоимеет место свойство x ∈ ν(y) ⇐⇒ ∃zR(x, y, z). Тогда для любого фиксированногоn ∈ ω множество ν(n) = {x | ∃zR(x, n, z)} является вычислимо перечислимым и,значит, S ⊆ S0 .Определим двухместную частичную функцию(0,если x ∈ ν(y),g(x, y) =не определено иначе.Поскольку g(x, y) = o(µz[R(x, y, z)]), то g — ч.в.ф.
По s-m-n-теореме найдется вычислимая функция f (y) такая, что g(x, y) = æf (y) (x). Тогда для любых x, y ∈ ωполучаем:x ∈ ν(y) ⇐⇒ g(x, y) ↓ ⇐⇒ æf (y) (x) ↓ ⇐⇒⇐⇒ x ∈ dom(æf (y) ) ⇐⇒ x ∈ Wf (y) ⇐⇒ x ∈ ν0 (f (y)).Другими словами, ν = ν0 ◦ f , т. е. ν 6 ν0 . Что и требовалось доказать.§ 21. Универсальные функции§ 21.81Универсальные функцииНапомним, что (k+1)-местная частичная функция F (x0 , x1 , . . . , xk ) называется универсальной для некоторого семейства K, состоящего из k-местных частичных функций, если выполняеются следующие условия:1) для любого n ∈ ω существует f ∈ K такая, что F (n, x1 , .
. . , xk ) = f (x1 , . . . , xk );2) для любой f ∈ K найдется n ∈ ω такой, что F (n, x1 , . . . , xk ) = f (x1 , . . . , xk ).Мы уже убедились в том, что для семейства всех k-местных ч.р.ф. существуетуниверсальная (k+1)-местная функция, которая сама является ч.р.ф. Однако длясемейства всех k-местных п.р.ф. и для семейства всех k-местных р.ф. аналогичноесвойство не имеет места.Предложение 61.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
