1610906301-73dade1bb16d31c957842031de4c898c (Краткий конспект к экзамену), страница 7

По сути мыдоказали что для любого такого преобразователя найдется программа n, что есть программа h(n),вычисляющая ту же самую функцию (поэтому мы и использовали отображение каппа)Теорема 9.3 (Райса)Пусть X — непустой класс одноместных ч.р.ф, не совпадающий со всем классом одноместныхч.р.ф. Тогда отношение {x|ϰ_x ∈X} невычислимо или же «множество номеров функций,попадающих в класс Χ невычислимо» (любое нетривиальное свойство вычислимых функцийалгоритмически не распознается по их программам. Тривиальным свойством является свойство,которым либо обладают все, либо не обладает ни одна программа) (то есть если объединяетч.р.ф. с каким то свойством то не существует программы, способной это свойство определить).Доказательство:Предположим противное: пусть отношение вычислимо. Воспользовавшись тем, что Χ не пуствозьмем натуральные a,b: ϰ_a∈X, ϰ_b∉X. Возьмем f(x)= b, если ϰ_x∈X и a, если ϰ_x∉X,причем f(x) по нашему предположению вычислима.

По теореме о неподвижной точкесуществует натуральное n такое что ϰ_f(n)= ϰ_n. Проверим ϰ_n на принадлежность X.Пусть ϰ_n∈X. Тогда заметим что ϰ_n=ϰ_f(n)=ϰ_b∉X. Противоречие.Тогда пусть ϰ_n∉X. Но ϰ_n= ϰ_f(n)= ϰ_a∈X. Противоречие.Таким образом получили противоречие с нашим предположением.Тема 10:Вычислимо-перечислимые множестваОпределение 10.1Множество A⊊N называется вычислимо перечислимым, если А — пустое множество, либосуществует о.р.ф f: range(f)=A.Предложение 10.1А — вычислимо → A — вычислимо-перечислимо.Доказательство:Если А — пустое множество то оно вычислимо. Пусть А — непустое.

