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

l ( x )...))x 1 = l ( l (... l ( x )...))Теперь имея нумерацию множеств N 0k ( k ≥ 1) можно ус-тановитьнумерацию множестваM = N 0 U N 02 U .... U N 0k U ...Положим для любого n ∈ Nc( x 1, x 2 ,..., x n ) = c( c n ( x 1, x 2 ,..., x n ), n − 1)(12)38Ясно, что c - биективное соответствие между M и N0. Кроме того, еслис( x 1, x 2 ,..., x n ) = m , тоc n ( x 1, x 2 ,..., x n ) = l ( m )n = r( m ) + 1Отсюда, используя (11) эффективно определяются x 1, x 2 ,..., x n .2 0 ) Приведем еще одну нумерацию наборов чисел.

Номер пары (x,y)зададим функциейp( x, y) = 2 k (2 y + 1) −& 1(13)Ясно, что это общерекурсивная функция. При этом если р(x,y)=n , товыполненоx = exp 2 ( n + 1) n +1 y =  exp ( n+1)+1 2 2Следовательно, для данной нумерацииl ( n ) = exp 2 ( n + 1) n +1 r( n ) =  exp ( n+1)+1 2 2Теперь, имея нумерационную функцию для пар чисел, аналогичнопредыдущему строим нумерационные функции для -kn чисел и множестванаборов M = N 0 U N 02 U ... ·Другую нумерацию множества М мож но получить так:τ ( x 1,..., x k ) = 2 x1 + 2 x1+ x 2 +1 +...+2 x1 +...+ x k + k −1 − 1(14)−1Ясно , что τ -вычислима.

Чтобы установить вычис-лимость τ , заметим,что каждое натуральное число имеет единственное представление в двоичнойпозиционной записи. Т.е. для любого n можно эффек-тивно и однозначно найтиk ≥ 1 и 0 ≤ b1 < b2 <..., bk такое, что n + 1 = 2 b1 + 2 b2 +...+2 bk .Откудаполучаемτ −1( n ) = ( x1, x 2 ,..., x n ) ,где x1=b1 ,xi+1=bi+1-bi-1 (1 ≤ i ≤ k )30 ) Рассмотрим теперь вопрос о нумерации слов в некотором алфавите иукажем некоторые из применяемых способов такой нумерации.ПустьA = {a1,..., ar} - конечный алфавит и пусть A ∗ - множество всехслов конечной длины в алфавите A , включая и пустое слово λ .Алфавитная нумерация определяется следующим образом:c( λ ) = 039c( ai1 ,..., ais ) = is + is −1r +...+ i1r s −1(15)Поскольку при фиксированном r каждое положительное число n однозначнопредставимо в видеn = is + is −1r +...+ i1r s −1(1 ≤ i1 ≤ r )(16) , токаждое число есть алфавитный номер одного и только одного слова из∗множества A Разложение (16) называется r-ичным разложением числа n сцифрами1,...,r в отличии от обычного r-ичного разложения с коэффициентами 1,...,r.Нумерация слов через нумерационные Функции.

Пусть имеется счетныйA = {a0 , a1,... } . Тогда нумерация слов определяется так:ν(λ ) = 0(17)ν( ai1 ,...,ais ) = c( i1,..., is ) + 1 , s ≥ 1алфавитгде функция c( i1,..., is ) определена соотношениен (12). Ясно, что такопределенная функция ν является биек- тивной и вычислимой .A = {a0 , a1,... } .Определим геделевы номера для каждой буквы g ( ai ) = 2i + 3 , i ∈ N 0 .Теперь для каждого слова P = ai ai ... ai определим геделев номер0 1kГеделевская _нумерация. Пусть имеем счетный алфавитg( P ) = 2положимтак:g ( ai0 ) g ( ai1 )3g ( aik )... pk,где pk- k-ое простое число.

Кроме того ,g( λ ) = 1При этом геделев номер последовательности слов P0,P1,...,Pk определяется2g ( P0 ) g ( P1 )3.... pk g ( Pk )4 0 ) Рассмотрим теперь два применения нумерационных функций.а) Утверждение 1 Функция f ( x , y ) , отличная от нуля на конечном2множестве пар из N 0 общерекурсивна.Док-во.Действительно, пустьf ≠ 0 на парах чисел ( x1, y1 ) ,..., ( x t , yt ) и пустьимеет на них значения z1,...,zt .На остальных парах f ( x , y ) =0. Положимu1 = c( x1, y1 ) ,..., ut = c( x t , yt ) ,где С - нумерационная функция Кантора.Определи» функцию g так:g ( ui ) = zi , i = 1,..., tg( u ) = 0 на остальных u ∈N 0 .40Было выше показано,что g -общерекурсивна.

