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

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

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

[5], [6]).Определение. Упорядоченная пара A = hA, Πi называется нормальным алгорифмом в алфавите A, если выполняются следующие условия:1) A — конечный непустой алфавит, не содержащий символы → и →·2) Π = hΦ1 , . . . , Φn i — конечный упорядоченный список так называемых формулподстановки (редукций) в алфавите A, т. е. цепочек вида P → Q или P →· Q,где P, Q — некоторые (возможно, пустые) слова в алфавите A.Редукция вида P → Q называется простой. Редукция вида P →· Q называется заключительной.§ 16.

Нормальные алгорифмы Маркова65Список Π называется схемой алгорифма A, которую обычно записывают в видеP1 → (· )Q1......Pn → (· )Qn ,где Pi → (· )Qi есть либо редукция Pi → Qi , либо редукция Pi →· Qi . Порядок записиредукций в схеме алгорифма имеет значение!Определение (шаг работы нормального алгорифма).

Пусть A — нормальный алгорифм в алфавите A, P — слово в алфавите A. Возможны следующие два случая:1) Ни одно слово P1 , . . . , Pn не является подсловом в P . Тогда пишем A:P A иговорим, что P не поддается нормальному алгорифму A.2) Среди слов P1 , . . . , Pn существуют такие, которые являются подсловами в P .Пусть m — наименьшее такое, что 1 6 m 6 n и Pm — подслово P . Определимслово R, которое получается из P заменой самого левого вхождения Pm наслово Qm .

При этом:а) если Φm имела вид Pm → Qm , то пишем A:P ` R и говорим, что A простопереводит P в R;б) если Φm имела вид Pm →· Qm , то пишем A:P `· R и говорим, что A заключительно переводит P в R.Определение. Пусть A — нормальный алгорифм в алфавите A, P — слово в алфавите A. Говорят, что A преобразует слово P в слово R и пишут A(P ) = R, еслисуществует конечная последовательность R0 , R1 , .

. . , Rk слов в алфавите A такая, чтоR0 = P, Rk = R и выполняется одно из двух условий:1) либо для любого i = 0, 1, . . . , k − 1 выполняется A:Ri ` Ri+1 и A:Rk A;2) либо для любого i = 0, 1, . . . , k − 2 выполняется A:Ri ` Ri+1 и A:Rk−1 `· Rk .Обозначим dom A = {P ∈ A∗ | ∃R A(P ) = R}. Говорят, что A применим к слову P ,если P ∈ dom A; в противном случае говорят, что A не применим к слову P .Замечание. Алгорифм A не применим к слову P тогда и только тогда, когда существует бесконечная цепочка A : P ` P1 ` P2 ` .

. .Определение. Частичная функция f : dom(f ) ⊆ ω n −→ ω называется вычислимойпо Маркову, если существует нормальный алгорифм A в некотором алфавите A ⊇{0, 1} такой, что:а) если (x1 , . . . , xn ) ∈ dom(f ), то A применим к слову 1x1 +1 01x2 +1 0 . . . 01xn +1 и приэтом выполняется A(1x1 +1 01x2 +1 0 . . . 01xn +1 ) = 1f (x1 ,...,xn )+1 ;б) если (x1 , . . . , xn ) ∈/ dom(f ), то A не применим к слову 1x1 +1 01x2 +1 0 . . . 01xn +1 ;в) алгорифм A не применим к словам в алфавите {0, 1}, отличным от слов вида1x1 +1 01x2 +1 0 .

