С.В. Яблонский - Введение в дискретную математику (1060464), страница 22
Текст из файла (страница 22)
+ 1 единиц и начала этих массивов согласованы, т. е. идут на ленте подряд в соответствии с номерами решеток (см. рис. 6; на данном рисунке для наглядности каждая решетка изображена отдельно); в) кеазиосновной код определяется для произвольного основного кода Ь,Ь>... Ь„где Ь, = Ь. =1, в виде следующей записи: Ь,и,ь>(>>...
П„,ЬЧ (с>>(= ° ..= 1((,->1 =( — 1 (Е>2). где гл. а вьгшслимыв эхпкцпн Таким образом, в квазноспозпом коде на решетке с шагом 1 расположен основной код, внутренние промежутки заполнены словами Уь Пн ..., У. „а остальная часть ленты — пустая. С машинными кодами и их преобразованиями связан ряд лемм.
Л е м м а 2 (о преобразовании основного кода в 1-кратный код). Пусть 1 — натуральное число (1~ 2). Тогда люлсно построить машину Тьюринга, креоброгующую основной код в соответствующий 1-кратный с некоторыл заданным буугерным словом У, еде !У(=1 и У ОУ'. Доказательство. 1 этап. Искомая машина будет постепенно на ленте правее основного кода строить 1-кратнын код. Для этого просматриваются слева направо символы основного кода и каждый символ основного кода на некотором шаге заменяется нулем, а справа пристраивается либо массив из 1 единиц, если в основном коде была 1, либо слово У, если в основном коде был О.
В процессе этого построения на ленте будет появляться слово, в котором мекгду двумя соседними единицами не может стоять более 1 нулей. Для таких слов можно (как для основных кодов) построить машину, находящую его левый (соответственно правый) конец. Обозначим соответствующие перемещения головки на ленте через Ь и В. Таким образом, работу машины можно описать более точно: 1) выходим на правый конец основного кода (оператор Н); 2) отступая две клетки вправо, выписываем массив из 1 единиц. Данное.преобразовапие обозначим.
через Ф (аь-ч-~а 001... 1'); ! 3) возвращаемся на левый конец основного кода (оператор 1); 4) просматривая первые три символа а'а" а'" с левого конца основного кода (а в последующем — в оставшейся части основного кода), вычисляем трехзначный предикат р(а', а", а"). Если а'а" а" 11а"', то имеем 1 режим и переходим к преобразованию, которое указывается стрелкой 1 (рз). Если а'а" а"' 101, то имеем и режим и переходим к оператору, следующему за р.
Если а'а" а"' =100, то имеем 111 режим и переходим к преобразованию, которое указывается стрелкой т (р,). 19б ч. х Функцпоньльные системы с Опегьцнями 1 режим. 5) Стираем символ а' (оператор 0(а')); 6) Выходим на правый конец слова (оператор П); 7) Пристраиваем непосредственно справа от слова массив ие 1 единиц (оператор Ф(а~ -~.а 1 ..'. 1~)); 8) Воевращаемся на левый конец слова (оператор С) и переходим к 4). 11 режим (первый символ а' — последний в массиве единиц основного кода, но имеется по крайней мере один не обработанный массив нз единиц в основном коде), 9) Стираем символ а' (0(а') ); 10) Выходим ва правый конец слова (оператор П); 11) Пристраиваем непосредственно справа от слова буферное слово У и еще 1 единиц (оператор Ф (а' -» -»аУ1... 1')); 12) Воавращаемся на левый конец слова (оператор Е) и переходим к 4), 111 режим (первый символ а' является последним в основном коде).
13) Стираем символ а' (0(а')); 14) Двигаясь вправо, выходим на левый конец построенного 1-кратного кода и останавливаемся. 11 э т а п. Мы получаем следующую операторную схему: ЖЯ» Реалиаация операторов атой схемы не вызывает ватруднений и по схеме легко может быть построена программа машины. Лемма докааана. Лемма 3 (о преобразованян решетчатого кода в основной). Пусть е — натуральное час*о, а~ 2. Тоеда можно построить машину Тьюринеа, которая преобразует произвольный решетчатый код с параметром е е соотеетстеуюи)ий основной код, гл.
ь вычпслпмыв еь нкцпп ~за Доказательство. 1 этап. Сначала опишем идею работы машины. Обозревая в начальный момент левуто единицу решетчатого кода, машина отступает далее влево на определенное расстояние и постепенно справа налево формирует там основной код путем «перетаскивания» кодов с решеток, начиная с е-й и кончая 1-й решеткой (см. рис. 7). 1... 101 ... 10...01...
10...011 пс»»Оной »» 1 решетжаий»»д Рис. 7 Более точно преобразование можно характеризовать так: разобьем его на последовательность более простых преобразований е А„А,... А,то. Преобразование А, (предварительная подготовка ленты). 1) Отступаем от начальной ячейки (левая единица решетчатого кода) влево на 0 ячеек (оператор ьт) е). 2) Непосредственно слева за этим промежутком вписываем единицу (оператор Ф(а'- 1'а)).
Преобразование закончено. П р е о б р а з о в а н н е А, («перетаскивание» массива единиц с е-й решетки). 1) От ячейки, в которой оператор А, поставил 1, смещаемся вправо на 20 ячеек (оператор тг~т ) Мы попадаем на левый конец массива, расположенного на г-й решетке. Пусть а', а" — первые два символа на г-й решетке (а' — левый конец). 2) Выясняем, является ли а' одновременно и правым концом кода путем вычисления предиката р(а, а" ) (с возвращением к а'): р (а', а") О при а" О (а' — правый конец массива), 1 при а 1 (а' — не есть правый конец массива). «) В решетчатом коде подряд может стоять в — $ пулей.
140 ч. ь Функцнон»льпые системы с ОпеРАциями Если р = 1 (а' — ие правый конец массива на з-й решетке), то: 3) Движемся до правого конца массива на этой решетке (оператор вт). 4) Стираем последний символ а в массиве (оператор 0(а)). 5) Возвращаемся на левый конец массива (оператор Е).
6) Смещаемся влево еще на 2» ячеек (оператор Аз) — мы попадаем на правый конец основного кода (вернее — построенного куска основного кода). 7) Выходим на левый конец основного кода (оператор 1). 8) Приписываем слева к основному коду символ (оператор Ф(а'- 1'а)). 9) Возвращаемся на правый конец основного кода (оператор зз), после чего переходим к 1). Если р = 0 (а' — правый конец массива на з-й решетке), то: 10) Стираем символ а' (оператор 0(а') ). 11) Смещаемся влево на 2» ячеек (оператор 11'), мы попадаем на правый конец основного кода.
12) Выходим на левый конец основного кода (оператор Е). 13) Приписываем слева к основному коду символы 10 (оператор Ф(а' - 1'Оа) ). 14) Возвращаемся на правый копец основного кода (гз). Преобразование закончено. П р е о б р а з о в а н п е Лз (1 < 1< з)' (»перетаскивание» массива единиц с (-й решетки). Выполняется так же, как и А, с ваменой операторов В'" и Ьз соответз-~-з вэч отвеяно на Лз и 1з з что обеспечивает попадание на 1-ю решетку. П р е о б р а з о в а и и е А, (»перетаскивание» массива единиц с 1-й решетки).
Выполняется так же, как и Л, зз Зв зтз с заменой операторов ттз и А з соответственно на Вз и Ьз+' и изъятием операторов Ф(а' - 1'Оа) и В (сп. п,п. 13) и 14)), поскольку эти операторы осуществляют подготовку к следующему преобразованию, а Л, является последним. 11 этап. Очевидно, мы имеем следующие оператор- гл. к вычпслпмык агнкции ные схемы для преобразований А„А„..., А„..., А,: Яг- ф>(е г а)а, лг пг)г~ ге(г 7 ее/Ро, м т гв' рве Лемма доказана. Л е м м а 4 (о преобразовании кваэиосновного кода в основной). Для люоого натурального числа 1(1~2) можно построить машину Тьюринга, которая произвольный квазиосновной код Ь,КЬ ... У„,Ь„, где ) У,) Ф„-,( 1 — 1, преобразует в соответствуюигий основной код Ь,Ь»... Ь,. Докааател1ство. 1.
этап. Искомая машина сначала отступает на некоторый промежуток вправо от кваэиосновного кода и затем постепенно там формирует основной код путем «перетаскивания» основного кода с решетки. Более точно преобразование состоит в следующем. 1) В начальный момент обозревается символ Ь„т. е. символ в узле решетки с шагом 1, на которой расположен основной код.
Движемся по решетке на правый конец основного кода (оператор Я), осуществляя стирание буферных слов Уи ..., У„и лежащих вне решетки (см. следствие 2 леммы 1). 2) Справа от правого конца (символ Ь,)' вписываем 31 — 1 нулей *) и одпу единицу (оператор Ф (Ь,'-». -«Ь„О... 0 1~)), после чего попадаем на ту же решетку. 31-1 3) Отыскиваем левый конец основного кода (оператор Г). ') В квазвосвоваск воде может подряд стоять 21 — 1 нулей. 142 ч ь Функциональные системы с опеРАцпями 4) Пусть а'а" а"' — первые три символа в основном коде (в начальный момент это Ь,Ь,Ь,).'Вычисляем ппедикат р(а'а" а'"), принимающий три значения. При а' 1 (основной режим) переходим к выполнению следующего за р оператора.
При а" О, а'" 1 а' является последней единицей в массиве и так как а 1, то имеется по крайней мере еще один массив — переходим к выполнению оператора, указываемого стрелкой с пометкой а" О, а"'-1. При а" =а'" 0 а' является последней единицей основного кода (т. е. а'-Ь„) — переходим к выполнению оператора, указываемого стрелкой с пометкой а" =* а" О. Основной режим а" 1.
5) Стираем символ а' (оператор 0(а')). 6) Движемся на правый конец основного кода (оператор Я). 7) Перемещаемся вправо еще на 31 ячеек (оператор дз'). 8)Выходим на правый конец формируемого кода (оператор В). 9) Приписываем справа единицу (оператор Ф(а'- — а1') ). 10) Движемся на левый конец формируемого кода (оператор Б) н переходим к 3). Режим а" О, а"'-1. Выполняем то же, что и в предыдущем режиме 5)'— 10), кроме пункта 9), где выполняем оператор Ф(а'- а01'). Режим а" а" -О. Здесь стираем символ а' (оператор 0(а')) и, сме- эы щаясь вправо на 31 ячеек (оператор В1), попадаем на левый конец искомого основного кода и останавливаемся.
П зтап. Мы имеем следующую операторную схему; 4ав(-а а лг) Гл. 4. Вычислимые Функции $4. Вычислимые функции Выше мы ввели систему Р»,, содержащую все константы из Е» и все функции, определенные на наборах »О чисел из расширенного натурального ряда Е» »г и принимающие значения на Е . Сейчас мы определим более О широкую, чем Р»,, систему функций. Пусть Дх„..., х„) — функция, определенная на подмножестве Ег множества всех наборов (аь ..., и.) чисел из расширенного натурального ряда Е» и принимающая значения также из Е», (вне множества Ег функция считается неопределенной).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
