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

)Запомнитьx 1,..., x m в R t +1,..., R t + mf1 ( x 1,..., x m ) → R t+ m+1f k ( x 1,..., x m ) → R t+ m+1g ( f1,..., f n ) → R 1Ясно: вычисление H ( x 1,..., x m ) останавливается ⇔ заканчиваетсявычисление каждой Fi ( x 1,..., x m ) , i ∈1, n и вычислениеG ( f1 ( x 1,..., x m ),..., f n ( x 1,..., x m ))ч.т.д.Следствие Пусть f ( y1,..., ym ) вычислимая на МПД функция и x i1 ,..., x iv )последовательность m переменных из С(возможно с повторениями).

Тогдафункция h( x 1,..., x n ) = f ( x i1 ,..., x iv ) вычислима.док-во.Если x = ( x 1,..., x n ) ,то h( x 1,..., x n ) = f ( I in1 ( x ),..., I inm ( x )и потому hвычислима.ч.т.д .Вычислимость рекурсииТеорема 2.Пусть функции g ( x 1,..., x n ) , h( x 1,..., x n , y, z ) - вычислимы на МПД. Тогдафункция f = R ( g, h) - вычислима.Док-во.Пусть G и H программы стандартного вида для вычисления функций g и h.Построим программу F вычивляющую функцию f = R ( g, h ) .По начальнойконфигурации ( x 1 ,..., x n , y,0,... ) по программе G вычисляетсяf ( x 1,..., x n ,0) = g ( x 1,..., x n ) . Теперь, если y ≠ 0 то применяем (многократно)программу Y* для нахождения f ( x 1,..., x n ,1) , f ( x 1,..., x n ,2 ) ,..., f ( x 1,..., x n y )31Положим m = max( n + 2, r (G ), r ( H ))Запоминаем x 1,..., x n , y в регистрах R m +1,..., R m + n , R m + n+1 .Номер цикла к ,где к=0,1,...,y помещаем в Rm+n+2.

Промежуточное значение f ( x 1,..., x n , k )помещаем в Rm+n+3. Вычисление по программе Н происходит в соответствии сблок-схемой.начало ( x 1,..., x n , y,0,... )1.запомнить ( x 1,..., x n , y,0,... )в R t + m +1,..., R t + m + n2.запомнить k в R m + n+ 2(в начале k=0)f ( x 1,..., x n ,0) = g ( x 1,..., x n ,0) → R m + n+3x=y( rm + n+2 = rm + n+1 ?)даk:k+1нетf ( x 1,..., x n , y ) → R 1rm + n+3 = R 1остановf ( x 1,..., x n , k + 1) = h( x 1,..., x n , k , f ( x 1,..., x n , k )) → R m + n+332Помещаем x 1 ,..., x n , k в регистры R m +1,..., R m + n , R m + n+1 . Полагаем вначалеk=0.Промежуточное значиние f ( x1 , ..., x n , k ) помещаем в R m + n +2 . Вычислениефункции g происходит в соответствии с блок-схемой:начало ( x 1,..., x n , y,0,...

)запомнить x 1 ,..., x nв R m +1,..., R m + nзапомнить k в R m + n +1(в начале k=0)f ( x 1,..., x n , k ) → R 1k:k+1f ( x 1 ,..., x n , k ) → R 1( rm + n+2 = rm + n+3 ?)даk → R1нет33Программа F для вычисления f : (Здесь t=m+n):T (1, m + 1)...T ( n + 1, m + n + 1)Iq :J (t + 2,t + 1, p)H [ m + 1,..., m + n,t + 2,t + 3 → t + 3]S (t + 2 )J (11, ,q )Ip : T (t + 31,)`Следовательно, функция f вычислима.ч.т.д.Вычислимость минимизации.Tеорема3.Пусть функция f ( x1 ,..., x n , y) вычислима.тогда функцияg ( x1 ,..., x n ) = µ y ( f ( x1 ,..., x n , y) = 0) вычислима.Док-во.Пусть F-программа стандартного вида,вычисляющая функцию f .Пустьm = max( n + 1, r ( F )) .Построим программу G для вычисления функции g последующему алгоритму: вычислять f ( x1 ,..., x n , k ) при k=0,1,... до тех пор, покане найдется такое k,что f ( x1 ,..., x n , k ) = 0 тогда k будет требуемым выходом.Программа G для вычисления функции g :T (1, m + 1)....`T ( n, m + n)F [ m + 1,..., m + n → m + n + 2]Iq :S ( m + n + 1)J ( m + n + 2, m + n + 3, q )J (11, , p)Ip : T ( m + n + 11,).следовательно , функция g вычислима.ч.т.д.34Следствие.Частично рекурсивные функции вычислимы на МПД,т.е.Ч ⊆ Е..4 0 ) Покажем теперь частичную рекурсивность вычислимых функций.Теорема 4.

