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

рассматриваем унарныепредставления чисел. Пусть Q = {q0 , q1 , q2 ,... , a r−1} внутренний алфавит,причем q 0 , q1 - являются заключительным и начальным состояниями.Кодирование алфавитов.ai ↔ i ∈ 0, k − 1q j ↔ j ∈ 0, r − 1(1)Поскольку кодирование алфавитов числами проведено, то впредь не будемразличать буквы и соответствувщие числа.Кодирование Конфигураций:Пусть дана конфигурация машины…b2 b1 b0 aic0c1c2…(2)qjТогда закодируем ее четверкой чисел j , a , m, n ,гдеj ↔ qja ↔ aim=n=∞∑ bi k i(3)i=0∞∑ ci k ii=0Поскольку рассматриваются конечные конфигурации, то суммы в (3) содержатконечное число слагаемых, отличных от нуля.

Далее, в силу того, что всякоенатуральное число однозначно представляется k-ичной записью, то даннаячетверка чисел однозначно определяет конфигурацию машины.Преобразование четверок при выполнении команд.45Пусть выполняется команда q j ai → q j ′ ai ′ R . Тогда конфигурация (2)перейдет в кснфигурацию…b2 b1b0 ai′ c0c1c2 …q j′Данная конфигурация характеризуется четверкой чисел j ′ , a ′, m′, n ′ ,гдеa ′ = c0 = res(n, k )m ′ = ai ′ + bk +... = ai ′ + mk(4)nn′ =  k Если выполняется команда q j ai → q j ′ ai ′ L , то конфигурация(2) перейдет вконфигурацию… b2 b1 b0ai′c0c1c2 …q j′Данная конфигурация характеризуется четверкой чисел j ′ , a ′ , m ′, n ′ ,гдеa ′ = b0 = res(m, k )mm′ =  (5)k n ′ = ai ′ + nkЕсли выполняется команда q j ai → q j ′ ai ′ E , то для новой четверкиj ′, a ′, m ′, n ′ выполненоa ′ = ai ′m′ = mn′ = n(6)Определим теперь числовые функции S ( j , a j ) , Q ( j , a j ) , A( j , a j ) , которыеопределяют сдвиг головки, новое состояние и новую букву на ленте.

Дляпроизвольной команды q j ai → q j ′ ai ′ Sположим 0 , если S = R j ∈ {1, ..., r − 1}S( j , a j ) = 1 , если S = L ai ∈ {1,..., k − 1}2 , если S = Eна остальных парах положим S ( j , a j ) =0.46Аналогично j ′ , если j ∈ {1,..., r − 1} ai ∈ {1,..., k − 1}Q( j , a j ) = 0 , в остальных слу ÷ аях(8), если j ∈ {1,..., r − 1} ai ∈ {1,..., k − 1}0 , в остальных слу ÷ аях(9)aA( j , a j ) =  i ′По доказанному выше функции S,Q,A -общерекурсивны ,т.к. они отличныот нуля на конечном числе пар чисел.Используя данные функции, преобразование четверок чисел можно записать ввидеj ′ = Q( j , a )(10)a ′ = res( n, k ) sgS ( j , a ) + res( m, k ) sg S ( j , a ) − 1 + A( j , a ) sg S ( j , a ) − 2 mm′ = ( mk + A( j , a )) sgS ( j , a ) +   sg S ( j , a ) − 1 + msg S ( j , a ) − 2knn ′ =   sgS ( j , a ) + ( nk + A( j , a )) sg S ( j , a ) − 1 + nsg S ( j , a ) − 2k Подчеркнем, что полученные функции j ′, a ′ , m′ , n ′ являютсяобщерекурсивными т.к.

