Основы теории вычислимых функций

Нумерации и операции

Разбить на страницы
Показывать лекцию целиком

Главные универсальные функции

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

Однако мы хотим говорить не о программах (чтобы не вдаваться в детали языка программирования), а о номерах функций. Для этого у нас есть средства. Именно, всякая универсальная функция U для класса вычислимых функций одного аргумента задает нумерацию этого класса: число n является номером функции $$U_n\colon x\hm\mapsto U(n,x)$$.

Вообще нумерацией (более точно, натуральной нумерацией ) произвольного множества F называют всюду определенное отображение u : N -> F, область значений которого есть все множество F. Если v(n) = f, то число n называют номером объекта f. Таким образом, всякая функция двух аргументов задает нумерацию некоторого класса функций одного аргумента (и является универсальной для этого класса).

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

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

Пусть U двуместная вычислимая универсальная функция для класса одноместных вычислимых функций (термин " k -местная функция" означает " функция k аргументов"). Ее называют главной универсальной функцией, если для любой двуместной вычислимой функции V существует всюду определенная вычислимая функция s(m), для которой

V(m,x) = U(s(m),x)

при всех m и x (равенство понимается, как обычно, в том смысле, что либо оба значения не определены, либо определены и равны).

Другими словами, Vm = Us(m), то есть функция s дает по V -номеру некоторой функции некоторый U -номер той же функции.

Теорема 15. Существует главная универсальная функция.

(Первый способ.) Покажем, что описанное в доказательстве теоремы 6 построение универсальной функции дает главную универсальную функцию. Напомним, что мы перечисляли все программы p0,p1,p2, ... какого-то естественного языка программирования в порядке возрастания их длин и полагали U(n,x) равным результату применения программы pn к входу x. Пусть теперь есть какая-то другая вычислимая функция V двух аргументов. Нам надо по любому натуральному m получить программу функции Vm, то есть функции, которая получится, если в V зафиксировать первый аргумент равным m. Ясно, что такую программу (в большинстве языков программирования) получить легко надо только в программе для V заменить первый аргумент на определение константы (или использовать программу для V в качестве подпрограммы, а в основной программе вызывать V с фиксированным первым аргументом).

(Второй способ.) Но можно и не вдаваться в детали построения универсальной функции, а воспользоваться лишь фактом ее существования.

Заметим сначала, что существует вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов, то есть такая функция T, что при фиксации первого аргумента среди функций Tn(u,v) = T(n,u,v) встречаются все вычислимые функции двух аргументов.

Такую функцию можно построить так. Фиксируем некоторую вычислимую нумерацию пар, то есть вычислимое взаимно однозначное соответствие $$\langle u,v\rangle \hm\leftrightarrow [u,v]$$ между N x N и N ; число [u,v], соответствующее паре $$\langle u,v\rangle$$, мы будем называть номером этой пары. Если теперь R двуместная вычислимая универсальная функция для вычислимых одноместных функций, то вычислимая функция T, определенная формулой T(n,u,v) = R(n,[u,v]), будет универсальной для вычислимых двуместных функций. В самом деле, пусть F произвольная вычислимая функция двух аргументов. Рассмотрим вычислимую одноместную функцию f, определенную соотношением f([u,v]) = F(u,v). Поскольку R универсальна, найдется число n, для которого R(n,x) = f(x) при всех x. Для этого n выполнены равенства T(n,u,v) = R(n,[u,v]) = f([u,v]) = F(u,v), и потому n -ое сечение функции T совпадает с F. Итак, универсальная функция трех аргументов построена.

Теперь используем ее для определения главной универсальной функции U двух аргументов. Неформально говоря, мы встроим внутрь U все другие вычислимые функции двух аргументов, и тем самым U станет главной. Формально говоря, положим U([n,u],v) = T(n,u,v) и проверим, что функция U будет главной. Любая вычислимая функция V двух аргументов встречается среди сечений функции T: можно найти такое n, что V(u,v) = T(n,u,v) для всех u и v. Тогда V(u,v) = U([n,u],v) для всех u и v и потому функция s, определенная формулой s(u) = [n,u], удовлетворяет требованиям из определения главной универсальной функции.

Нумерации, соответствующие главным универсальным функциям, называют главными, или геделевыми.

Теперь уже можно доказать точный вариант утверждения, с которого мы начали.

Теорема 16. Пусть U двуместная главная универсальная функция для класса вычислимых функций одного аргумента. Тогда существует всюду определенная функция c, которая по номерам p и q двух функций одного аргумента дает номер c(p,q) их композиции: Uc(p,q) есть композиция $$U_p \hm\circ U_q$$, то есть

