В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 5

Ниже рас-сматриваются функции типа.В качестве базисных функций беруются следующие:1) нуль-функция : 0(x)=0 ∀ x ∈ N0f : N0n → N0 функция следования: s(x)=x+1 ∀ x ∈ N0n3) Функция выбора аргументов: Im ( x1 ,..., xn ) = xm ,∀ n ∈ N ,1 ≤ m ≤ n2)Допустимыми операциями над функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.Операция суперпозиции. Пусть даны n-местная функция g и n функцийf1 ,..., f nСчитаем, что функции f1 ,..., f n зависят от одних и тех жепеременных x1 ,..., xm. Это можно сделать путем введения фиктивныхпеременных.

Суперпозицией (подстановкой) функцийфункцияgи f1 ,..., f n называетсяh( x1 ,..., xm ) = g ( f1 ( x1 ,..., xm ),..., f n ( x1 ,..., xm ))(1)Если среди заданных функций имеются частичные, то и функция h будетчастичной.Функция h на наборе переменных x1 ,..., xm определена тогда итолько тогда, когда определены все функции f1 ( x1 ,..., xm ) ,...,f n ( x1 ,..., xm ) и функция h определена на наборе f1 ( x1 ,..., xm ) ,...,f n ( x1 ,..., xm ) . Операцию суперпозиции обозначают :h = S( g , f1 ,..., f n )Операция рекурсии (точнее: примитивной рекурсии).

Пусть заданы n местная функция g ( x1 ,..., xn ) и n+2-местная функция h ( x1 ,..., xn , y, z) .Определим n+1-местную функциюсоотношений:fиндуктивным образом с помощьюf ( x1 ,..., xn ,0) = g ( x1 ,..., xn )f ( x1 ,..., xn , y + 1) = h( x1 ,..., xn , y, f ( x1 ,..., xn , y))(2)Ясно, что данные соотношения однозначно определяют функциюf.Еслиf ( x1 ,..., xn , y + 1) считается определенной втом и только в том случае, когда определены f ( x1 ,..., xn , y) иh( x1 ,..., xn , y, t) при t = f ( x1 ,..., xn , y) Значит, если f ( x1 ,..., xn , y0 )функцииgиhчастичные, то25неопределено, то иf ( x1 ,..., xn , y)неопределено при y>y0 .Про функциюговорят, что она получена рекурсией из функ-цийf = R( g , h ) .gиhfи обозначаютОперация минимизации .Пусть задана n -местная функцияg ( x1 ,..., xn − 1 , y) .

Зафиксируем набор ( x1 ,..., xn − 1 , xn ) и рассмотримуравнение относительно y :g ( x1 ,..., xn − 1 , y) = xn(3)Будем решать данное уравнение, вычисляя последовательноg ( x1 ,..., xn − 1 ,0) . g ( x1 ,..., xn − 1 ,1) , g ( x1 ,..., xn − 1 ,2) и сравнивая сxn . Наименьшее y , для которого выполнено (3) обозначим(4)µ y = ( g ( x1 ,..., xn − 1 , y) = xn )y определено, если g ( x1 ,..., xn − 1 , z) определенопри всех z ≤ y . В противном случае считаем, что y неопределено. Зна-чение yесть функция f от переменных x1 ,..., xn − 1 , xn , про которую говорят, что онаПри этом считаем, чтополучена изf = My g(5)Заметим, что определенные выше операции S и R , будучи приме-ненными квсюду определенным функциям, дают всюду определенные функции.

ОперацияM может давать частичные функции даже при при-менении к всюдуопределенным функциям.ПримерЗдесьµ y ( x2 + y) = x1 − x2g ( x2 , y) = x2 + y всюду определена, но x1-x2определена толькопри x 1 ≥ x 2 .Дадим теперь основное определение данного раздела. функция - называетсячастично рекурсивной, если она может быть получена из базисных функций 0(x), s(x), I mn ( x 1,..., x n ) применением конечного числа раз операций суперпозиции,рекурсии и минимизации.

Иногда частично рекурсивные функции называютфункциями, вычисли-мыми по Черчу. Всюду определенная частичнорекурсивная функция называется общерекурсивной .Если рассматривать тот жебазис функций, то в качестве допустимых операций брать операциисуперпозиции и рекурсии, то получаемые функции называются примитивнорекурсивными.Обозначим : Ч- класс частично рекурсивных функций, Ч0 - классобщерекурсивных функций, Чпр - класс примитивно-рекурсивных функций.Класс частично рекурсивных функций - одно из главных понятий теорииалгорипмов.

Это объясняется тем, что какие бы классы точно очерченных26"алгоритмов" до сих пор не рассматривались, во всех случаях оказывалось, чтосоответствующие числовые функции, вычислимые посредством алгоритмов этихклассов, были частично рекурсив-ными. Поэтому общепринятой являетсягипотеза, формулируемая какТезис Черча (для частично рекурсивных функций).Класс алгоритмически вычислимых функций совпадает с классом всехчастично рекурсивных функций. Принятие данного тезиса позволяетистолковывать доказательство, что некоторая функция не является частичнарекурсивной, как доказатеяьство отсутствия алгоритма вычисления ее значений.Сделаем одно замечание. Пусть необходимо доказать, что конкретнаяфункция вычислима.

Это можно сделать следующими способами.1. Написать программу машины Тьюринга или МПД, вычисляющую f ,принадлежит классу функций, вычислимость которыхлибо показать, что fдоказана.2. Написать рекурсивную схему для f , показывающую, что fчастично рекурсивна.3. Дать неформальное (но достаточно точное) описание алгоритма,f , и затем сослаться на тезис Черча.вычисляющегоМы будем пользоваться способом 3) как строгим методом доказательства,основанным на тезисе Черча .20 )Приведем примеры частично рекурсивных функций и установимчастичную рекурсивность основных числовых функций, используемых варифметике и анализе .1.

