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

Пусть f(x)=ψ(x,x)+1. По условию существует такое m,что f(x)=ψ(x,x)+1=ψ(m,x). Из этого получаем, что, ввиду того, что f(x) всюду определена имеемчто f(m)=ψ(m,m)+1=ψ(m,m). Получаем противоречие, так как выходит что k=k+1.Определение 7.8Обозначим {m}(x1...xn)~ A^n_p(x1...xn), если m — номер программы, иначе будем считать {m}(x1...xn) неопределенным.

Заметим тогда что {m}(x1...xn)~U(μy(T(m,(x1...xn),y))Теорема 7.4 (О параметризации)Для любой ч.р.ф f(y1...ym,x1...xn) существует о.р.ф s(y`) такая что f(y1...ym,x1...xn)~{s(y1...ym)}(x1...xn)Доказательство:Рассмотрим f`(x`,y`)=f(y`,x`) (введем такую функцию)Пусть P — программа, вычисляющая f`. Преобразуем P следующим образом: Запишем вR(n+1)=y1,… R(n+m):=ym и заменим все операторы вида goto g на goto g+n и if ...=0 goto d наif...=0 goto d+n.Назовем получившуюся программу P*. Код P*<<0,n+1,y1>,<0,n+2,y2>...<0,n+m,ym>...> и после этого пойдет код P. Нетрудно заметить что P*и есть {s(y1...ym)}(x1...xn)Тема 8:Машины ТьюрингаМащины Тьюринга являются одной из самых первых и популярных формализацией понятиявычислимости.Определение 8.1Машина Тьюринга состоит из:• Конечной ленты,состоящей из одинаковых ячеек, в каждой из которых записан какой тосимвол из непустого конечного алфавита А ={a0...an} (обычно a0=0, a1=1} Эта лентаизначально конечна, но может расширяться, путем добавления ячеек слева и справа.• Указателя, который в каждый момент времени находится над какой либо ячейкой, можетсдвигаться вправо или влево и считывать и заменять символы в ячейках.Также Машина в каждый момент находится в одном из своих внутренних состояний,обозначаемых символами из конечного алфавита Q={q0,q1...qm}, при этом обычно полагается,что А⋂Q=∅ q0 — заключительное состояние, q1 — начальное.• Программы, которая состоит из конечного набора команд видаqi aj → qk al S, qi qk∈ Q, aj, al∈ A, S∈ {L, Λ, R}Для каждой пары qi aj существует не более одной команды qi aj → qk al S.Каждая команда qi aj → qk al S работает по принципу: заменяем состояние с qi на qk (состояния≠ячейки)! , символ в текущей ячейке заменяем с aj на al и если S=L двигаемся на ячейку влево,R- вправо, Λ — остаемся на месте.

Если мы в последней справа (слева) ячейке, но S=R (L) тодописываем ячейку и записываем в нее 0.Определение 8.2Говорят, что произошла правильная остановка машины, если она попала в состояние q0.Если же машина попала в qa, но команды qa at → qk ap S нет, то говорят, что произошланеправильная остановка машины. Также машина может вовсе никогда не остановиться.Определение 8.3В каждый момент времени машина Тьюринга находится в некотором состоянии q и ее указательобозревает некоторую j-ю ячейку ленты, на которой записаны по порядку символы c1...cj...cp.Это мы будем называть конфигурацией машины Тьюринга (ее также можно записать словомc1...qcj...cp)Определение 8.4Пусть V и W- конфигурации машины М.

Тогда V =>M W означает что из V за конечное числошагов переходит в W и при этом М не достраивает ячеек слева.Определение 8.5Пусть f:N^R → N, f называется вычислимой на Машине Тьюринга М, если для любыхx1...xk∈N, если f(x1...xk) определена то 0q1 1^(x1+1)01^(x2+1)0...01^(xk+1)0..0 =>0q01^(f(x1...xk)+1)0...0. Если же f(x1...xk) не определена, то машина никогда не придет втребуемую конфигурацию.Теорема 8.1Функция вычислима на некоторой машине Тьюринга <=> функция является ч.р.фЭта теорема доказывается во многом аналогично теореме 7.2: сначала доказывается, что всепростейшие функции вычислимы на машинах Тьюринга, а затем показывается что функции,вычислимые на МТ замкнуты относительно операторов суперозиции, примитивной рекурсии иминимизации, затем доказывается рекурсивность отношения T(m,x`,y) m — код машиныТьюринга, x` - входные данные, y — код вычисления на этой машине из конфигурации 0q11^x0+10...01^(x(k-1)+1).

Затем доказывается рекурсивность U1(y) выдающей результат этоговычисления и показать что любая функция, вычислимая на машине Тьюринга представима ввиде U1(μy(T(m,x`,y))), откуда следует рекурсивность.Тема 9:Нумерации и алгоритмические проблемыОпределение 9.1Нумерацией множества S называется отображение из N в S. ν: N → S — нумерация, еслиν(N)=S, n → s∈ S n — номер s.Определение 9.2Упорядоченная пара (S,ν), где ν — нумерация, S — множество называется нумерованныммножеством.Определение 9.3С каждым нумерованным множеством (S,ν) и каждым S0 ⊊S связана алгоритмическая проблема(распознавания элементов по их ν-номерам). Эта проблема называется разрешимой, есливычислимо ν^(-1)(S0).Подмножества N можно считать алгоритмическими проблемами относительно тождественнойнумерации ν: n→ n.Пример 9.1Определим нумерацию ν0: N → Z следующим образом 0 → 0, 1 →1, 2 → -1, 3 → 2…Также определим код матрицы 2x2 с целыми коэффицентами a,b,c,d как <v0^(-1)(a), ν0^(-1)(b),ν0^(-1)(c), ν0^(-1)(d)>Теперь мы можем определить нумерацию ν(m) N → M2(Z) следующим образомν(m)= матрица с кодом x, если x- код некоторой матрицыи E (единичная матрица) в противном случае.Определение 9.4Нумерация ν вычислима если отношение {(x,y)|ν(x)=ν(y)} вычислимо.Определение 9.5Нумерация v называется однозначной, если ν взаимно однозначная (при этом и ν^(-1) будетвзаимно-однозначной).Прежде чем рассмотреть следующую теорему вооружимся несколькими определениями:Определение 9.6Запись f(x`)↑ означает, что значение f(x`) неопределено, а запись f(x`)↓ означает что значениеf(x`) определено.Также напомним обозначение {x}(y`)=U(μt(T(x,<y`>,t))).Теорема 9.1.