U(c(p,q),x) = U(p, U(q,x))

для всех p, q и x.

Рассмотрим двуместную вычислимую функцию V, для которой V([p,q],x) = U(p,U(q,x)). По определению главной универсальной функции, найдется такая всюду определенная одноместная вычислимая функция s, что V(m,x) = U(s(m),x) для всех m и x. Тогда V([p,q],x) = U(s([p,q]),x) и потому функция c, определенная соотношением c(p,q) = s([p,q]), будет искомой.

Повторим это доказательство неформально. Определение главной универсальной функции требует, чтобы для любого другого языка программирования, для которого имеется вычислимый интерпретатор V, существовал бы вычислимый транслятор s программ этого языка в программы языка U. (Для краткости мы не различаем программы и их номера и рассматриваем число m как U -программу функции Um.)

Теперь рассмотрим новый способ программирования, при котором пара $$\langle p,q \rangle$$ объявляется программой композиции функций с U -программами p и q. По условию, такие программы можно алгоритмически транслировать в U -программы, что и требовалось доказать.

Любопытно, что верно и обратное к теореме 16 утверждение:

  28. Пусть U двуместная вычислимая универсальная функция для класса вычислимых функций одного аргумента. Если существует всюду определенная функция, которая по номерам p и q двух функций одного аргумента дает какой-либо номер их композиции, то функция U является главной. (Указание: покажите, что по k можно алгоритмически получать U -номер функции $$x\hm\mapsto [k,x]$$.)

Естественный вопрос: существуют ли вычислимые универсальные функции, не являющиеся главными? Мы увидим дальше, что существуют.

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

  30. Пусть U главная универсальная функция. Докажите, что для любой вычислимой функции V(m,n,x) существует такая всюду определенная вычислимая функция s(m,n), что V(m,n,x) = U(s(m,n),x) при всех m, n и x. (Указание: объединить m и n в пару.)

Вычислимые последовательности функций

