В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций) (1159492), страница 9
Текст из файла (страница 9)
a j k α a j0 (→ α a j1 a j2 ... a j k α a j0 →... → a j2 a j3 ... a j k α a j1 α a j0п о6)Теперь, повторяя этот процесс,получим :⇒ α a j k α a j k −1 ... α a j1 α a j0 (→ α α a j k α a j k −1 ... α a j1 α a j0 →п о 6)( п о 4)⇒ β a j k α a j k −1 ... α a j1 α a j0 (→ a j k β α a j k −1 ... α a j1 α a j0 →п о 2)( п о 3)⇒ a j k β a j k −1 ... α a j1 α a j0 ⇒...( п о 2,3,4)...
⇒ a j k a j k −1 ... a j020 ) Для нормальных алгоритмов разработана техника програмирования,позволяющая осуществлять операции композиции алгоритмов, реализовыватьоператоры "если Ф , то выполнить F1 , иначе F2 ", "пока Ф выполнить F1 , иначеF2 ”.Следовательно, класс функций М достаточно широк. Много конкретных52нормальных алгоритмов и соответствующая техника программированияпредставлены в книге [8].В связи с этим Марковым А.А.был выдвинут принципнормализации, который заключается в том, что все алгоритмы исчерпываютсянормальными алгоритмами или, что то же самое - всякий алгоритм нормализуем.Принятие данного принципа позволяет истолковывать утверждения онесуществовании нормальных алгоритмов для решения конкретных задач какутверждения о несуществовании алгоритмов вообще.
Данный принципэквивалентен тезисам Черча и Тьюринга поскольку справедливаТеоремаКласс функций М вычислимых по Маркову, совпадает с классом функцийТ , вычислимых по Тьюрингу, и, следовательно, с классом частичнорекурсивных функций Ч и с классом МПД-вычислимых функций Е .Доказательство совпадения классов M и Ч проводится по той же схеме,что и приведенное выше доказательство совпадения классов Т и Ч. Полностьюоно приведено в книге [19], гл. 5.53§ 9 Нумерация алгоритмовВ данном разделе будут приведены эффективные кодированиянатуральными числами множества всех алгоритмов для каждой израссматриваемых моделей алгоритмов: машин Тьюринга , МПД-программ,частично рекурсивных функций.
Данные результаты относятся к числуфундаментальных, т.к. они используются для получения многих важных фактов,в частности, для установления невычислимости ряда конкретных функций.1°) Нумерация машин Тьюринга.Зафиксируем счетные множества символов {a0 , a1 ,..., ai ,...} {q0 , q1 ,..., q j ,...} ибудем считать, что внешние алфавиты и алфавиты внутренних состояний всехмашин Тьюринга берутся из этих множеств.
При этом будем считать, что a0принадлежит всем внешним алфавитам машин и интерпретируется как пустойсимвол, а буквы q0 и q1 принадлежат всем внутреним алфавитам машин и всегдаозначают заключительное и начальное состояния соответственно. Опишемтеперь единый способ представления информации о машинах с помощьюкодирования. Каждому символу из множества{ L, R , E , a0 , a1 ,..., ai ,... q0 , q1 ,..., q j ,...} поставим в соответствие двоичныйнабор согласно таблице:СимволCимволысдвигаRLEСимволыалфавиталентыa0a1.aiКод10100100010000100000…100...00…Число нулейв коде12346…2i+4….1000005Символыq0q1100000007алфавита………состоянийqi1000…0002i+5………Таблица кодирования символов машин.Далее , команде I машины Тьюринга Т, имеющей вид qa → q ′a ′d ,ставится в соответствие двоичный набор видаКод ( I ) = Код (q) Код (a) Код (q ′) Код (a ′) Код (d ) (1)в котором коды букв приписаны друг к другу.
Пусть машина Т имеет алфавитыA = {a0 , a1 ,..., am } Q = {q0 , q1 ,..., qn } .Упорядочим команды машины Т в соответствии с лексикографическимпорядком левых частей команд: q1a0 , q1a1 , q1am , q2 a0 ,…, q2 am ,…, qn a0 ,…, qn am .54Пусть I1 ,..., I n ( m +1) - соответствующая последовательность команд. Тогдамашине Т поставим в соответствие двоичный набор видаКод (T) = Код ( I1 ) Код ( I2 )... Код ( In ( m+1) )(2)полученный приписыванием друг н другу кодов команд. Пример: Пусть данамашина Тьюринга Т :A = {a0 , a1} , Q = {q0 , q1}T: q1a0 → q0a0 E (3)q1a1 → q0a1 EТогда имеемКод (T) = 107104105104103107106105106103xЛегко видеть, что машина Т переводит конфигурации q1a1 вxn +1конфигурации q0a1 и поэтому, представляя натуральное число n как a1 ,лолучаем, что машина Т вычисляет функцию f ( x ) = xЯсно, что указанное кодирование является алгоритмической процедурой.Имея код машины, однозначно восстанавливается множество ее команд - дляэтого надо выделить подслова, начинающиеся с единицы с нулями доследующей единицы.
Пятерка таких подслов образует команду. Далее, легковидеть, что имеется алгоритмическая процедура, позволяющая попроизвольному слову из 0,1 выяснять - будет ли это слово служить кодомнекоторой машины Тьюринга. Будем теперь рассматривать код машиныТьюринга как двоичную запись натурального числа. Данное число назовемномером машины Тьюринга.
Поскольку все коды начинаются с единицы , торазным кодам соответствуют разные числа.Упорядочим машины Тьюринга повозрастанию чисел , представляемых их кодами , и занумеруем их T0,T1,…,Tn,… .(4)Указанное упорядочение является эффективным в том смысле , чтосуществует алгоритм ,который по n выдаеткод(Тn) и существует алгоритм , который , наоборот ,по код(Тn) выдает nT .Если обозначить через f n ( x ) -одноместную функцию , которую вычисляетмашина Тьюринга Тn ,то в результате получим нумерацию всех одноместныхчастично рекурсивных функций:f 0 ( x ) , f 1 ( x ) ,…, f n ( x ) ,…(5)Cогластно доказанному ,каждая одноместная частично рекурсивнаяфункция представлена в этой последовательности.Можно доказать ,что каждаятакая функция представлена в последовательности (5) бесконечное число раз.Аналогично можно определить нумерацию n-местных функций.2 0 ) Нумерация МПД-программ.Приведем аналогичную конструкцию по нумерации МПД-программ ,которая позволит получить нумерацию МПД-вычислимых функций.Сначалаопределим нумерацию команд.Положимα ( Z (n)) = 4(n − 1)55α ( S (n)) = 4(n − 1) − 1α (T (m, n)) = 4 p(m − 1, n − 1) + 2α ( J ( m, n, q )) = 4π (m, n, q ) + 3Здесь p( x , y ) = 2 x (2 y + 1) − 1π ( x , y , z) = p( p( x − 1, y − 1), z − 1)(6)(7)Ясно , что функция α эффективно вычислима.Для вычисления α −1 ( x )действуем так:Находим числа u,v ,такие ,что x=4u+v где 0 ≤ v < 4 .Тогда имеем :α −1 ( x ) = Z (u + 1) ,если v=0α −1 ( x ) = S (u + 1) ,если v=1α −1 ( x ) = T (l (u) + 1, r (u) + 1) ,если v=2α −1 ( x ) = J (m, n, q ) , если v=3 где (m, n, q ) = π −1 (u)Следовательно , функция α −1 также эффективно вычислима.Пусть теперь дана МПД-программа P = I1...
I s .Определим её номерγ ( P) = τ (α ( I1 ),..., α ( I s )) ,гдеτ ( x1 ,..., xs ) = 2 x1 + 2 x1 + x 2 +1 + 2 x1 + x 2 + x 3 + 2 + 2 x1 +...+ x s + s −1 − 1 (8)Ясно , что тем самым определена биекция γ множества программ вмножество натуральных чисел , причём функции γ и γ −1 эффективновычислимы ,по программе P эффективно находится её номер n = γ ( P ) ,а пономеру n можно эффективно найти программу P , такую что n = γ ( P ) .Числоγ ( P ) называется номером программы Р.Например , если P = I1 I 2 I 3 ,гдеI1=T(3,1),I2=S(4),I3=Z(6),то α (T (1,3)) = 18, α ( S (4)) = 13, α ( Z (6)) = 20Следовательно, γ ( P ) = 218 + 2 32 + 253 − 1Пусть теперь дано n=4127.
Поскольку 4127 = 25 + 212 − 1 ,то P = I1 I 2 ,гдеα ( I 2 ) = 12 − 5 − 1 = 6 .Следовательно , I1=S(2),I2=T(2,1).Разумеется , существуют и другие способы нумерации программ , для насважна лишь эффективная вычислимость функций γ и γ −1 .56Таким образом получаем эффективную нумерацию МПД(9)программ: P0 , P1 , P2 ,..., Pn ,...Теперь, имея нумерацию МПД-программ,можно занумеровать МПДвычислимые функции. Для любого a ∈ N и n ≥ 1 определимf a( n ) ≡ n-местная функция,вычисляемаяпрограммой с номером a .Это дает нумерацию n-местных МПД-вычислимых функцийf 0( n ) , f1( n ) , f 2( n ) ,…(10)(1)( x ) = 1 , n=1Например, если a =4127,то согласноопределению имеем f 4127(n)f 4127( x1 ,...
xn ) = x2 + 1 , n > 1.Поскольку для всякой частично рекурсивной функции fвычисляющая её МПД-программа Р, то f(n)(n)существует= f a( n ) ,где a = γ ( P ) .Число aназывают номером(индексом) функции f ( n ) .Приведём одно применение существования нумерации частичнорекурсивных функций.Теорема.Существуют всюду определенная функция, не являющаяся частичнорекурсивной.Док-во.построим всюду определенную функцию ϕ , отличающуюся от каждойчастично рекурсивной функции f 0 , f 1 ,..., f n ,... в перечеслении одноместныхчастачно рекурсивных функций.Полагаем f x ( x) + 1 , если f x ( x) оп ределенаϕ( x) = 0,elseФункция ϕ всюду определена и отличается от f n при x=n,n ∈ N 0 .Действительно , если f n (n) определено ,то ϕ (n) = f n (n) + 1 , еслиf n (n) не определено , то ϕ (n) определено и равно 0.Поскольку ϕ отличается отf n при всех n ∈ N 0 ,то ϕ не может находиться в перечислении (10) и , значит ,она не может быть частично рекурсивной.ч.т.д.Замечание.
Приведенный метод рассуждения есть пример диагональнойконструкции Кантора, с помощью которой им была доназана несчетностьмножества действительных чисел. Данным методом можно установитьнерекурсивность большого класса функций.Например, функция57 f x ( x) + 2 x , если f x ( x) оп ределеноg ( x) = p( x) , если f x ( x) не оп ределенопричем p(x) - целочисленный полином является всюду определенной и нечастично рекурсивной.3°) Универсальные функции.Пусть F - некоторый класс функций от k переменных.
ФункциюU (n, x1 ,..., x k ) от k+1 переменных называют универсальной для класса F , есливыполнимы условия:а) Для всякого n ∈ N 0 f n ( x1 ,..., xk ) = U (n, x1 ,..., x k ) ∈ Fб) Для всякой f ( x1 ,..., x k ) ∈ F существует n ∈ N такое, чтоf ( x1 ,..., x k ) = U ( n, x1 ,..., xn ) .Теорема 2.Для класса ×1 - одноместных частично рекурсивных функций существуетуниверсальная частично рекурсивная функция U(n,x).Док-во.Определим U (n, x ) = f Pn ( x ) ,точнее y , если Pn ( x) ↓ yU (n, x) = не оп ределено , else(11)Данное соотношение определяет частичную функцию. Функция U(n,x)является частично рекурсивной. Действительно, для произвольных (n,x) нужнонайти программу Рn(эффективная процедура)и применить Рn к начальнойконфигурации (x,0,0,…,0,…).
Если Pn ( x ) ↓ , то положить U(n,x)=r1, где r1содержимое регистра R1 в заключительной конфигурации. Если Pn ( x ) ↑ , тосчитать значение U(n,x) неопределенным. По тезису Черча функция U(n,x)частично рекурсивна. Покажем, что функция U(n,x) универсальна. ПосколькуU(n,x) частично рекурсивна,то и fn=U(n,x) для всякого n ∈ N 0 частичнорекурсивна, т.к. -fn получена подстановкой константы вместо первого аргумента.Пусть тепарь f ( x ) - произвольная одноместная частично рекурсивная функция.Тогда по доказанному она может быть вычислена некоторой МИД-программойР.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