(Неразрешимость проблемы остановки)Проблема принадлежности множеству K:={x∈N|{x}(x)↓} неразрешима (иными словамиотношение K невычислимо). (не существует алгоритма, способного по заданной программе иданным вычислить, завершит ли программа свою работу)Доказательство:Предположим противное: Пусть эта проблема разрешима.

Тогда рассмотрим функцию f(x)=0,если x∉ K и неопределенную в противном случае). Ее также можно записать как μy(y=0 ^ x ∉K),то есть f(x) — ч.р.ф, а значит вычислима на некоторой мини-машине с номером а, и какследствие f(x)={a}(x). Заметим что f(x)↓<=>x∉K<=>{x}(x)↑. Но т.к. f(x)={a}(x) имеем что {a}(x)↓ <=> {x}(x)↑. Так как x является произвольным, взяв x= a имеем что {x}(x)↓<=>{x}(x)↑ итаким образом получаем противоречие (значение неопределено и определено одновременно).Следствие 9.1Отношение Κ1={<x,y>∈N|{x}(y)↓} невычислимоДоказательствоЗаметим, что, если бы это отношение было вычислимо, то взяв y=x мы получили бы способвычислить принадлежность отношению {x∈N|{x}(x)↓}.Также примером неразрешимых проблем является проблема распознания многочленов f скоэффицентами из Z[x1,x2…]: ∃x`: f(x`)=0Определение 9.7Обозначение ϰ_n(x)={n}(x) (каппа) — одноместная ч.р.ф от x.Определение 9.8Будем говорить что последовательность одноместных функций (fi) i∈N вычислима, еслисуществует чрф F(i,x) такая что fi(x)~F(i,x)Теорема 9.2 (О неподвижной точке)Пусть h(t) - о.р.ф.

Тогда существует натуральное n такое что:ϰ_h(n)=ϰ_ nДоказательство:Докажем вспомогательную лемму:Лемма 9.11)Последовательность функций (fi) вычислима2)Существует такая о.р.ф g что для всех i выполнено fi=ϰ_g(i)3)Существует такое k, что функция ϰ_k — о.р.ф и для всех i выполнено fi=ϰ_ (ϰ _k)(i)Доказательство:2 <=> 3 достаточно заметить что g и есть та самая ϰ_k1→ 2Поскольку (fi) вычислимая последовательность то существует чрф F(i,x). По теореме опараметризации существует о.р.ф g такая что F(i,x)~{g(i)}(x)~ ϰ_g(i), что и требовалось2→ 1Имеем fi(x)~ϰ_g(i)~{g(i)}(x)~U(μy (T(g(i),<x>,y)), эту функцию и можно взять как F(i,x), что итребовалось.Теорема 9.2 (продолжение)Предположим что h — одноместная о.р.ф, для которой нарушается условие теоремы, а именнодля любого натурального n ϰ_h(n)≠ϰ_ n.В таком случае рассмотрим бесконечную таблицу, где на (i,j) месте находится ϰ_ (ϰ _i)(j), а вслучае если такое значение не определено можем оставлять позицию пустой.Будем называть строку этой таблицы полной, если в ней нет позиций, на которых не стоитничего (или иными словами функция ϰ_ (ϰ _i) всюду определена).

По лемме 9.1 все такие строкиэто в точности все возможные вычислимые последовательности функций. Тогда построим спомощью предположения о функции h полную строку вида f0,f1… не совпадающую ни с однойиз уже существующих в таблице следующим образом:1)если значение ϰ_k(k) определено то возьмем fk=ϰ_(h(ϰ_k(k))) и тогда fk≠ϰ_(ϰ_k(k)) то естьнаша строка отличается от k-ой строки на k-ом месте.2)Если же ϰ_k(k) не определено то пусть fk — нигде не определенная функция (в этом случаенам нет нужды делать нашу строку отличной от k-ой, поскольку она не полная.)Проверим, что последовательность fi вычислима.

Для этого достаточно заметить чтоfi(x)~ϰ_(h(ϰ_i(i))(x)~{h({i}(i))}(x). (Если значение ϰ_i(i) определено то равенство поопределению, иначе с обеих сторон стоят неопределенные функции и равенство верно)).Но поскольку последовательность построенная нами вычислима, то она уже содержится средистрок нашей таблицы. Получаем противоречие (пусть эта последовательность совпадает с k-ойстрокой) Поскольку строка полная то определена ϰ_k(k) и также совпадаютfk=ϰ_(ϰ_k(k))=ϰ_(h(ϰ_k(k))), что приводит к тому, что предположение о h неверно).Функцию h(t) можно понимать как алгоритмический преобразователь программ.