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

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

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

Его можно назвать алгебраическим, поскольку определяемый здеськласс функций будет порождаться из некоторых простейших функций с помощьюопределенных операций. Совокупность функций, возникающих в результате подобного алгебраического порождения, называется классом частично рекурсивных функций.В рамках данного параграфа рассматриваются только частичные функции наω, т. е. всевозможные функции вида f : X → ω, где множество X ⊆ ω n являетсяобластью определения функции, а число n ∈ ω — ее местностью.

Любую 0-местнуювсюду определенную функцию f = a мы отождествляем с константой a ∈ ω. Нигде неопределенная функция единственна и имеет вид f = ∅, причем любое натуральноечисло является местностью нигде не определенной функции.Если f — n-местная, а g — m-местная частичная функция, то для любых значенийx1 , . . . , xn , y1 , . .

. , ym ∈ ω мы пишем f (x1 , . . . , xn ) = g(y1 , . . . , ym ) тогда и только тогда,когда либо эти значения одновременно не определены, либо они оба определены исовпадают.Определение. Простейшими функциями называются нульместная функция 0,всюду определенные одноместные функции o(x) = 0, s(x) = x + 1 и n-местные функn(x1 , . . . , xn ) = xm для всех m, n таких, что 1 6 m 6 n.ции ImОпределение. Говорят, что функция f (x1 , . . .

, xn ) получается с помощью операторасуперпозиции S из функций h(y1 , . . . , ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ), если длялюбых x1 , . . . , xn выполняется:f (x1 , . . . , xn ) = h(g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )).40Глава III. Формализации понятия вычислимой функцииЗамечание. С неформальной точки зрения оператор суперпозиции соответствуетпринципу последовательного запуска вычислительных устройств, когда результатывычислений одних устройств служат входными данными для других.

Если f получена с помощью суперпозиции из h, g1 , . . . , gm , то вычисление значения f (x1 , . . . , xn )происходит следующим образом. Сначала на входных данных x = hx1 , . . . , xn i вычисляются значения y1 = g1 (x), . . . , ym = gm (x). Если хотя бы одно из этих значений неопределено, то значение f (x) тоже не определено. Если же все y1 , . .

