В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 49
Текст из файла (страница 49)
Постройте машину Тьюринга (называемую «удвоение и обозначаемую Г), которая перерабатывает слово 01"0 в слово 01"01"О, причем в начальном и конечном положении обозревается крайняя левая ячейка. 12.29. Постройте машину Тьюринга, переводящую слово 01'01»01'0 в слово 01'01'01»0, причем в начальном положении обозревается ячейка с 0 между наборами из у и ~ единиц, а в конечном положении обозревается ячейка с 0 между наборами из ~ и х единиц. (Эта машина называется «циклический сдвиг» и обозначается Ц.) Ре ш е н и е. Проверим, что такой перевод произойдет в результате последовательного применения (композиции) ранее построенных машин В, Б и В, т.е. Ц = ВБ В.
В самом деле, вычисляем: ВБ-В(01«01»9101«0) * ВБ-(В(01 "О!»9~0!'0)) ВБ-(01 "О!'901»0) = В(Б-(ОРО1 901»О)) = В(ОР901 ОРО) = 01*9,01"01»О. 12.30. Постройте машину Тьюринга, перерабатывающую слово 01"01» в слово 01"01'01"01», причем в начальном положении обозревается самая левая ячейка, а в конечном — ячейка, в которой записан О, заключенный между массивами 1"01» и 1"01».
(Машина называется «копирование» и обозначается Кь) Указание. Проверьте, что эта машина представляет собой следующую композицию построенных выше машин: К2 = Б'ГВБ'ВГВБ'ВБ Б ВБ'. 12.31. Постройте машину Тьюринга с внешним алфавитом А = = (а», Ц, обладающую следующим свойством: а) машина не применима ни к какому непустому слову, т.е. применение машины к любому непустому слову приводит к тому, что машина никогда не останавливается; б) машина применима к любому непустому слову, т.е.
любое непустое слово перерабатывается машиной в некоторое слово (в результате машина останавливается т.е. приходит в состояние д»); в) машина применима только к словам вида 11...1 (Зп единиц), л > 1; г) машина применима только к словам вида 11 ... 1а,11... 1 (слева от а» и единиц, справа — т единиц), л > 1, т > 1. 236 Сс О!'гО!" д00"'0 Б: 01 "г д01п 00 "ЗО д,0!в 01 г01но Б'. 01чд01пО!"'зО В: О1" д01" 01чО Сс01' д00'00'0 Б'. 01" 01"'д01" 0 Б: д01"'01"'00"'О.
Таким образом, функция 1г(хь х„хг) = хг вычисляется следующей композицией машин: Б'ВБ'ОБ ОБ = Б'ВБ'(ОБ )'. в) Теперь мы можем представить себе алгоритм построения композиции машин Б', В, Б, О для вычисления любой функции вида 1 "(х„хг, ..., х„) = х . С помощью правого сдвига Б', применив его т — 1 раз, нужно сначала достичь массива 01сч (Б')" ': 01вО...д01""0...01"'"О.
237 Решение. а) Будем считать, что машина начинает работать из стандартного начального положения, т.е. в начальном состоянии д, «головкой» машины обозревается ячейка, в которой записана самая правая единица перерабатываемого слова. Тогда искомую машину построить нетрудно: из начального положения она должна неограниченно двигаться по ленте вправо.
Вот ее функциональная схема: д,ао -+ доао д~! -+ дг1П, дгао -+ дгаоП* дг1 -+ дг1П. В этой машине предусмотрена остановка, если только в начальном состоянии д~ обозревается пустая ячейка, т.е. если машина применяется к пустому слову. Попьпайтесь построить машину Тьюринга, отвечающую требованию настоящей задачи, при условии, что она начинает работать из положения, в котором обозревается произвольная ячейка с буквой данного слова. Вычислимые ио Тьвриигу функции. Уточним понятие вычислимости функции на машине Тьюринга. Будем говорить, что машина правильно вычисляет функцию Яхь хг, ..., х„), если начальное слово д,01"'01"0...01""0 машина переводит в слово до01Г<" "' - ""'0 ...
0 и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция 7'не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева. 12.32. Постройте машины Тьюринга, которые правильно вычисляют следующие функции: а) 7(х) = х + 1; б) 0(х) = О. Указание. См.задачи!2.1и12.13.
12.33. Постройте машины Тьюринга, правильно вычисляющие следующие функции: а) 1г(хп хг) = хг, .б) 1г(хь х„х,) = х,; в) 1"(хь хг, ..., х„) = х (1 ~ т ~ и). Решение. б) Мы должны переработать слово д,О!"<О!"'ОроО в слово до 01 гО. Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга Б', В, Б, Сч Затем, двигаясь влево, транспонировать (с помощью В) массив О! ъ с кюкдым соседним слева массивом, пока массив 01"" не выйдет на первое место: (ВБ ) ': д01"-01ч0...01-ч01- 0...01 О. Теперь нужно дойти до крайнего правого массива с помощью (л — 1)-кратного применения правого сдвига Б'.
(Б')" '. 01'"01" О... 01' '01'""0 ... ц01*"О. Наконец нужно стирать последовательно справа налево все массивы единиц, кроме первого: (ОБ)" '. д01"-00"'0...00"--'00'-~0...00*0. Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга: (Б')" '(ВБ )" '(Б')" '(ОБ )" '. 12.34. Докажите, что следующие функции вычислимы по Тьюрингу, для чего постройте машины Тьюринга, вычисляющие иж а),Дх, у) = х+у; б) ~(х) = х-'1 = (О, если х = О, в) а8(х) =~ ' 11, если х > 0; (О, если х > О, г) а8(х) =~ ' !1, если х = 0; ~0, если х < О, !х — 1, если х > у; е) г(х, у) = х — у (х > у); ~х1 х 3) У(х) = ~ — ~ — целая часть числа —; Ы 2' и) ~(х, у) = НОД(х, у); к) Дх) = 2х + 1; л) г"(х) = —; м) г"(х) = 1 н)г"(х) = 2' ". 238 Указание.
а) См. задачу!2.4; е) см. задачу12.22;ж) см. Учебник, пример 32.5; и) см. задачи 12.6 и 12.23; л) составьте программу машины Тьюринга, вычисляющей эту функцию, исходя из того, что зта функция фактически равна следующей: 11, если х = 1, ,г"(х) = ~ ' ~0, если х > 1. Решение. в) Проверьте, что данная функция вычисляется следующей машиной Тьюринга, исходя из стандартного начального положения: 9,0 -+ даО, у~1 -~ дзОЛ, дз! -+ дзОЛ, 9~0 -+ 9~1. Программа машины, правильно вычисляющей эту функцию, такова: %0 -+ ЧгОП, дз1 -+ д»1П, %0 -+ ЧоОЛ (для х = 0), Чз! -+ Чз1П, 9»0 + д40Л д~! + 9~0Л 940 + 9зОП д~О + да1Л ° 12.35. Докажите, что следующие функции вычислимы по Тьюрингу, построив соответствующие машины Тьюринга: 11, х делится на 3, а) Л(~)=~ (О, х не делится на 3; (1, х делится на р, б) ~,(х) =! ' 10, х не делится на р.
Указание. См. задачу 12.2. 12.36. Машина Тьюринга имеет следующую функциональную схему: %0 — » й!Л, д,! -+ 9,1П, дзО -+ дз1П, 9»! -+ 9~1Л, Ч»0 — » ЧоО, 9»! -+ де1. Найдите формульное выражение функции Г(х), вычисляемой этой машиной. 12.37. По программе машины Тьюринга напишите формульное выражение функции Г(х, у), вычисляемой этой машиной: 12.38. а) Докажите, что если машины Тьюринга Ги б правильно вычисляют функции Яу) и я(х) соответственно, то композиция Н= Гб этих машин правильно вычисляет сложную функцию л(х) = Д8(х)). б) Докажите, что если функции )"(еь гз), я,(х, у), я~(х, у) вычислимы по Тьюрингу, то и сложная функция ~Р(х, у) =~(й(х, У) я,(х, у)) вычислима по Тьюрингу.
239 в) докажите, что если функции Ле>, ег, е)). Ф(х, у), й(х у) е)(х, у) вычислимы по Тьюрингу, то и сложная функция г()(х, у) = = Лй)(х У) й(х, У), Я)(х, у)) вычислима по Тьюрингу. Решение. а) В самом деле, применим машину (»к начальной конфигурации о)01'. Получим: о01в(").
Применяя далее к полученной конфигурации машину Г, получим: д01г(в(»». б) Пусть машины Е, 6„0) правильно вычисляют функции 1; я), яг соответственно. Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию (р(х, у), пользуясь введенными выше машинами копирования К:„циклического сдвига Ц, левого сдвига Б: 62 01в(»,»)Д01вг(» в) Б: а01вг(» в)01вг(» в) д,01"О1» Ка: О 1 "01»()01 "01» дО]У(вг(», »), вг(», »)) 6): 01'01»а01" (" > Ц: 01 (" »а01"01» ()0 -г Чоб: Е)01 ф 13.
Рекурсивные функции В этом параграфе рассматриваются функции ~> Ф" — г Ф, т.е. заданные на множестве Ф = (О, 1, 2, ...) натуральных чисел и принимающие значения в нем же. При этом, эти функции могут быть как всюду определенными, так и не всюду определенными, т.е. частичными. Говорят, что функция от и аргументов г"(х„..., х„) = ~(й)(х„ ..., х„), ..., я (х„..., х„)) получена с помощью оператора суперпозиции из функций у(у), ..., у ) от т аргументов и функций я)(х„ ..., х„), ..., я„(х„..., х„) от и аргументов.
Примитивно рекурсивные функции. Следующие всюду определенные функции называют простейи(ими: 0(х) = О, Я(х) = х + 1, 1"„(х( ..., х„) = х (1 < т < п). Говорят, что (и+ 1)-местная функция (р получена из и-местной функции у" и (и + 2)-местной функции я с помощью оператора примитивной рекурсии, если для любых х„..., х„, у справедливы равенства: (Р(х)г р Х»> 0)»В(Х)г г Х»)г (р(х„..., х„, у + 1) = я(х„..., х„, у), (р(х„..., х„, у)). 240 Пара этих равенств называется схемой примитивной рекурсии. Для и = 0 схема примитивной рекурсии имеет следующий вид: Чг(0) = а. (Р(у + 1) = Я(У, ((г(у)), где а — постоянная одноместная функция, равная числу а. Функция называется примитивно рекурсивной, если она может быть получена из простейших функций О, Я, 1„" с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
Говорят, что функцияЯхп ...,х„) получена из функций г(хп ..., х„, г) и а(х„..., х„) с помощью ограниченного оператора минимизации (ограниченного р-оператора), и обозначают г(хь ..., х„) = = иг < а(я(хь ..., х„, г) = 01, если выполнено условие: Яхь ..., х„) = = г < а(хь ..., х„) тогда и только тогда, когда я(хь ..., х„, 0) ~ ~ О, я(ХИ ..., Х„, 1) И О, ..., я(ХН ..., Х„, г — 1) ,-о О, а г(Х„..., Х„, г) = О. 13.1. Докажите, что следующие функции примитивно рекурсивны, руководствуясь непосредственно определением примитивно рекурсивной функции: а) <р(х) = и; б) ор(х) = х+ и; в) гр(х, у) = х+ у; г) ор(х, у) = ху.
Решение. а) Покажем, что эта функция получается из простейших в результате лишь их суперпозиции, без применения оператора примитивной рекурсии. В самом деле, чтобы из любого числа х получить фиксированнное число и, нужно сначала числу х сопоставить число 0: 0(х) = О, а затем к полученному результату, т.е. к О, с ПЬмощью функции Я прибавлять по единице 1 до тех пор, пока не получится число и, т.е. необходимо применить эту функцию к числу 0(х) последовательно и раз. Получим выражение: гр(х) = Ю(Я(...Ю(0(х))...)), доказывающее примитивную рекурсивность данной функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