Всякая вычислимая на МПД функция является частичнорекурсивной.Док-во.Пусть f ( x1 ,..., x n ) вычислимая на МПД функция и пусть P = I1 I 2 ... I s соответствующая программа.Будем называть шагом вычисления выполнениеодной команды программы.Для произвольных x = ( x1 ,..., x n ) и t ∈ N 0определим следующие функции , свезанные с вычислением P( x ) : r1 (с о д е р ж и м о е R1 ) после t ш а г о в в P( x) , если P( x) не остановилось раньшеc( x, t) = r (соде ржимое R1 ) , если P( x) остановилось1раньше.ном е р следующей команды , после t ш а г о вв P( x) , если P( x) не остановилосьc( x, t) = после t шагов или раньше 0 , если P( x) остановилось послеt шаговили раньше.c( x ,0) = x1j ( x ,0) = 1Очевидно, что функции c( x , t ) , j ( x , t ) всюду определены.Найдем теперь выражение для f ( x ) через введенные функции.

Еслизначение f ( x ) определено, то P( x ) останавливается после t 0 шагов, гдеt 0 = µ t ( j ( x , t ) = 0)Таким образом,поэтомуf ( x ) = c( x , t 0 )Если хе значение f ( x ) неопределено, то P( x ) не останавливается, и тогдаj ( x , t ) ≠ 0 ∀t ∈ N 0 , поэтому µ t ( j ( x , t ) = 0) не опредено. Следовательно, вовсех случаях f ( x ) = c( x , µ t ( j ( x , t ) = 0))Теперь, если убедиться, что функции c( x , t ) и j ( x , t ) частичнорекурсивны, то таковой будет и функция f ( x ) .

Ясно,что существуетнеформальный алгоритм вычисления значений функций c( x , t ) и j ( x , t ) . Для35этого нужно по заданным x , t написать последовательность конфигурацийK 0 → K1 →... → Kt и выписать содержимое регистра R1 к номер выполняемойна шаге t+1 команды. По тезису Черча функции c( x , t ) и j ( x , t ) частичнорекурсивны и, значит, функция f ( x ) является частично рекурсивной.ч.т.д.Замечание Более точный анализ показывает, что функции c( x , t ) и j ( x , t )является примитивно рекурсивными.Следствие.

Классы функций Ч и Е совпадают, т.е. Ч=Е .50 ) Рассмотрим теперь вопрос о соотношении введенных классовЧпр,Ч0,Ч.Поскольку класс Ч содержит частично определенные функции, то ясно,что Ч0 ⊂ Ч.Кроме того, очевидно,что Чпр ⊆ Ч.Вопрос о том, является ли включение Чпр ⊆ Ч соб- ственным решаетсянесколько сложнее.Первый пример общерекурсивной функции, не являющейся примитивнорекурсивной,был дан Аккерманом (1928 г.).Функция Аккермана ϕ ( x , y) задается соотношениеми :ϕ( x ,0) = y + 1ϕ ( x + 1,0) = ϕ ( x ,1)ϕ ( x + 1, y + 1) = ϕ ( x , ϕ ( x + 1, y))Можно доказать, что данные соотношния однозначно определяютфункцию ϕ ( x , y) .Например,ϕ ( 0,0) = 1 , ϕ ( 0,1) = 2 , ϕ (1,0) = 2ϕ (11, ) = ϕ ( 0, ϕ (1,0)) = ϕ ( 0,2) = 3ϕ ( 2,0) = ϕ (11,)=3ϕ (1,2) = ϕ ( 0, ϕ (11, )) = ϕ ( 0,3) = 4ϕ ( 3,0) = ϕ ( 2,1) = ϕ (1, ϕ ( 2,0)) = ϕ (1,3) == ϕ ( 0, ϕ (1,2)) = ϕ ( 0,4) = 5Результаты вычислений убеждают,что найдется алгоритм вычисленияфункции ϕ ( x , y) .В то же время доказывается, что функция ϕ ( x , y) не является примитивнорекурсивной,т.к.