. , ym определены,то затем они подаются на вход функции h. Если выходное значение h(y1 , . . . , ym ) неопределено, то f (x) считается неопределенным, иначе f (x) = h(y1 , . . . , ym ) определено и является окончательным выходным значением.Определение. Говорят, что функция f (x1 , . . . , xn , y) получается с помощью оператора примитивной рекурсии R из функций g(x1 , .

. . , xn ) и h(x1 , . . . , xn , y, z), если длялюбых x1 , . . . , xn , y выполняется схема примитивной рекурсии:(f (x1 , . . . , xn , 0) = g(x1 , . . . , xn )f (x1 , . . . , xn , y + 1) = h(x1 , . . . , xn , y, f (x1 , . . . , xn , y))Замечание. Оператор примитивной рекурсии формализует циклическую структуру, вычисляющую функции, заданные рекуррентными соотношениями (или по индукции). Если f получена с помощью примитивной рекурсии из g и h, то вычислениезначения f (x, y) происходит следующим образом. Сначала на входных данных x вычисляется значение g(x), которое совпадает с f (x, 0). Если это значение не определено, то f (x, y) тоже не определено, иначе, подав x, 0 и f (x, 0) на вход функции h, мывычисляем h(x, 0, f (x, 0)), которое совпадает с f (x, 1).

Если последнее значение неопределено, то f (x, y) не определено, иначе мы подаем x, 1 и f (x, 1) на вход функцииh, и так далее. Данные вычисления продолжаются до тех пор, пока мы не достигнемзначения f (x, y). Если при этом на промежуточных шагах хоты бы одно вычисляемоезначение функции h не определено, то f (x, y) считается неопределенным.Определение. Говорят, что функция f (x1 , . . . , xn ) получается с помощью оператора минимизации M из функции g(x1 , . . . , xn , y) и обозначается f (x1 , . .

. , xn ) =µy[g(x1 , . . . , xn , y) = 0], если для любых x1 , . . . , xn выполняется:если g(x1 , . . . , xn , 0), . . . , g(x1 , . . . , xn , y − 1)y,определены и не равны 0, а значениеf (x1 , . . . , xn ) =g(x1 , . . . , xn , y) определено и равно 0,не определено в противном случае.Замечание. Оператор минимизации формально описывает такой вычислительныйприем, как эффективный перебор: последовательно перебирая числа из натурального ряда, мы проверяем, удовлетворяет ли текущее число фиксированному эффективному условию.

Эффективное условие записывается в виде уравнения g(x, y) = 0.Вычисление значения f (x) происходит следующим образом. Сначала на входныхданных x, 0 вычисляется значение g(x, 0). Если это значение не определено, то f (x)тоже не определено. Иначе если g(x, 0) = 0, то вычисления заканчиваются – число 0будет подано на выход. Если же g(x, 0) 6= 0, то на входных данных x, 1 вычисляетсязначение g(x, 1). Если это значение не определено, то f (x) тоже не определено. Иначеесли g(x, 1) = 0, то вычисления заканчиваются – число 1 будет подано на выход.

Если же g(x, 1) 6= 0, то данный процесс продолжается. В результате мы либо вычислим§ 11. Частично рекурсивные функции41наименьшее решение уравнения g(x, y) = 0, либо ничего не вычислим. Последнеевозможно по двум причинам: либо некоторое вычисляемое значение функции g окажется неопределенным, либо g(x, y) определено для всех y, но не равно нулю.Определение. Частичная функция f (x1 , .

. . , xn ) называется частично рекурсивной(примитивно рекурсивной), если существует конечная последовательность функцийf0 , . . . , fm = f такая, что для любого i 6 m функция fi либо простейшая, либополучается из некоторых предыдущих с помощью одного из операторов S, R или M(операторов S или R).Определение. Всюду определенные частично рекурсивные функции называтся рекурсивными.Замечание. Будем использовать сокращения: ч.р.ф.

— для частично рекурсивныхфункций, п.р.ф. — для примитивно рекурсивных функций, р.ф. — для рекурсивныхфункций.Из определения следует, что если функция f получается из некоторых ч.р.ф.(п.р.ф.) с помощью оператора S, R или M (S или R), то f тоже является ч.р.ф.(п.р.ф.).Кроме этого, очевидно, между введенными классами функций имеют место следующие теоретико-множественные включения:ПРФ ⊆ РФ ⊆ ЧРФ.Замечание. Заметим, что одноместную функцию o(x) можно исключить из числапростейших функций — класс частично рекурсивных функций при этом не изменится. Это следует из того, что o(x) можно получить из 0-местной функции 0 и 2-местнойфункции I22 (x, y) с помощью оператора примитивной рекурсии.Теорема 16 (о вычислимости ч.р.ф. на машинах Шёнфилда). Любая частично рекурсивная функция является вычислимой на машине Шёнфилда.Доказательство. Пусть f — ч.р.ф.

Следовательно, по определению существует конечная последовательность функций f0 , . . . , fk = f такая, что для любого i 6 kфункция fi либо простейшая, либо получается из некоторых предыдущих с помощью оператора S, R или M . Индукцией по числу k ∈ ω докажем, что f вычислимана некоторой машине Шёнфилда.Если k = 0, то f является простейшей, т. е. либо константой 0, либо функциейn(x1 , . . . , xn ). Следующие три макроo(x), либо функцией s(x), либо функцией вида Imпрограммы вычисляют эти функции на машинах Шёнфилда (0 и o(x) вычисляютсяодной программой):0 и o(x):0:ZERO 0 s(x):0:INC 11:[1] → [0]n(x):Im0:[m] → [0]Пусть k > 0. Тогда f получена из некоторых ч.р.ф. с помощью одного из трехоператоров.

Рассмотрим соответствующие три случая.Если f (x1 , . . . , xn ) получена с помощью оператора суперпозиции из h(y1 , . . . , ym ),g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ), то в силу индукционного предположения функцииh, g1 , . . . , gm вычислимы по Шёнфилду. Тогда следующая макропрограмма вычисляет функцию f :42Глава III. Формализации понятия вычислимой функции0:···m−1 :m:g1 ([1], . . . , [n]) → [n + 1]···gm ([1], . . . , [n]) → [n + m]h([n + 1], .

. . , [n + m]) → [0].Если f (x1 , . . . , xn , y) получена с помощью оператора примитивной рекурсии изчастичных функций g(x1 , . . . , xn ) и h(x1 , . . . , xn , y, z), которые мы считаем вычислимыми по Шёнфилду, то следующая макропрограмма будет вычислять f :0 : g([1], . . . , [n]) → [0]1 : [n + 1] → [n + 2]2 : ZERO n + 13 : INC 04 : DEC 0, 85 : h([1], . . . , [n], [n + 1], [0]) → [n + 3]6 : [n + 3] → [0]7 : INC n + 18 : DEC n + 2, 5Если функция f (x1 , . .

. , xn ) получена с помощью оператора минимизации из вычислимой по Шёнфилду функции g(x1 , . . . , xn , y), то следующая макропрограммабудет вычислять f :0:1:2:3:4:INC 0DEC 0, 3INC 0g([1], . . . , [n], [0]) → [n + 1]DEC n + 1, 2Теорема доказана.§ 12.Рекурсивность некоторых функций и отношенийНашей дальнейшей целью является доказательство утверждения, обратного теореме16. Для этого нам потребуется целая серия предварительных фактов и новых понятий. Всюду далее через x мы обозначаем кортеж hx1 , .

. . , xn i, при n = 0 этот кортежсчитается пустым.Лемма 17. Все нульместные всюду определенные функции являются примитивнорекурсивными.Доказательство. Пусть a ∈ ω — произвольная константа. Возможны два случая.Если a = 0, то это по определению простейшая функция, и значит она являетсяп.р.ф. Если же a > 0, то a = s(s .

. . s(0) . . .), т. е. a получена из простейших функций| {z }a0 и s(x) с помощью a-кратного применения оператора S.Лемма 18. Следующие функции являются примитивно рекурсивными:а) f (x, y) = x + y;б) f (x, y) = x · y;§ 12. Рекурсивность некоторых функций и отношенийв) f (x, y) =(xy0,г) sg(x) =1,(1,д) sg(x) =0,43(здесь 00 = 1);x = 0;x > 0;x = 0;x > 0;(0,x = 0;¦е) f (x) = x−1=x − 1, x > 0;(0,x 6 y;¦ж) f (x, y) = x−y=x − y, x > y;з) f (x, y) = |x − y|Доказательство.

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

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