Зафиксируем a∈A.Введем функцию f(x)=x, если x∈A и a в противном случае. Нетрудно заметить что функциявычислима и при этом range(f)=A, что и требовалось.Теорема 10.1 (Поста)А — вычислимо <=> А и А` - вычислимо-перечислимо. (А`=N\A)Доказательство:=>По ранее доказанному если А вычислимо то оно вычислимо-перечислимо, но заметим что N\A втаком случае также вычислимо (например функцией f(x)=0, x∈A и 1 в противном случае).<=Пусть А и A` вычислимо перечислимы.Тогда Если А — пустое множество и А` =Ν то А — вычислимо.Пусть А непустое, тогда по определению в.п. множеств существуют о.р.ф g+, g-: А=range(g+),A`=range(g-). Заметим также что h(x)=μt(x=g+(t) v x=g-(t)) — о.р.ф.

Но тогда заметим что x∈A<=> g+(h(x))=x => A — вычислимо.Предложение 10.2Следующие условия эквивалентны:1)А — вычислимо перечислимое множество2)Существует вычислимое отношение R(x,t): x∈A <=> ∃ t R(x,t)Доказательство:=>Пусть А — пустое, тогда R — также пусто (для любых x,t ¬R(x,t)) и оно, очевидно вычислимо.Тогда пусть А не пустое → Существует о.р.ф f: A=range(f).

Тогда x∈A <=> x∈range(f) <=> ∃t(x=f(t)) (вычислимо по определению вычислимо перечислимых множеств).<=x∈A <=> ∃ t R(x,t). Если А — пустое, то А — вычислимо перечислимо. Иначле зафиксируемa∈A. Определим y=<x,t> и определим f(y)=(y)0, если R((y)0,(y)1) и a в остальных случаях).Нетрудно заметить, что range(f)⊊A. Покажем обратное включение: x∈A <=> ∃ t R(x,t) <=> ∃ y=<x,t>, x=(y)0, t=(y)1, причем они оба удовлетворяют отношению R. Но тогда f(y)=x и какследствие x∈range(f) и A⊊range(f).Определение 10.2Если f: N → N то Г(f)={<x,y>|y=f(x)} называется графиком f.Теорема 10.2 (О графике)Пусть f: N → N частичная функция.

Тогда f — ч.р.ф <=> Г(f) — вычислимо-перечислимоемножество.Доказательство:=>Пусть f — ч.р.ф. → существует a∈N: f(x)=U(μ t(T(a,<x>,t))) (существует мини-машина сномером a, которая эту функцию вычисляет).Тогда имеем что если z∈Г(f) <=> (seq(z)^(lh(z)=2))^(∃ t(T(a,<(z)0>,t))^ (∀t`<t)(¬T(a,<(z)0>,t`)^((z)1=U(t)) (z является последовательностью длины 2 существует вычисление скодом t, при которой выполняется отношение T, причем для вычисления с меньшим кодом t` ононе выполняется и при этом (z)1 является результатом выполнения вычисления с кодом t.Нетрудно заметить что это отношение является конкатенацией вычислимых отношений и какследствие само вычислимо и (по предложению 10.1) вычислимо-перечислимо.<=Пусть Г(f) — в.п.

Неформально можно описать так: взяв x перечисляем множествоГ(f)={z1,z2…} пока не получим zi={x,y} и сразу выдаем y в качестве ответа.Докажем формально: Если Г(f) — пустое множество, то f(x) — пустое множество и какследствие вычислимо.Иначе если Г не пусто то существует о.р.ф g: Г(f)=range(g) рассмотрим ч.р.ф h(x)=μ t((g(t))0=x)(функция, находящая значение при котором g(t)=zi будет содержать x.). Тогда возьмемf(x)=(g(h(x)))1 — ч.р.ф, что и требовалось.Можно также заметить что мы можем определять вычислимость или в.

перечислимость черездруг друга, если знаем одно из этих определений (Поскольку мы установили связь междувычислимостью и в.перечислимостью множеств (Теорема 10.1) и функций и множеств,показывающих их «график» (Теорема 10.2)Предложение 10.3K={x|{x}(x)↓} вычислимо-перечислимое.Доказательство: x∈K <=> {x}(x)↓ <=> U(μ t T(x,<x>,t))↓ <=> ∃ t T(x, <x>, t) но отношение Tвычислимо, то есть K — в.п.Получаем что K не вычислимо, но вычислимо перечислимо (из этого получаем что N\K — нев.п., иначе по Теореме Поста K вычислимо).Предложение 10.4Класс в.п.

множеств не замкнут относительно дополнений, но замкнут относительно ⋂ и ∪.Доказательство:Первое утверждение (о незамкнутости) мы получили из предыдущего предложения (K — в.п.,но его дополнение — нет) . Докажем второе утверждение:Пусть A,B — в.п. множестваx∈A <=>∃ t R0(x,t)x∈B <=>∃ t R1(x,t), где R0, R1 — вычислимые отношения.Тогда x∈A∪B <=> ∃ t R0(x,t) v ∃ t R1(x,t) <=> ∃ t (R0(x,t) v R1(x,t)) , но R0 и R1 вычислимы, азначит их объединение тоже вычислимо.Теперь докажем для ⋂, стоит однако заметить, что похожий трюк с выносом кванторасуществования может не сработать, то есть ∃ t P ^ ∃ t Q ≠ ∃ t (P^Q) (например P: t=1, Q: t=0,очевидно что ∃ t P ^ ∃ t Q истинно в то время как ∃ t P^Q ложно.) Тогда возьмем t=<t0,t1> изапишем x∈A⋂ B <=>∃ t (R0(x,(t)0) v R1(x,(t)1))Предложение 10.5Пусть А — в.п. множество и a∈N.

Тогда А ∪ {a} и A\{a} — в.п. множества (можно добавить иотнять конечное число элементов из в.п.м и оно останется в.п.м.)Доказательство: Т.к. {a} вычислимо (f(x)=a) то оно в.п. и по доказанному ранее А ∪ {a} —в.п.м. Также поскольку А в.п. существует вычислимое отношение R(x,t): x∈A <=> ∃ t R(x,t), нотогда A\{a} выражается как x∈A ^ x≠a <=> ∃ t (R(x,t)) ^ (x≠a), так как отношение вычислимо, томножество в.п..