Пусть дана некоторая последовательность f0,f1, ... вычислимых функций одного аргумента. Мы хотим придать смысл выражению " последовательность $$i\mapsto f_i$$ вычислима". Это можно сделать двумя способами:

  • можно называть эту последовательность вычислимой, если функция F двух аргументов, заданная формулой F(i,n) = fi(n), является вычислимой.
  • можно называть эту последовательность вычислимой, если существует вычислимая последовательность чисел c0,c1, ..., для которой ci является одним из номеров функции fi.
    •

    Второе определение (в отличие от первого) зависит от выбора нумерации.

    Теорема 17. Если нумерация является вычислимой (то есть соответствующая универсальная функция вычислима), то из второго определения следует первое. Если нумерация является к тому же главной, то из первого определения следует второе.

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

    Если U вычислимая универсальная функция, а последовательность $$i\hm\mapsto c_i$$ вычислима, то функция $$F\colon \langle i,x\rangle\hm\mapsto f_i(x)\hm=U(c_i,x)$$ вычислима как результат подстановки одной вычислимой функции в другую.

    Напротив, если функция F вычислима, а универсальная функция U является главной, то функция-транслятор, существующая по определению главной универсальной функции, как раз и дает по i один из номеров функции fi.

      31. Пусть фиксирована главная универсальная функция для класса вычислимых функций одного аргумента. Тогда возникает нумерация вычислимых действительных чисел в соответствии с определением: номером числа $$\alpha$$ является любой номер любой функции, которая по рациональному $$\varepsilon > 0$$ дает $$\varepsilon$$ -приближение к $$\alpha.$$

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

    Главные универсальные множества

    По аналогии с функциями, перечислимое множество $$W \subset N \times N$$ называется главным универсальным перечислимым множеством (для класса всех перечислимых подмножеств N ), если для любого другого перечислимого множества $$V \subset N \times N$$ найдется такая всюду определенная вычислимая функция s : N -> N, что

    $$\langle n,x\rangle \in V \Leftrightarrow \langle s(n),x\rangle \in W$$

    для всех n и x. (Очевидно, что из этого свойства следует универсальность.)

    Как и для функций, можно перейти к нумерациям. Каждое множество $$U \subset N \times N$$ задает нумерацию некоторого семейства подмножеств натурального ряда: число n является номером n -го сечения $$U_n=\{x\mid \langle n,x\rangle\in U\}$$. Перечислимое подмножество множества N x N задает нумерацию некоторого семейства перечислимых подмножеств натурального ряда; такие нумерации называют вычислимыми. Перечислимое множество $$W \subset N \times N$$ универсально, если и только если всякое перечислимое подмножество натурального ряда имеет W -номер; оно является главным тогда и только тогда, когда любая вычислимая нумерация V (любого семейства перечислимых множеств) вычислимо сводится к W -нумерации в том смысле, что Vn = Ws(n) для некоторой вычислимой функции s и для всех n.

    Теорема 18. Существует главное универсальное перечислимое множество $$W \subset N \times N$$.

    Эта теорема является очевидным следствием такого утверждения:

    Область определения главной универсальной функции для класса вычислимых функций одного аргумента является главным универсальным множеством для класса перечислимых подмножеств N.

    Доказательство леммы. Пусть U главная универсальная функция, а W область ее определения. Пусть $$V \subset N \times N$$ произвольное перечислимое множество. Рассмотрим вычислимую функцию G с областью определения V. Поскольку функция U является главной, найдется всюду определенная вычислимая функция s : N -> N, для которой Gn = Us(n) при всех n. Тогда равны и области определения функций Gn и Us(n), то есть Vn = Ws(n).

      32. Постройте главное универсальное множество непосредственно, используя универсальное подмножество N3 (по аналогии с выше приведенным построением главной универсальной функции).

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

    Теорема 19. Пусть $$W \subset N \times N$$ главное универсальное перечислимое множество. Тогда по W -номерам двух перечислимых множеств можно алгоритмически получить номер их пересечения: существует такая вычислимая всюду определенная функция двух аргументов s, что

    $$W_{s(m,n)} = W_{m} \cap W_{n}$$

    для любых двух m и n.

    Рассмотрим множество $$V \subset N \times N$$, определенное так:

    $$\langle [m,n], x\rangle \in V \Leftrightarrow x \in (W_m \cap W_n)$$

    (здесь квадратные скобки обозначают номер пары) и применим к нему определение главного универсального множества.

    Как и для функций, понятие вычислимости последовательности перечислимых множеств может быть определено двояко: можно считать вычислимой последовательность V0,V1, ... сечений произвольного перечислимого множества V, а можно требовать, чтобы по i можно было алгоритмически указать один из номеров i -го члена последовательности в главной нумерации. Эти определения равносильны (доказательство полностью аналогично рассуждению для функций).

    Страницы:

    Главные универсальные функции

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

    Однако мы хотим говорить не о программах (чтобы не вдаваться в детали языка программирования), а о номерах функций. Для этого у нас есть средства. Именно, всякая универсальная функция U для класса вычислимых функций одного аргумента задает нумерацию этого класса: число n является номером функции $$U_n\colon x\hm\mapsto U(n,x)$$.

    Вообще нумерацией (более точно, натуральной нумерацией ) произвольного множества F называют всюду определенное отображение u : N -> F, область значений которого есть все множество F. Если v(n) = f, то число n называют номером объекта f. Таким образом, всякая функция двух аргументов задает нумерацию некоторого класса функций одного аргумента (и является универсальной для этого класса).

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

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

    Пусть U двуместная вычислимая универсальная функция для класса одноместных вычислимых функций (термин " k -местная функция" означает " функция k аргументов"). Ее называют главной универсальной функцией, если для любой двуместной вычислимой функции V существует всюду определенная вычислимая функция s(m), для которой

    V(m,x) = U(s(m),x)

    при всех m и x (равенство понимается, как обычно, в том смысле, что либо оба значения не определены, либо определены и равны).

    Другими словами, Vm = Us(m), то есть функция s дает по V -номеру некоторой функции некоторый U -номер той же функции.

    Теорема 15. Существует главная универсальная функция.

    (Первый способ.) Покажем, что описанное в доказательстве теоремы 6 построение универсальной функции дает главную универсальную функцию. Напомним, что мы перечисляли все программы p0,p1,p2, ... какого-то естественного языка программирования в порядке возрастания их длин и полагали U(n,x) равным результату применения программы pn к входу x. Пусть теперь есть какая-то другая вычислимая функция V двух аргументов. Нам надо по любому натуральному m получить программу функции Vm, то есть функции, которая получится, если в V зафиксировать первый аргумент равным m. Ясно, что такую программу (в большинстве языков программирования) получить легко надо только в программе для V заменить первый аргумент на определение константы (или использовать программу для V в качестве подпрограммы, а в основной программе вызывать V с фиксированным первым аргументом).

    (Второй способ.) Но можно и не вдаваться в детали построения универсальной функции, а воспользоваться лишь фактом ее существования.

    Заметим сначала, что существует вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов, то есть такая функция T, что при фиксации первого аргумента среди функций Tn(u,v) = T(n,u,v) встречаются все вычислимые функции двух аргументов.

    Такую функцию можно построить так. Фиксируем некоторую вычислимую нумерацию пар, то есть вычислимое взаимно однозначное соответствие $$\langle u,v\rangle \hm\leftrightarrow [u,v]$$ между N x N и N ; число [u,v], соответствующее паре $$\langle u,v\rangle$$, мы будем называть номером этой пары. Если теперь R двуместная вычислимая универсальная функция для вычислимых одноместных функций, то вычислимая функция T, определенная формулой T(n,u,v) = R(n,[u,v]), будет универсальной для вычислимых двуместных функций. В самом деле, пусть F произвольная вычислимая функция двух аргументов. Рассмотрим вычислимую одноместную функцию f, определенную соотношением f([u,v]) = F(u,v). Поскольку R универсальна, найдется число n, для которого R(n,x) = f(x) при всех x. Для этого n выполнены равенства T(n,u,v) = R(n,[u,v]) = f([u,v]) = F(u,v), и потому n -ое сечение функции T совпадает с F. Итак, универсальная функция трех аргументов построена.

    Теперь используем ее для определения главной универсальной функции U двух аргументов. Неформально говоря, мы встроим внутрь U все другие вычислимые функции двух аргументов, и тем самым U станет главной. Формально говоря, положим U([n,u],v) = T(n,u,v) и проверим, что функция U будет главной. Любая вычислимая функция V двух аргументов встречается среди сечений функции T: можно найти такое n, что V(u,v) = T(n,u,v) для всех u и v. Тогда V(u,v) = U([n,u],v) для всех u и v и потому функция s, определенная формулой s(u) = [n,u], удовлетворяет требованиям из определения главной универсальной функции.

    Нумерации, соответствующие главным универсальным функциям, называют главными, или геделевыми.

    Теперь уже можно доказать точный вариант утверждения, с которого мы начали.

    Теорема 16. Пусть U двуместная главная универсальная функция для класса вычислимых функций одного аргумента. Тогда существует всюду определенная функция c, которая по номерам p и q двух функций одного аргумента дает номер c(p,q) их композиции: Uc(p,q) есть композиция $$U_p \hm\circ U_q$$, то есть

    U(c(p,q),x) = U(p, U(q,x))

    для всех p, q и x.

    Рассмотрим двуместную вычислимую функцию V, для которой V([p,q],x) = U(p,U(q,x)). По определению главной универсальной функции, найдется такая всюду определенная одноместная вычислимая функция s, что V(m,x) = U(s(m),x) для всех m и x. Тогда V([p,q],x) = U(s([p,q]),x) и потому функция c, определенная соотношением c(p,q) = s([p,q]), будет искомой.

    Повторим это доказательство неформально. Определение главной универсальной функции требует, чтобы для любого другого языка программирования, для которого имеется вычислимый интерпретатор V, существовал бы вычислимый транслятор s программ этого языка в программы языка U. (Для краткости мы не различаем программы и их номера и рассматриваем число m как U -программу функции Um.)

    Теперь рассмотрим новый способ программирования, при котором пара $$\langle p,q \rangle$$ объявляется программой композиции функций с U -программами p и q. По условию, такие программы можно алгоритмически транслировать в U -программы, что и требовалось доказать.

    Любопытно, что верно и обратное к теореме 16 утверждение:

      28. Пусть U двуместная вычислимая универсальная функция для класса вычислимых функций одного аргумента. Если существует всюду определенная функция, которая по номерам p и q двух функций одного аргумента дает какой-либо номер их композиции, то функция U является главной. (Указание: покажите, что по k можно алгоритмически получать U -номер функции $$x\hm\mapsto [k,x]$$.)

    Естественный вопрос: существуют ли вычислимые универсальные функции, не являющиеся главными? Мы увидим дальше, что существуют.

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

      30. Пусть U главная универсальная функция. Докажите, что для любой вычислимой функции V(m,n,x) существует такая всюду определенная вычислимая функция s(m,n), что V(m,n,x) = U(s(m,n),x) при всех m, n и x. (Указание: объединить m и n в пару.)

    Вычислимые последовательности функций

    Пусть дана некоторая последовательность f0,f1, ... вычислимых функций одного аргумента. Мы хотим придать смысл выражению " последовательность $$i\mapsto f_i$$ вычислима". Это можно сделать двумя способами:

  • можно называть эту последовательность вычислимой, если функция F двух аргументов, заданная формулой F(i,n) = fi(n), является вычислимой.
  • можно называть эту последовательность вычислимой, если существует вычислимая последовательность чисел c0,c1, ..., для которой ci является одним из номеров функции fi.
    •

    Второе определение (в отличие от первого) зависит от выбора нумерации.

    Теорема 17. Если нумерация является вычислимой (то есть соответствующая универсальная функция вычислима), то из второго определения следует первое. Если нумерация является к тому же главной, то из первого определения следует второе.

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

    Если U вычислимая универсальная функция, а последовательность $$i\hm\mapsto c_i$$ вычислима, то функция $$F\colon \langle i,x\rangle\hm\mapsto f_i(x)\hm=U(c_i,x)$$ вычислима как результат подстановки одной вычислимой функции в другую.

    Напротив, если функция F вычислима, а универсальная функция U является главной, то функция-транслятор, существующая по определению главной универсальной функции, как раз и дает по i один из номеров функции fi.

      31. Пусть фиксирована главная универсальная функция для класса вычислимых функций одного аргумента. Тогда возникает нумерация вычислимых действительных чисел в соответствии с определением: номером числа $$\alpha$$ является любой номер любой функции, которая по рациональному $$\varepsilon > 0$$ дает $$\varepsilon$$ -приближение к $$\alpha.$$

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

    Главные универсальные множества

    По аналогии с функциями, перечислимое множество $$W \subset N \times N$$ называется главным универсальным перечислимым множеством (для класса всех перечислимых подмножеств N ), если для любого другого перечислимого множества $$V \subset N \times N$$ найдется такая всюду определенная вычислимая функция s : N -> N, что

    $$\langle n,x\rangle \in V \Leftrightarrow \langle s(n),x\rangle \in W$$

    для всех n и x. (Очевидно, что из этого свойства следует универсальность.)

    Как и для функций, можно перейти к нумерациям. Каждое множество $$U \subset N \times N$$ задает нумерацию некоторого семейства подмножеств натурального ряда: число n является номером n -го сечения $$U_n=\{x\mid \langle n,x\rangle\in U\}$$. Перечислимое подмножество множества N x N задает нумерацию некоторого семейства перечислимых подмножеств натурального ряда; такие нумерации называют вычислимыми. Перечислимое множество $$W \subset N \times N$$ универсально, если и только если всякое перечислимое подмножество натурального ряда имеет W -номер; оно является главным тогда и только тогда, когда любая вычислимая нумерация V (любого семейства перечислимых множеств) вычислимо сводится к W -нумерации в том смысле, что Vn = Ws(n) для некоторой вычислимой функции s и для всех n.

    Теорема 18. Существует главное универсальное перечислимое множество $$W \subset N \times N$$.

    Эта теорема является очевидным следствием такого утверждения:

    Область определения главной универсальной функции для класса вычислимых функций одного аргумента является главным универсальным множеством для класса перечислимых подмножеств N.

    Доказательство леммы. Пусть U главная универсальная функция, а W область ее определения. Пусть $$V \subset N \times N$$ произвольное перечислимое множество. Рассмотрим вычислимую функцию G с областью определения V. Поскольку функция U является главной, найдется всюду определенная вычислимая функция s : N -> N, для которой Gn = Us(n) при всех n. Тогда равны и области определения функций Gn и Us(n), то есть Vn = Ws(n).

      32. Постройте главное универсальное множество непосредственно, используя универсальное подмножество N3 (по аналогии с выше приведенным построением главной универсальной функции).

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

    Теорема 19. Пусть $$W \subset N \times N$$ главное универсальное перечислимое множество. Тогда по W -номерам двух перечислимых множеств можно алгоритмически получить номер их пересечения: существует такая вычислимая всюду определенная функция двух аргументов s, что

    $$W_{s(m,n)} = W_{m} \cap W_{n}$$

    для любых двух m и n.

    Рассмотрим множество $$V \subset N \times N$$, определенное так:

    $$\langle [m,n], x\rangle \in V \Leftrightarrow x \in (W_m \cap W_n)$$

    (здесь квадратные скобки обозначают номер пары) и применим к нему определение главного универсального множества.

    Как и для функций, понятие вычислимости последовательности перечислимых множеств может быть определено двояко: можно считать вычислимой последовательность V0,V1, ... сечений произвольного перечислимого множества V, а можно требовать, чтобы по i можно было алгоритмически указать один из номеров i -го члена последовательности в главной нумерации. Эти определения равносильны (доказательство полностью аналогично рассуждению для функций).

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^