Функции-константы.f ( x ) = m = s( s(... s( 0( x ))... ))_ m раз .2. Функция f ( x , y ) = x + yИмеемx + 0 = x = I 12 ( x , y )x + ( y + 1) = ( x + y ) + 1Это есть рекурсия с помощью функций g(x)=x и h(x,y,z)=s(z).3. Функция f ( x , y ) = x yx0 = 0Имеемx ( y + 1) = x y + xЭто есть рекурсия с помощью функций g(x)=0(x) , h(x,y,z)=x+z4.

Функция f ( x , y ) = x yИмеемx0 =1x y +1 = x x yЭто есть рекурсия с помощью функций g(x)=s(0(x)) , h(x,y,z)=xz.5. ФункцияИмеем0 , если x = 0sg ( x) = 1 , если x > 0sg( 0 ) = 027sg( x + 1) = 1Это рекурсия, в которой g=0(x) , h=s(0(x))1 , если x = 00 , если x > 0sg ( x ) = 1Имеемsg ( x + 1) = 06. Функция sg ( x) = Это рекурсия, в которой g=1 , h=0.0 , если x < y x − 1 , если x ≥ y0 −& 1 = 0( x + 1) −& 1 = x7. Функция x −& 1 = ИмеемЭто рекурсия, в которой g=x , h=y .8. Функция x −& y = 0 , еслиx< y x − y , если x ≥ yИмеем x −& 0 = xx −& ( y + 1) = ( x −& y) −& 1Это рекурсия, в которой g=x , h= z −& 19.

ФункцияИмеем−−x−y.x − y = ( x −& y) + ( y −& x)Замечание. Поскольку функцияx − y общерекурсивна, то можно заменитьопределение операции миними-зации, рассматривая вместоf ( x1,..., x n ) = µ y ( g ( x1,..., x n −1, y ) = x n )функции видаf ( x1,..., x n ) = µ y ( h( x1,..., x n , y ) = 0)Определяемый класс функций при этом будет тем же самым.10. Функция min( x , y )Имеем min( x , y ) = x −&( x −& y )11. Функция max( x , y )Имеем max( x , y ) = x + ( y −&x )28x  y  -целая часть от деления x на у x По определению полагаем 0  = x , чтобы функция была всюду12. Функцияопределена. xИмеем   = µz< x (( x −& z)(( x + 1) −& y( z + 1)) = 0) yДействительноно, при у=оµz (( x −& z)(( x + 1) −& y( z + 1)) = 0) = µz (( x −& z) = 0) = xy ≠ 0 существует минимальное z, z ≤ x , при котором( x + 1) −& y(z + 1) = 0 или ( x + 1) ≤ y ( z + 1) или x < y ( z + 1) откуда C=z.13.

Функция res( x , y ) -остаток от деления x на y.x Имеем res( x , y ) =x-y   yПри14. Функция1 , если res( x, y) = 0d ( x, y) = 0 , если res( x, y) ≠ 0Имеем d ( x , y ) = sg ( res( x , y ))15. Двоичная степень числа x.exp2 ( x) = t , еслиИмеем exp 2 ( x ) =общерекурсивна.2 t x , но2 t +1 не делитxµ t ( d ( x , et +1 ) = 0) и замечаем , что функция 2t +1 -16.

Функция, отличная от О в конечном числе точек. Еслиf (x ) ≠ 0 вf ( x1 ) = y1,..., f ( x k ) = yk ,то имеемf ( x ) = y1 sg x − x1 + y2 sg x − x 2 +...+ yk sg x − x kточках x 1,... x k , причемАналогично можно доказать (примитивную) рекурсивность функцийа) π ( x ) = число простых чисел, не превосходящих x.б) q ( x) = x −&[ x] -квадратичный остаток числа x.2p( x ) = px (x+1)-ое -простое число( p0 = 2 , p1 = 3 , p2 = 5 , p3 = 7 )в)30 ) Покажем теперь вычислимость на МПД частично рекурсивныхфункций.29Базисные функции 0( n ) , s( n ) , I mn ( x 1,..., x n ) вычислимы на МПДкомандами Z ( n ) , S ( n ) , T ( m , 1) .Вычислимость суперпозицийТеорема1. Пусть функции g ( y1,..., yn ) , f1 ( x 1,..., x m ) ,..., f n ( x 1,..., x m )вычислимы на МПД.

Тогда вычислима и функцияy( x 1,,, x m ) = S ( g; f1,..., f n )Док-во.Пусть G, F1,..., Fn - программа стандартного вида для вычисленияфункций g, f1,..., f n соот-ветственно. Напишем программу H для вычисленияфункции h.Положим t = max( n, m, r(G ), r( F1 ),..., r( Fn ))Запомним x 1,..., x m в регистрах R t +1,..., R t + m , в регистрахR t + m +1,..., R t + m + n запоминаем значения F1 ( x 1,..., x m ),..., Fn ( x 1,..., x m )соответственно. Указанные регистры не затрагиваются вычисле- ниями попрограммам G, F1,..., Fn .Теперь дадим программу H вычисления h :T (1, t + 1)T ( 2, t + 2 )....T ( m, t + m )F1[t + 1,..., t + m → t + m + 1]....Fn [t + 1,..., t + m → t + m + n]G[t + m + 1,..., t + m + n → 1]30Вычисление по программе H происходит в соответ-ствии с блок-схемойначало ( x 1,..., x n ,0,...