По построению выполненоf ( x , y ) = g( c( x , y )) и поэтому f общерекурсивна.б) Определим сначала понятие совместной рекурсии. В схеме совместнойрекурсий функция порождается с помощью нескольких функций.Пусть для определенности даны функцииg1( x )g2 ( x )h1( x , y, z, t )h2 ( x , y, z, t )здесь обозначено x = ( x 1, x 2 ,..., x n ) .Тогда можно определить пару функций f1( x , y ) и f 2 ( x , y ) по рекурсии:f1( x , y ) = g1( x )f 2 ( x , y ) = g2 ( x )f1( x , y + 1) = h1( x , y, f1( x , y ), f 2 ( x , y ))f 2 ( x , y + 1) = h2 ( x , y, f1( x , y ), f 2 ( x , y ))Утверждение2 Если g1, g2 , h1, h2 -общерекурсивные функции, то f1, f 2также общерекурсивны.Док-во.Определим функцию , u( x , y ) = c( f1( x , y ), f 2 ( x , y )) , гдеС- нумерационная функция Кантора.Тогда имеемf1( x , y ) = l ( u( x , y ))f 2 ( x , y ) = r( u( x , y ))Далее имеемu( x ,0 ) = c( f1( x ,0 ), f 2 ( x ,0 )) = c(( g1( x ), g2 ( x ))) -частично рекурсивная по условию.u( x , y + 1) = c( f1( x , y + 1), f 2 ( x , y + 1)) == c( h1( x , y, f1( x , y ), f 2 ( x , y )), h2 ( x , y, f1( x , y ), f 2 ( x , y )))функция u( x , y + 1) получается по схеме обычной рекурсии с помощьюфункцийg( x ) = c( g1( x ), g2 ( x ))h( x , y, z ) = c( h1( x , y, l ( z ), r( z )), h2 ( x , y, l ( z ), r( z )))Значит функция u( x , y ) частично рекурсивна, а потому частичнорекурсивны и функции f1( x , y) , f 2 ( x , y ) .41§ 6 Вычисление по Тьюрингучастично рекурсивных функцийВо введении отмечалось, что различные уточнения понятия алгоритмаопределяют один и тот же класс вычислимых функций.

Этот факт выше былустановлен для класса Ч - частично рекурсивных функций и класса Е-функций,вычислимых на машинах произвольного доступа. Теперь это будет установленодля класса Т - функций, вычислимых по Тьюрингу. В данном разделе будетустановлено, что справедливо включение Ч ⊆ Т , а в следующем разделе обратное включение Т ⊆ Ч .Утверждение.Всякая частично рекурсивная функция вычислима на подходящей машинеТьюринга.Док-во.Поскольку частично рекурсивные функции получаются из базисныхnфункций 0(x),s(x), I m( x1 ,..., x n ) с помощью применения конечного числа разопераций суперпозиции (S),рекурсии (R) и минимизации(M), то достаточнодоказать вычислимость по Тьюрингу базисных функций и указанных операций.а) Вычислимость базисных функций .Функция 0(ч) вычисляется тривиально. Начальная конфигурация q111..11(x+1раз) должна переводиться в конфигурацию q 0 1 .

Это делает машинаT: q11 → q1λRq1λ → q 0 1Eфункция S(x) также вычисляется тривиально. Начальная конфигурацияq111..11(x+1 раз) должна переводиться вконфигурацию q 0 11...11(x+2 раз).Это делает мажинаT: q11 → q11Lq1λ → q 0 1En( x1 ,..., x n ) начальная конфигурацияДля вычисления функции I mq111..11∗1...1∗ ... ∗1...1(x1+1,x2+1,...,xm+1 раз соответственно) должнапереводиться в конфигурацию q 0 11...11(xm+1 раз).Это может выполнитьмашина, которая стирает все знаки 1 , *,при этом "считает" до m и оставляет mую группу без изменения и снова стирает все знаки 1 , * . Ясно, что это можетвыполнить подходящая машина Тьюринга.б) Вычислимость операции суперпозиции.Пусть даны функции g( y1 ,..., y n ) и f1 ( x1 ,..., x m ) ,..., f n ( x1 ,..., x m )вычислимые по Тьюрингу, Нужно показать вычислимость функцииh( x1 ,..., x m ) = g( f1 ( x1 ,..., x m ),..., f n ( x1 ,..., xm ))Это можно реализовать в соответствии со схемой:42(слово из x+1 палочек обозначим x )x1∗ ...∗ xm → f1 ( x1 ,..., xm )∗ ...∗ fn ( x1 ,..., xm ) → g ( f1 ,..., fn ) (1)Пусть M1,...,Mn - машины, вычисляющие функции f1 ,..., f n соответственно.Тогда первый шаг в схеме (1) может быть выполнен машиной M 1 ∗ ...