. . 01xn +1 .66Глава III. Формализации понятия вычислимой функции(Применимость алгорифма A ко всем остальным словам в алфавите A не имеетзначения.)Пример. Докажем, что функция sg(x) вычислима по Маркову. Для этого определимнормальный алгорифм A в алфавите {0, 1, α}, где α 6= 0, α 6= 1, по следующей схеме:0→0α111 → α11α11 →· 11α1 →· 1Λ→αЕсли P = 1x+1 , где x > 0, то A : 1x+1 ` α1x+1 ` α1x ` . . . ` α11 `· 11, т. е. Aприменим к слову 1x+1 , и A(1x+1 ) = 11 = 1sg(x)+1 .Если P = 1, то A : 1 ` α1 `· 1, т. е. A применим к слову 1, и A(1) = 1.Если P — слово в алфавите {0, 1}, отличное от 1x+1 , то либо P = Λ, либо Pсодержит 0.

Покажем, что в обоих случаях A не применим к P .Если P = Λ, то A : Λ ` α ` αα ` ααα ` . . ., т. е. будет бесконечно частоприменяться последняя редукция.Если P содержит 0, то P = 1n 0w, где n ∈ ω, w ∈ {0, 1}∗ . Тогда A : 1n 0w ` 1n 0w `n1 0w ` . . ., т. е. будет бесконечно часто применяться первая редукция.Таким образом, предложенный выше нормальный алгорифм A вычисляет функцию sg(x).Сформулируем теперь основной интересующий нас результат из теории нормальных алгорифмов.Теорема 43. Частичная функция вычислима по Маркову тогда и только тогда,когда она является частично рекурсивной.Общая схема доказательства теоремы 43 такая же, как для машин Шёнфилдаи машин Тьюринга, поэтому здесь мы его не приводим.

Подробности можно найти,например, в [6].В заключение, заметим, что употребление буквы «ф» в термине «нормальныйалгорифм» является традиционным при изложении теории нормальных алгоритмов. Эта традиция основана на произношении слова «algorithm». Тем не менее, внекоторых источниках встречается термин «нормальный алгоритм».§ 17.Тезис ЧёрчаИтак, мы рассмотрели четыре различные формализации понятия вычислимой функции: частично рекурсивные функции, машины Шёнфилда, машины Тьюринга и нормальные алгорифмы Маркова. Данные подходы отталкиваются от разных принципови имеют не похожие друг на друга реализации (за исключением, быть может, подходов Тьюринга и Шёнфилда). Более того, существуют другие, менее распространенные формализации понятия вычислимости.

Однако все известные формальныеподходы порождают один и тот же класс функций, в чем мы уже успели частичноубедиться. Сформулируем основное утверждение данной главы.§ 17. Тезис Чёрча67Теорема 44. Для произвольной частичной функции f : dom(f ) ⊆ ω n −→ ω следующие условия эквивалентны:1) f является частично рекурсивной функцией;2) f вычислима на машине Шёнфилда;3) f вычислима по Тьюрингу;4) f вычислима по Маркову.Доказательство.

Следует из теорем 16, 34, 42, 43.Поэтому в дальнейшем для нас не будет иметь значения, какая из данных формализаций выбрана. Объединим рассмотренные нами четыре формализации следующим определением.Определение. Частичную функцию f , удовлетворяющую условиям (1)–(4) теоремы44, будем называть частично вычислимой (ч.в.ф.). Всюду определенную функцию f ,удовлетворяющую условиям (1)–(4) теоремы 44, будем называть вычислимой (в.ф.).Таким образом, можно считать, что первоначальная цель, которая послужилаотправной точкой для развития теории вычислимости, достигнута — найдено формальное определение вычислимой функции.

Теорему 44 можно воспринимать какподтверждение высказывания, которое обычно называют тезисом Чёрча.Тезис Чёрча. Класс интуитивно вычислимых функций совпадает с классом всехчастично рекурсивных функций.Тезис Чёрча — это высказывание, которое говорит, что предложенная формализация понятия вычислимой функции адекватно отражает наши интуитивные представления о вычислимости. Исторически именно этот тезис был первым точным определением частично вычислимой функции.Тезис Чёрча не является формальным математическим утверждением. Однакопри доказательстве теорем он часто используется в неявном виде.

Как правило, этопроисходит следующим образом: чтобы доказать существование частично рекурсивной функции с определенными свойствами, в математических рассуждениях можетбыть показана ее интуитивная вычислимость, а строгое доказательство частичнойрекурсивности при этом опускается. Такой прием позволяет сократить объем доказательства, но автор любого такого доказательства должен быть готов представитьформальный вариант доказательства, не использующий тезис Чёрча.Глава IVТеория вычислимостиДанная глава является введением в теорию вычислимости и содержит фундаментальные понятия и теоремы из нескольких, ставших уже классическими, разделовэтой богатейшей теории.