растет быстрее, чем любая одноместная примитивнорекурсивная функция.Доказательство, ввиду его громоздкости, опускается (см. Мальцев (7), стр.105).36§ 5. Нумерация наборов чисел и слов10 ) В теории алгоритмов получил распространение прием, позволяющийсводить изучение функций от нескольких переменных к изучению функцийодной переменной.

Он основан на нумерации наборов чисел так, что имеетсябиективное соответствие между наборами чисел и их номерами, причемфункции, определяющие по набору чисел его номер и по номеру сам набор чиселявляются общерекурсивными.Рассмотрим сначала множество N 0 ∗ N 0 - множество пар натуральныхчисел. Рассмотрим следующее упорядочение этих пар, называемоеканторовским:(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...(1)Здесь в порядке возрастания n ∈ N 0 упорядочиваются пары (x,y)с условиемx+y=n в виде последовательности(0,n),(1,n-1),...,(x,y),...,(n,0)(2)Пусть c(x,y)- номер пары (x,у)в последовательности (1), причем считаемc(0,0)=0.

Если c(x,y)=n , то обозначим через r , l - функции, удовлетворяющие:x = l( n )y = r( n )и, следовательно,c( l ( n ), r( n )) = nПокажем, что функции с , l , r в явном виде выра-жаются через обычныеарифметические функции. Произвольная пара (x,у) находится на месте x+1 впоследовательности (2). Далее перед последователь-ностью (2) находятсяпоследовательности, отвечающие элементам (x1,y1) с условием x1+y1=t , гдеt=0,1,2,...,x+y-1 , и каждый из них содержит t+1 элемент.Следовательно, элемент (x,y) находится в после-довательности (1) на месте1+2+...+x+y+x+1 . Поскольку нумерация начитается с нуля , то номер элемента(x,y) в последовательности (1) равен( x + y )( x + y + 1)( x + y )2 + 3x + yc( x , y ) =+x =22Пусть теперь c(x,y)=n и найдем x = l ( n ) , y = r( n ) .(4)Из (4) следуют равенства:2 n = ( x + y )2 + 3x + y8n + 1 = ( 2 x + 2 y + 1)2 + 8x8n + 1 = ( 2 x + 2 y + 3 )2 − 8 y − 8Следовательноили2x + 2 y + 1 ≤[8n + 1 < 2 x + 2 y + 3]x + y + 1≤[8n + 1 + 1]2<x + y+237Это означает, чтоx + y + 1=[]8n + 1 + 1(5)2Теперь, используя (4), определяем x :1x = l (n) = n −& 2[]8n + 1 + 1 2 []8n + 1 −& 12(6)Подставляя найденное значение x в (5) получаем y :y = r ( n) = []8n + 1 + 1 1 + 2 2 []8n + 1 + 1 2 []8n + 1 −& 1 −& n −& 1 (7)2Заметим, что важен не сам вид полученных функций c( x , y ) , r( n ) , l ( n ) ,а важен факт их эффективной вы-числимости.Теперь с помощью нумерации пар чисел легко получить нумерацию троекчисел, т.е.

элементов множества N 03 . Определим функции :c 3 ( x , y, z ) = c( c( x , y ), z )Тогда ,если c 3 ( x , y, z ) = nтоz = r( n )y = r( l ( n ))x = l ( l ( n ))(8)(9)Аналогично, для наборов произвольной длины r+1 полагаемc1 ( x 1 ) = x 1 , c 2 ( x 1, x 2 ) = c( x 1, x 2 )(10)c r +1 ( x 1, x 2 ,..., x r +1 ) = c r ( c( x 1, x 2 ), x 3 ,..., x r +1 )и по определению называем число c n ( x 1, x 2 ,..., x n ) канторов- ским номеромn-kn ( x 1, x 2 ,..., x n )Если c n ( x 1, x 2 ,..., x n ) = m , тоx n = r( m )x n−1 = r( l ( m )).....(11)x 2 = r( l (...