∗ M n (вобозначениях раздела 2). Второй шаг в схеме (1) может быть выполнен машинойM g , вычислявшей функцию g . Следовательно, функция h вычисляетсякомпозицией M g o( M1 ∗ .. . ∗ M n )в) Вычислимость операции рекурсии.Ограничимся для простоты реализацией схемыf(0)=a(2)f(x+1)=g(x,f(x))Общий случай рассматривается аналогично.Вычисление f ( x ) осуществляется циклами.

Для цикла i ∈ [ 0, x ] на лентезаписано x1 ∗ x 2 ∗ x 3 = x − i∗ i ∗ f (i ) по условию f (i + 1) = g(i , f (i )) и в ходереализации цикла i+1 данное слово преобразуется в словоx1 −& 1∗ x2 + 1∗ g ( x2 , x3 ) , если x1>1. Если же x1=0 то выдается f ( x ) = x 3 .Чтобыреализовать эту процедуру,нужно иметь программы следующих машин (ихсуществование очевидно):- машина МЛ по слову x1 ∗ x 2 ∗ x 3 выдается символ И , если x1=0 , и символЛ в противном случае.- машина М0 оставляет всякое слово без изменения;-машина М1 по слову x1 ∗ x 2 ∗ x 3 выдает x1 −& 1 (нужно стереть ∗ x 2 ∗ x 3 и вслове x1 , стирает одну палочку);- машина M2 по слову x1 ∗ x 2 ∗ x 3 выдает x1 + 1 (нужно стереть x1 ∗ и ∗ x1и к слову x 2 приписать одну палочку);- машина М3 по слову x1 ∗ x 2 ∗ x 3 выдает x 3 (нужно стереть x1 ∗ x 2 ∗ );- машина М4 по слову x1 ∗ x 2 ∗ x 3 выдает g ( x 2 , x 3 ) (нужно стереть x1 ∗ ивычислить g ( x 2 , x 3 ) );- машина Мz , осуществляющая вход в цикл, которая по входу x выдаетx1 ∗ 0∗ a .

(нужно дописать постоянное слово ∗ 0∗ a ).Вычисление функции f ( x ) проходит в соответствии со схемой (вобозначениях раздела 2)x → x1∗0∗ a = x1∗ x2 ∗ x3 →σ ∗ x1∗ x2 ∗ x3MzMЛ ∗ M0M 3 ∨ ( M1∗ M 2 ∗ M 4 )σ =Лx −& 1∗ x2 ∗ g ( x2 , x3 ) ←σ =Иx343Г) Вычислимость операции минимизации.Ограничимся для простоты реализацией операции минимизации видаf ( x ) = µ y ( g ( x , y ) = 0)Общий случай разбирается аналогично.Вычисление f ( x ) осуществляется циклами. После цикла i на ленте записаноx ∗ i . В ходе цикла i+1 вычисляется g ( x , i ) и проверяется условие g ( x , i ) = 0 ?Если оно выполнено, то i выдается в качестве ответа.

Если оно не выполнено, тослово x ∗ i преобразуется в слово x ∗ i + 1 .Для реализации этой процедуры нужны программы сдедущих машин (ихсуществование очевидно):-машина МЛ по слову x1 ∗ x 2 ∗ x 3 выдает И ,если x1=0, и Л ,else;-машина М0 оставляет слово без изменения;-машина М1 по слову x1 ∗ x 2 находит g ( x1 , x 2 ) ;-машина М2 переводит слово x1 ∗ x 2 ∗ x 3 в слово x 2 ∗ x 3 ;-машина М3 по слову x ∗ i выдает i ;-машина М4 переводит слово x ∗ i в слово x ∗ i + 1 ;-машина МZ осуществляет вход и цикл.Слово x она преобразует в словоx∗0 .Схема вычисления f ( x ) осуществляется в соответствии со схемой (вобозначениях раздела 2).x → x∗0 = x∗ i → g ( x, i )∗ x∗ i → σ ∗ x∗ iMM ∗MzM1 ∗ M0Л2M 3 ∨ ( M1∗ M 2 ∗ M 4 )σ =Лx∗i + 1σ =ИiТем самым установлено, что частично рекурсивные функции вычислимыпо Тьюрингу и, следовательно, имеет место включение Ч ⊆ Т.44§ 7.Арифметизация машин Тьюринга и частичнаярекурсивность функций, вычислимых по ТьюрингуВ данном разделе будет доказано, что всякая Функция, вычислимая поТьюрингу, является частично рекурсивной.

Это будет сделано на основе приема,распространенного в теории алгоритмов и называемого арифметизацией..Данный прием заключается в том, что нечисловые объекты -в данномслучае слова в конечном алфавите-кодируются натуральными числами, апреобразование этих объектов заменяются арифметическими операциями надих номерами.Рассмотрим машину Тьюринга Т. Пусть A = {a 0 , a1 , a 2 ,..., a k −1} - еевнешний алфавит, причем считаем a 0 =Л , a1 =И , т.к.