Для дальнейшего изучения теории вычислимости можнопорекомендовать книги [1], [5], [9], [10].Следует особо подчеркнуть, что все результаты данной главы не зависят от выбора конкретного формального определения частично вычислимой функции. Длянас будет иметь значение только факт существования эффективной клиниевскойнумерации æke для класса всех k-местных частично вычислимых функций. Под эффективностью здесь мы понимаем справедливость s-m-n-теоремы, которая связываетнумерации æke для различных k.Можно интуитивно воспринимать æn как частичную функцию, вычисляемую n-малгоритмом при некотором эффективном перечислении всех алгоритмов. Однаконужно помнить, что подобный неформальный подход, так же как и рассуждения, использующие тезис Чёрча, всегда требуют формального обоснования.

Мы чаще всегобудем использовать формализм частично рекурсивных функций.§ 18.Теорема о неподвижной точкеТеорема о неподвижной точке (другое название — теорема о рекурсии) была доказана Клини и является одним из наиболее элегантных и важных результатов теориивычислимости. Ее короткое доказательство использует s-m-n-теорему и на первыйвзгляд кажется несколько мистическим.

Переформулируем s-m-n-теорему в новых,введенных нами выше терминах.s-m-n-теорема. Для любых m, n ∈ ω существует разнозначная (m+1)-местнаявычислимая функция smn (e, y1 , . . . , ym ) такая, что для всех e, y1 , . . . , ym , x1 , . . . , xn выполняетсяæm+n(y1 , . . . , ym , x1 , . . . , xn ) = ænsm(x1 , . . . , xn ).en (e,y1 ,...,ym )Конечно, в первоначальном варианте s-m-n-теоремы утверждалось, что функциюможно выбрать даже примитивно рекурсивной. Однако для наших дальнейшихцелей потребуется только ее вычислимость. Как и раньше, через x мы обозначаемкортеж hx1 , . . . , xk i.smnТеорема 45 (о неподвижной точке). Справедливы следующие два утверждения:1) Для любой частично вычислимой функции f (x, y) существует вычислимаяфункция g(x) такая, чтоæf (x,g(x)) = æg(x) .§ 18.

Теорема о неподвижной точке692) Для любой частично вычислимой функции f (x) существует a ∈ ω такое, чтоæf (a) = æa .Доказательство. Для доказательства первого утверждения рассмотрим частичновычислимую функцию F (e, y, x, z) = æk+2(y, x, z), которая является универсальнойeдля семейства всех (k+2)-местных ч.в.ф. По s-m-n-теореме существует вычислимаяфункция s(e, y, x) такая, чтоæk+2(y, x, z) = æs(e,y,x) (z).e(∗)Функция æf (x,s(y,y,x)) (z) является (k+2)-местной ч.в.ф. от переменных hy, x, zi.Следовательно, в силу универсальности найдется клиниевский номер n ∈ ω такой,что(∗∗)æf (x,s(y,y,x)) (z) = æk+2n (y, x, z).Из (∗) и (∗∗) при e = n следует, что æf (x,s(y,y,x)) (z) = æs(n,y,x) (z). Подставив вполученное тождество y = n, получим æf (x,s(n,n,x)) (z) = æs(n,n,x) (z).

Отсюда видно,что вычислимая функция g(x) = s(n, n, x) является искомой.Второе утверждение является вариантом первого в случае, когда кортеж x пуст.Его доказательство дословно повторяет рассуждения, проделанные выше. Разницалишь в том, что в итоге вместо функции g(x) = s(n, n, x) мы получим число a =s(n, n).В утверждении (1) доказывается существование неподвижной точки с параметрами, утверждение (2) — классическая теорема о неподвижной точке. Функцию f (x)из пункта (2) можно неформально представлять как эффективный преобразовательпрограмм, который любую программу n, реализующую процедуру æn , перерабатывает в программу f (n), реализующую, вообще говоря, какую-то другую процедуруæf (n) .

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

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