они суть суперпозиции общерекурсивных функций.Определим теперь следующие функцииQ ( t , j , a, m, n ) -номер состояни, в которое переходитмашина из начальной конфигурациис четверкой j ′, a ′ , m′ , n ′ через t тактов.~A(t , j , a , m, n) - номер считываемой буквы на лентечерез t тактов.~M ( t , j , a , m, n) -значение m через t тактов.~N (t , j , a , m, n) -значение n через t тактов.Ясно, что при t=0 имеемQ( 0, j , a , m, n) = j~A( 0, j , a , m, n) = a~M ( 0, j , a , m, n) = m~N ( 0, j , a , m, n) = n(11)При переходе от t к t+1 справедливы соотношения~~~Q(t + 1, j , a , m, n) = Q(Q (t , j , a , m, n), A(t , j , a , m, n))~~~~A(t + 1, j , a , m, n) = a ′(Q ′(t , j , a , m, n),.

A(t , j , a , m, n), M (t , j , a , m, n), N (t , j , a , m, n)47~~~~M (t + 1, j , a , m, n) = m ′(Q ′(t , j , a , m, n), A(t , j , a , m, n), M (t , j , a , m, n), N (t , j , a , m, n))~~~~N (t + 1, j , a , m, n) = n ′(Q ′(t , j , a , m, n), . A(t , j , a , m, n), M (t , j , a , m, n), N (t , j , a , m, n))( это соотношение 12)Соотношения (11) и(12) определяют по схеме совместной рекурсии~ ~ ~ ~~функции Q , A, M , N . Поскольку функции Q , a ′ , m ′ , n ′ общерекурсивны, то~ ~ ~ ~такими будут и функции Q , A, M , N .Частичная рекурсия функций , вычислимых на машине Тьюринга.Ограничимся рассмотрением функций одного артумента. Пусть функцияf ( x ) вычислима на машине Тьюринга Т.

Произведем арифметизацию данноймашины.Начальная конфигурация q11x +1 характеризуется четверкой 11, ,0, n ( x ) ,где2n( x) = 1 + k + k +...+ kx− 1k x − 1  k x −& 1==k − 1  k −& 1 (13)Элементы четверки через t тактов определяются соотношениями:~q ( t , x ) = Q ( t ,11, ,0, n ( x ))~a ( t , x ) = A ( t ,11, ,0, n ( x ))~m( t , x ) = M ( t ,11, ,0, n ( x ))~n ( t , x ) = N ( t ,11, ,0, n ( x ))(14)Заметим, что в (13) и (14) мы имеем общерекурсивные фуннкции.По определению , если f ( x ) определено, то машина Т останавливается вмомент t0 ,когда выполненоq ( t , x ) = 0 ,т.е.можно написатьt 0 ( x ) = µ t ( q ( t , x ) = 0)(15)Если f ( x ) не определено, то q ( t , x ) ≠ 0 ∀x и тогда значение t0 в (15) неопределено. Заметим, что функция t0(x) частично рекурсивна, посколькуполучена из общерекурсивной применением операции минимизации.

Еслиизвестно значение t0(x) , то можно определитьвсе элементы четверкиq 0 ( x ) = q ( t 0 ( x ), x )a 0 ( x ) = a ( t 0 ( x ), x )m0 ( x ) = m( t 0 ( x ), x )n 0 ( x ) = n ( t 0 ( x ), x )(16)которые являются частично рекурсивными функциями.Если значение f ( x ) определено, то заключительная конфигурация имеетвид q 0 1 f ( x )+1 .Она характеризуется четверкой 0,1,0, n 0 ( x )482n0 ( x) = 1 + k + k +...+ kf ( x) −1Таким образом можно написать k f ( x) −& 1= k −& 1 (17) k s −& 1f ( x) = µ s  n0 ( x) − (18) = 01k−&Если значение f ( x ) не определено, то не определено и значение t0(x) исоответственно n 0 ( x ) = n ( t 0 ( x ), x ) и тогда формула (18) дает неопределенноезначение.

Из соотношения (18) следует, что функция f ( x ) является частичнорекурсивной.Результат данного раздела служит серьезным доводом в пользу тезисовТьюринга и Черча, поэтому доказательства с использованием данных тезисовсчитаются достаточно строгими и обоснованными.49§ 8 Нормальные алгоритмы10 ) .

В данном разделе дается представление об одном подходе к уточнениюпонятия алгоритма, предложенном А. А.Марковым и называемом нормальныеалгоритмы (в авторской транскрипции - алгорифмы). Данный подход связываетнеформальное понятие эффективности с переработкой слов в некоторомконечном алфавите в соответствии с определенными правилами. В качествеэлементарного преобразования используется подстановка одного слова вместодругого. Множество таких подстановок определяет схему алгоритма.

Правила,определяющие порядок применения подстановок, а также правила остановаявляются общими для всех нормальных алгоритмов. Дадим формальныеопределения. Пусть A = {a1 ,..., an } - алфавит. Если Р,Q - слова в алфавите А(возможно пустые), то выражения P → Q , P → (⋅)Q называются Формуламиподстановки в алфавите А (предполагается, что знаки → , ⋅ , не входят валфавит А ). При этом формула P → Q называется простой, а формула P → ⋅ Qзаключительной .Обозначим P → (⋅)Q любую из этих формул. Произвольнаяконечная последовательность таких формул называется схемой S a нормальногоалгоритма a . Значит схема нормального алгоритма имеет вид:P1 → (⋅)Q1P2 → (⋅) Q2Sa: .

