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

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

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

Следовательно, характеристическую функцию множества A = {n ∈ω | γ(n) — одноэлементное} можно записать в виде XA (n) = sg(|n − 2ex(0,n) |), т. е. Aвычислимо.Заметим, что любое подмножество S0 ⊆ ω можно рассматривать как алгоритмическую проблему относительно тождественной нумерации ν(x) = x. В этом случаеразрешимость проблемы S0 эквивалентна вычислимости множества S0 . В следующейважной теореме мы как раз рассматриваем проблему на множестве ω относительнотождественной нумерации.Напомним, что для частичной функции f запись f (x) ↓ означает, что значениеf (x) определено, а запись f (x) ↑ означает, что f (x) не определено.Теорема 47.

Множество K = {x ∈ ω | æx (x) ↓} невычислимо.Доказательство. Допустим, напротив, множество K вычислимо. Следовательно,XK (x) вычислима. Рассмотрим одноместую функцию(0,если æx (x) ↑f (x) =не определено, если æx (x) ↓Так как f (x) = µy[XK (x) = 0 & y = 0], то f (x) частично вычислима. По теореме обуниверсальной ч.р.ф.

существует клиниевский номер n ∈ ω такой, что f (x) = æn (x).Рассмотрим значение аргумента x = n, получим следующую цепочку эквивалентныхусловий:æn (n) ↓ ⇐⇒ f (n) ↓ ⇐⇒ æn (n) ↑ .Противоречие.Пусть S — множество всех 1-местных ч.в.ф. Определим нумерацию ν : ω → S ×ω,положив ν(n) = hæ(n)0 , (n)1 i для каждого n ∈ ω. Проблемой остановки мы будем называть множество {hf, xi ∈ S × ω | f (x) ↓}. Нетрудно понять, что разрешимостьпроблемы остановки относительно введенной нумерации ν равносильна вычислимости множества {hx, yi ∈ ω 2 | æx (y) ↓}.Следствие 48 (о неразрешимости проблемы остановки). Множество {hx, yi ∈ ω 2 |æx (y) ↓} невычислимо.Доказательство.

Допустим A = {hx, yi | æx (y) ↓} вычислимо. Тогда XA (x, y) вычислима. Следовательно, функция f (x) = XA (x, x) тоже вычислима. Заметим, чтоf (x) = 1 ⇐⇒ XA (x, x) = 1 ⇐⇒ hx, xi ∈ A ⇐⇒ æx (x) ↓ ⇐⇒ x ∈ K. Такимобразом, функция XK (x) = f (x) вычислима, что противоречит теореме 47.74Глава IV. Теория вычислимостиЗамечание. Заметим, что T -предикат Клини T1 (e, x, y) ложен, если e не являетсякодом программы.

Поэтому из условия æe (x) ↓ вытекает, что e должен быть кодомпрограммы для машины Шёнфилда. Отсюда следует, что множество из формулировки следствия 48 совпадает с множеством{he, xi | e — код программы для машины Шёнфилда,которая останавливается на входе x},а утверждение следствия 48 означает, что не существует алгоритма, который по заданному коду программы и входным данным определяет, останавливается ли даннаяпрограмма на заданном входе или нет.В различных разделах математики очень часто одну задачу сводят к другой задаче так, что если удается решить вторую задачу, то полученное решение некоторымэффективным образом трансформируется в решение первой задачи.В терминах теории нумераций сводимость одной нумерации ν0 к другой нумерации ν означает, что нумерацию ν можно эффективно преобразовать в нумерацию ν0так, что из разрешимости любой проблемы в нумерации ν будет следовать разрешимость этой же проблемы в нумерации ν0 .Формальное определение сводимости нумераций выглядит следующим образом.нанаОпределение.

Пусть заданы две нумерации ν0 : ω −→ S0 и ν : ω −→ S, где S0 ⊆ S.Говорят, что ν0 сводится к ν, и пишут ν0 6 ν, если существует вычислимая функцияf (x) такая, что ν0 (x) = ν(f (x)) для каждого x ∈ ω. Другими словами, коммутативнаследующая диаграммаidS0 −−−→ Sxxνν0 ω −−−→ ωfГоворят, что нумерации ν0 и ν эквивалентны, и пишут ν0 ≡ ν, если ν0 6 ν и ν 6 ν0 .(В частности, если ν0 ≡ ν, то S0 = S.)Теорема 49 (о разрешимых нумерациях бесконечных множеств). Любая разрешимая нумерация бесконечного множества эквивалентна некоторой однозначной нумерации.наДоказательство. Пусть ν : ω −→ S — разрешимая нумерация бесконечного множества S. Следовательно, нумерационная эквивалентность A = {hx, yi | ν(x) = ν(y)}вычислима, т.

е. функция XA (x, y) вычислима.Определим функцию f по следующей схеме (см. рисунок):(f (0) = 0,f (n + 1) = µx[ν(x) 6= νf (0) & . . . & ν(x) 6= νf (n)].В силу бесконечности S функция f всюду определена. Запишем схему более формально:f (0) = 0,nPf (n + 1) = µx[ XA (x, f (i)) = 0].i=0Поэтому из вычислимости функции XA следует, что f тоже вычислима. (Упражнение: доказать, что введенная схема сводится к схеме примитивной рекурсии.)§ 20. Вычислимо перечислимые множестваf (0)qω 0rf (1)q2r3r´¡4rf (2)q5r345756 ··· ©r¢©´¢´¡¢©©©´¢¡¢©ν´¢ ´¡ ©© ¢´¡©©¢¶¢´³??ª©¡¢®+́¢®©¼ttt···Sµ´µ¡6¢̧¢¡ν0 ¡ν0 ¢ν0¡¢¡¢¡r¢rrrrrω r01r¢126 ···Определим нумерацию ν0 (n) = νf (n).

Ясно, что range(ν0 ) ⊆ S. По построениюдля любого n ∈ ω выполняются условия ν0 (n + 1) 6= ν0 (0), . . . , ν0 (n + 1) 6= ν0 (n),следовательно, ν0 однозначна. Кроме этого, очевидно, что ν0 6 ν.Докажем, что S ⊆ range(ν0 ). Для этого индукцией по n покажем, что имеет местовключение {ν(0), . . .

, ν(n)} ⊆ {ν0 (0), . . . , ν0 (n)}. При n = 0 по построению ν0 (0) =ν(f (0)) = ν(0).Пусть включение {ν(0), . . . , ν(n)} ⊆ {ν0 (0), . . . , ν0 (n)} уже доказано. Рассмотримэлемент s = ν(n + 1). Если s ∈ {ν0 (0), . . . , ν0 (n)} ⊆ {ν0 (0), . . . , ν0 (n), ν0 (n + 1)}, тодоказывать нечего. Если же s ∈/ {ν0 (0), . . .

, ν0 (n)}, то ν(n + 1) 6= νf (0), . . . , ν(n + 1) 6=νf (n) и по индукционному предположению n+1 является наименьшим натуральнымчислом с таким условием. Следовательно, по определению функции f заключаем, чтоf (n+1) = n+1, а значит, ν(n+1) = ν0 (n+1) и {ν(0), . . . , ν(n+1)} ⊆ {ν0 (0), .

. . , ν0 (n+1)}. Что и требовалось доказать.Итак, {ν(0), . . . , ν(n)} ⊆ {ν0 (0), . . . , ν0 (n)} для всех n∈ω. А поскольку range(ν)=S,то отсюда следует, что S ⊆ range(ν0 ). Таким образом, S = range(ν0 ).Докажем, наконец, что ν 6 ν0 . Определим вычислимую функциюg(x) = µn[ν(f (n)) = ν(x)] = µn[XA (f (n), x) = 1].Пусть x ∈ ω.

Тогда найдется минимальный n такой, что ν(x) = ν0 (n). Но ν0 (n) =ν(f (n)), следовательно, g(x) = n. Отсюда заключаем, что ν(x) = ν0 (g(x)). Такимобразом, ν 6 ν0 .§ 20.Вычислимо перечислимые множестваВ этом параграфе мы введем понятие вычислимо перечислимого множества (сокращенно в.п. множества) и изучим некоторые свойства таких множеств. С интуитивной точки зрения множество является вычислимо перечислимым, если существуеталгоритм эффективного перечисления всех его элементов. При этом мы допускаем,что это перечисление может иметь повторения и не обязано быть перечислением вкаком-то строго определенном порядке.Определение.

Пусть k > 1. Множество A ⊆ ω k называется вычислимо перечислимым (в.п.), если A = ∅ или A = {hf1 (x), . . . , fk (x)i | x ∈ ω} для некоторыхвычислимых функций f1 (x), . . . , fk (x).76Глава IV. Теория вычислимостиДругими словами, вычислимые функции f1 , . . . , fk покоординатно перечисляютмножество A. В случае k = 1 определение выглядит проще: множество A ⊆ ω является в.п. тогда и только тогда, когда A = ∅ или A = range(f ) для некоторой вычислимой функции f (x).

Введенное определение является формальным описанием интуитивного понятия перечислимости. Однако существует несколько эквивалентныхописаний в.п. множеств, каждое из которых оказывается полезным при изучении техили иных свойств в.п. множеств.Теорема 50 (об эквивалентных определениях в.п. множеств).Для произвольного множества A ⊆ ω k следующие условия эквивалентны:1) A вычислимо перечислимо.2) Существует вычислимое отношение R ⊆ ω k+1 такое, чтоhx1 , .

