markov_teorija_algorifmov (522344), страница 62
Текст из файла (страница 62)
пе е абатывает С другой стороны, если алгорифм о перера атывает й всяк ю й(-членную систему слов, к которой он применим, в слово в , то для л о" А, юб й такой системы Я имеет место условное равенство ЕБ, А ОЕ)(Я) =5(В). ПЕрЕВЕдЕМ тЕПЕрЬ аЛГОрнфМ ($Б А оЗ) В аЛфаВИт А+» взяв яв в качестве,.базового" алфавита, т.
е, алфавита, кото- рый при переводе не затрагивается, алф у. у рующий „приведен нный" алгорифм мы обозначим символом и, п именить О ную процедуру можно, в частности, пр писан авите А+. П н этом и к к нормальным алгорифмам 6 в)алфавите . р всякий алгорифм л) при любом У уд Р ) 1 б ет вычислимой ве бальной функцией л( переменных и, если алгорифм темы 5 слов в А будет выполняться условное равенство так что среди „приведенных" функций вида х)' будут иметься (с точностью до эквивалентности) все вычислимые вербаль- ные ф функции любого числа переменных.
3. В дальнейшем будет удобен следующий спо ф " способ икса- ции значений первого аргумента функции рассматриваемого нами типа. П Р вЂ” какое-либо слово в А. Рассмотрим в у р- А но- усть — ка мальиый алгорифм фр со с хемой Ру. ~гл. нп 4 55! ТЕОРЕМА О НЕПОДВИЖНОЙ ТОЧКЕ 333 з В (61»79) =3» (14). 334 ВЫЧИС Ч СЛИМЫЕ ВЕРВАЛЬНЫЕ а»НКЦИИ Всякое слово 9 в алфавите А э вает в Р () у этот алгорифм перерабатыякую й»-членную систему слово у и, значит всяк — в ( + )-членную систему РУБ. Пусть теперь 2» — какой-либо н нормальныи алгорифм иад р р ьную композицию (2(о$ ) ифм иад алфавитом Ау такой, что для любог слова !е (е»о»гр) ((2) Я (»о 12) базово о- ° Ьр) в алфавит А+ так, чтобы роль Приведем алгорнфм (й»о,х» в ового" алфавита играл алфавит А . Пол ч б а ы ьный алгорифм мы, следуя Г.
С. Цейт и ну [31, будем обозначать символом 52»р. Если 61 — вычис менной, то ля — числимая вербальная функция )У+! д я любой »У-членной системы 5 + пере- (!) 2» (3) — Р»(РУЗ) Значит, всяк ю А~- и м 52» у -членную систему слов, к кот р " торов алгор фм р применим, он перерабатывает в некото ое тому р р дставляет собои вычислимую слова эта ф льную ункцию А5 пе емен р . нных. В понятном смысле а эта функция получается из ф нкции 1»» фу ии 1 ~ут~м фи~ы(Яо т 4. Проанализировав способ б построения схемы алгорифма о)тр) !3 37.11, а затем и 52» )во 4!.6», ч , что может ыть пост оен но . и ма = в + и для любого слова Р в А б дет им место графическое равенство (1) й! (Н»» Р) 521» Легко сооб а р зить, что с использованием п о е процедуры, укавычислнмой вербальной ф нкции лго и и может быть за ан д даже в виде линой ужы~ двух переменных в алфа- 5.
Замечание. Н Наличие нормального алгорифма Я', реализующего конструкцию 52»р, азумеет ляет собой ~ым - бо о-ли исключения. Аналоги ные) алг р фмы мог б смотренных нами сочетаний но мал ут ыть построены и ля ф ф компонируемых алгоет ыть построен нормальный алгорифм, пере- рабатывающий пару записей любых двух нормальных алгорифмов 6! и В в запись их нормальной композиции (Во52»), при фиксации алфавитов объединяемых алгорифмов может быть построен нормальный алгорифм, перерабатывающий пару записей нормальных алгорнфмов 52» и В в запись их нормального объединения (5 В), и т. д. Существование таких алгорифмов подсказывается принципом нормализации, и схемы их действительно могут быть осуществлены.
При надлежащей регламентации понятия «буквы» («буквами» можно, например, согласиться считать слова вида аЫа, » ) О) можно построить и нормальный алгорифм, который всякое натуральное »т' будет перерабатывать в запись универсального для А»-буквенного алфавита нормального алгорифма. Фактическое построение таких алгорифмов представляло бы собой известное усиление теорем, доказанных нами в гл. 1»' и т'. й 55.
Теорема о неподвижной точке В этом параграфе мы изложим один нз самых замечательных результатов общей теории алгорифмов — теорему Клини о неподвижной точке. Несмотря на относительную простоту доказательства, теорема эта вскрывает весьма неожиданный факт и имеет многочисленные и важные применения. К сожалению, в данной монографии мы не сможем в достаточной мере коснуться их за недостатком места (тем не менее см. теорему 3 56.1.1). 1. Пусть й и  — вычислимые вербальные функции одной и двух переменных соответственно. Мы будем говорить, что В вычисляет 61, если для любого 52 в А имеет место условное равенство Рассмотрев под углом зрения сказанного в предыдущем параграфе формулировку видоизмененной теоремы об универсальном алгорифме !3 45,5,11, мы без труда увидим, что 1.1.
Может быть посв»роена вычислимая вербальная функция двух переменных Я, вычисляюи»ая любую вычислимую вербальную функцию одной переменной. Построение такой „универсальной" функции, как мы в свое время убедились, требует определенных усилий. Замечатель. ным образом оказывается также (ср. К л и н и !51, с. 3)4, теорема ХХ»'11), что $ зм ТЕОРЕМА О НЕПОДВИЖНОЙ ТОЧКЕ 336 6 (Ру Я) = 2В (9 (Р) Я). Но Согласно теореме бальная функция бого Р в А и, значит, 6(Р) ю6(6УР). Но )В (6з,Р) Я (9 (6з)ТР) - <9 (6') > (Р), и потому 6(Р) -<9(6з)>(Р) ВЫЧИСЛИМЫЕ ВЕРБАЛЬНЫЕ ФУНКЦИИ [ГЛ. РН 1.2. Всякая вычислимая вербальная функция двух переменных вычисляет некоторую вычислимую вербальную функцию одной переменной. В самом деле, пусть 2) †произвольн вычислимая вербальная функция двух переменных.
Используя вычислимую вербальную функцию зс из 2 54,4, а также отсекающие нормальные алгорифмы ЗАт,т и 9А 12 29.41 и применяя теоремы объединения и композиции, построим вычислимую вербальную функцию двух переменных 6 такую, что для любых слов Р и Я в алфавите А имеет место условное равенство 6(РТЯ) =9Ф(РТР) у® Тогда, в частности, для любого 11 в А 6 (6зу(зз) и) (оз (6зубз) Я) =6(6я уе) 13 б4 4(1)1. 6(6'Те=6 '(а Ц б4.З(1)1 6ч'Я) = 6 (6чз ТЯ) ° Таким образом, 6 действительно вычисляет вычислимую ВЕрбаЛЬНуЮ фуНКцИЮ ОдНОй ПЕрЕМЕННОй (4зз.
ТЕОрЕМа доказана. Заметим, что фУнкциЯ 6чз эффективно стРоитсЯ по 2), и мы смогли бы даже построить нормальный алгорифм, перерабатывающий запись любой такой функции В в запись соответствующей функции 1з аз, так что доказательство теоремы 1.2 вполне конструктивно. 2. Мы будем говорить, что нормальный алгорифм 9 в алфавите А+ является вычислимым оператором над вычислимыми вербальными функциями одной переменной, если: 1) 9 является вычислимой вербальной функцией одной переменной и 2) запись всякой вычислимой вербальной функции одной переменной 9 перерабатывает в запись некоторой другой функции того же самого типа. Если слово Р в алфавите А, является записью некоторого нормального алгорифма в А+, то символом <Р> мы будем обозначать тот самый нормальный алгорифм в А+, записью которого является Р.
Имеет место следующая теорема „о неподвижной точке": 2.1. Каков бы ни был вычислимый оператор 9 над вычислимыми вербальными функциями одной переменной, может быть указана такая вычислимая вербальна функция 6 одной переменной, что для любого слова Р в алфавите А имеет место условное равенство 6(Р) =<6(6')>(~ ).
В самом деле, пусть 9 — произвольный вычислимый оператор над вычислимыми вербальными функциями одной переменной. Пусть 2 — „универсальная функция", существование которой утверждается в 1.1. Аналогично тому, как зто делалось в доказательстве теоремы 1,2, построим вычислимую вербальную функцию двух переменных 2) такую, что для любых Р и Я в А будет выполняться условное равенство 1.2 может быть указана вычислимая веродной переменной 6 такая, что для лю- что и требовалось доказать. Таким образом, всякий вычислимый оператор над вычисли- мыми функциями одной переменной имеет неподвижную точку. 3.
3 а м е ч а н и я. 1 . Читатель без труда сформулирует и докажет соответствующие утверждения для случая функций )з' переменных. 2 . Неподвижная точка оператора 9 строится аффективно. На самом деле может быть построен даже нормальный алгорифм, перерабатывающий запись произвольного оператора рассматриваемого типа в запись его неподвижной точки. 3'. Любопытно отметить, что в приводимом нами определении оператора отсутствует какое-либо требование „согласованности": не требуется, чтобы „равные" (в смысле совпадения значений) функции оператор снова переводил в „равные". РАСПОЗНАВАНИЕ ИНВАРИАНТНЪ|Х СВОЙСТВ ззз з зе! Вычислимые ВеРБАльные ФУнкции |гл, ю| ззв 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