. .Pm → (⋅)Qm(1)Схема S a определяет следующий алгоритм a , перерабатывающий словав алфавите А (т,е, вычисляющий словарную функцию на словах в алфавите А ).Говорим, что слово Р входит в слово W , если существуют слова V1 и V2(возможно, пустые)) такие, что(2)W=V1PV2Если слово V1 имеет наименьшую длину из всех слов вида (2), то говорят опервом вхождении P в слово W.Пусть дано произвольное слово K в алфавите A. Возможны следующиеслучаи:1) Ни одно из слов P1,...,Рm не входит в слово K.В этом случае говорим, что схема S a неприменима к K1 и пишем S a :K .2) Среди слов P1,...,Рm существует Рi , входящее в K.Пусть t-минимальное число, такое, что Рt входит в K , и пусть K=V1PtV2,где V1 имеет минимальную длину (т.е.

берется первое вхождение Рt в K.)Тогда определим слово W=V1QtV2В этом случае говорим, что схема S a применима к K и пишемSa : K ⇒ WSa : K ⇒ ⋅ W(3)в зависимости от того, применялась простая формула или заключительнаясоответственно.50Теперь пишем Sa : K ⇒ W ,если существует конечная последовательностьслов W0 , W1 ,..., Wk в алфавите A такая, что K = W0 , W = Wk и выполненоW0 ⇒ W1 , W2 ⇒ W3 ,..., Wk −1 ⇒ ⋅ Wk(4)либо Wk −1 ⇒ WkВ первом случае пишем также Sa : K ⇒ ⋅ W .Говорим, что нормальный алгоритм a со схемой S a вычисляет словарнуюфункцию Fs : A∗ → A∗ , где A∗ -множество слов в алфавите А, если для любых ливо Sa : P ⇒ Q и Sa : Qливо Sa : P ⇒ ⋅ Qслов P, Q ∈ A∗ имеем Fs (P) = Q ⇔ Работа нормального алгоритма может быть описана так.

Если дано слово Р, то находим в схеме алгоритма S a первую формулу P → (⋅) Qt , такую, что Рtвходит в P, и производим замену первого вхождения Pt словом Qt .Пусть W1результат этой подстановки. Если применяемая формула P → ⋅ Qt заключительная, то работа алгоритма заканчивается и слово W1 есть результатработы алгоритма. Если применяемая формула P → Qt простая, то, к слову W1применяем описанную процедуру. Если на некотором шаге получено слово Wi ,к которому неприменима схема алгоритма S a (т.е. ни одно из Pj , j ∈1, m невходит в Wi ,то работа алгоритма заканчивается, и Wi есть результат работыалгоритма.

Если описанный процесс не заканчивается то, по определению,алгоритм неприменим к слову Р.Словарная функция f в алфавите A (т.е. типа f : A∗ → A∗ ) называетсявычислимой по Маркову, если существует схема нормального алгоритма S a валфавите B ⊇ A , вычисляющая f , т.е. f = Fs . Класс функций, вычислимыхпо Маркову, обозначим M. Рассмотрим несколько примеров.1) A = {a1 , a2 }Схема Sa :a1 → ⋅ λa2 → a2Данный алгоритм оставляет пустое слово λ без изменения и всякое словоР в алфавите А переводит в слово Q , полученное из Р путем вычеркиванияпервого вхождения буквы a1 . Алгоритм a неприменим к словам, несодержащим вхождений буквы a1 .2) A = {a1 , a2 ,..., an }Схема Saa1 → λa →λ: 2...an → λДанный алгоритм переводит всякое слово P в алфавите А в пустое слово.513) A = {}Схема Sa :λ → ⋅x678Данный алгоритм переводит всякое слово P = ... в слово Q = ... .123x+1Если представить натуральное числоn словом n +1 , то данный алгоритм вычисляет функцию f(n)=n+1.4) A = {a1 , a2 ,..., an }Схема Sa :λ → ⋅ λ .Данный алгоритм вычисляет функцию Fs ( P ) = P , ∀P .Если же взятьсхему Sa :λ → λ, то данный алгоритм вычисляет нигде не определенную функцию.5) A = {a1 , a2 ,..., an } .Если P = ai1 ...

ai k ,то обращением слова P назовем словоP −1 = ai k ... ai1 .Рассмотрим алфавит B = A U{α , β } и соответственно схему S a ( α , β новые буквы).1. αα → β2. βα → αβ , ∀a ∈ A3. βα → β4. β → ⋅ λ5. α ab → bα a , ∀a , b ∈ A6. λ → αПокажем, что данный алгоритм a осуществляет обращение слов валфавите A.Док-во.Пусть P = a j0 ... a j k слово в алфавите А. ТогдаP (→ αP (→ a j1 α a j0 ... a j k (→ a j1 a j2 α a j0 a j3 ... a j k →п о 6)п о5)п о5)( п о5)→ a j1 a j2 ...