. . , xk i ∈ A ⇐⇒ ∃yR(x1 , . . . , xk , y).3) Существует частично вычислимая функция f (x1 , . . . , xk ) такая, что A =dom(f ).Доказательство. (1) ⇒ (2) Если A = ∅, то вычислимое множество R = ∅ очевидноудовлетворяет условию (2). Если же A 6= ∅ и A = {hf1 (x), . . . , fk (x)i | x ∈ ω}, гдеf1 , . . . , fk — вычислимые функции, то имеет место эквивалентность¡¢hx1 , . .

. , xk i ∈ A ⇐⇒ ∃y f1 (y) = x1 & . . . & fk (y) = xk .Тогда множество R = {hx1 , . . . , xk , yi | f1 (y) = x1 & . . . & fk (y) = xk } является искомым (k+1)-местным вычислимым отношением.(2) ⇒ (3) Пусть R ⊆ ω k+1 — вычислимое отношение такое, что A является егопроекцией (см. рисунок), т. е. имеет место эквивалентность x ∈ A ⇐⇒ ∃yR(x, y).y6'$R"&fA!%-xОпределим частичную k-местную функцию f (x) = µy[R(x, y)]. Так как R вычислимо, то f (x) — ч.в.ф. Кроме этого, имеет местоf (x) ↓ ⇐⇒ ∃yR(x, y) ⇐⇒ x ∈ A.Другими словами, dom(f ) = A.(3) ⇒ (1) Если A = ∅, то доказывать нечего.

Пусть A 6= ∅. Следовательно, найдется кортеж a = ha1 , . . . , ak i ∈ A. По условию A = dom(f ), где f — ч.в.ф. Тогдаf вычислима на некоторой машине Шёнфилда с кодом e. По теореме Клини о нормальной форме f (x) = U (µy[Tk (e, x, y)]), где U и Tk — вычислимые. Для каждогоi ∈ {1, . . . , k} определим вычислимую функцию((n)i , если Tk (e, (n)1 , . .

. , (n)k , (n)0 ),fi (n) =ai ,если ¬Tk (e, (n)1 , . . . , (n)k , (n)0 ).§ 20. Вычислимо перечислимые множества77Покажем, что набор функций f1 , . . . , fk — искомый, т. е. A = {hf1 (x), . . . , fk (x)i |x ∈ ω}. Для этого докажем сначала включение A ⊆ {hf1 (x), . . . , fk (x)i | x ∈ ω}.Пусть x = hx1 , . . . , xk i ∈ A. Тогда f (x) = U (µy[Tk (e, x, y)]) определено. Следовательно, значение µy[Tk (e, x, y)] определено. Следовательно, существует y ∈ ω такой,что Tk (e, x, y) истинно.

Положим n =< y, x1 , . . . , xk >. Тогда Tk (e, (n)1 , . . . , (n)k , (n)0 )истинно и, значит, fi (n) = (n)i = xi для всех i ∈ {1, . . . , k}. Таким образом, x ∈{hf1 (x), . . . , fk (x)i | x ∈ ω}.Докажем теперь включение {hf1 (x), . . . , fk (x)i | x ∈ ω} ⊆ A. Рассмотрим произвольный набор hf1 (n), . .

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

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