1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 14
Текст из файла (страница 14)
Существуют частичные функции, не являющиеся частично рекурсивными.Доказательство. Рассмотрим семейство {æ0 (x), æ1 (x), æ2 (x), . . .}. В силу теоремы обуниверсальной ч.р.ф. оно совпадает с семейством всех одноместных ч.р.ф. Введемследующую всюду определенную одноместную функцию(æx (x) + 1, если æx (x) определено,f (x) =0иначе.§ 14. Машины Шёнфилда vs Частично рекурсивные функции57Допустим, f — ч.р.ф. Тогда найдется e ∈ ω такое, что f = æe .
Следовательно, æe тожевсюду определена. В частности, значение æe (e) определено. Но тогда æe (e) = f (e) =æe (e) + 1. Противоречие. Следовательно, f не является частично рекурсивной.В заключение параграфа мы докажем еще одну фундаментальную теорему теории алгоритмов — теорему о параметризации. Интуитивный смысл данной теоремысостоит в следующем. Если задана некоторая ч.р.ф. f (y, x), переменные которойусловно разделены на две группы, то к вычислению этой функции можно подойтидвумя способами.Первый способ — стандартный: мы целиком подаем на вход машины P , вычисляющей f , весь набор hy, xi и получаем на выходе значение f (y, x).Второй способ: мы фиксируем значения переменных y, считая их параметрами, ипреобразуем нашу программу P с помощью специального параметризатора в программу Py , которая уже будет вычислять функцию f как функцию от оставшихсяпеременных x.
Код программы Py зависит от значений y, но основное свойство заключается в том, что этот код может быть вычислен по y с помощью некоторой п.р.ф.s(y). Строго говоря, параметризатор — это и есть функция s, которая, используязначения y, преобразует код e программы P в код s(y) программы Py .'P-f (y, x)¾6Py¾6(y, x)x$S&6%yТеорема 40 (о параметризации).
Для любой ч.р.ф. f (y1 , . . . , ym , x1 , . . . , xn ) существует разнозначная п.р.ф. s(y1 , . . . , ym ) такая, чтоf (y1 , . . . , ym , x1 , . . . , xn ) = æns(y1 ,...,ym ) (x1 , . . . , xn ).Доказательство. Обозначим для краткости y = hy1 , . . . , ym i, x = hx1 , . . . , xn i и введем функцию f 0 (x, y), положив по определению f 0 (x, y) = f (y, x). Ясно, что f 0 (x, y)— ч.р.ф. Следовательно, существует машина Шёнфилда P с кодом e, которая еевычисляет. Обозначим через P ∗ макрос, соответствующий программе P .Зафиксируем значения y, считая их параметрами, и рассмотрим функцию g(x) =0f (x, y).
Данная функция вычисляется с помощью следующей макропрограммы:INC n + 1 ···y1INC n + 1···INC n + m ···y mINC n + mP∗По теореме об элиминации макросов эта макропрограмма эквивалентна программеPy , которая не использует макросы и код которой зависит от параметров y. Ясно, что58Глава III.
Формализации понятия вычислимой функцииесли l — число команд в программе P , то число команд в Py вычисляется с помощьюп.р.ф. h(y) = y1 + . . . + ym + l.Определим функцию(код k-ой команды Py , если в Py есть команда с номером k,G(k, y) =0иначе.Тогда код программы Py задается функцией¦1h(y)−s(y) =YG(k,y)+1pk.k=0Отсюда видно, что если доказать примитивную рекурсивность функции G(k, y),то функция s(y) также будет примитивно рекурсивной. Запишем определение функции G(k, y) в виде следующей неформальной схемы:код(INC n + 1),если 0 6 k < y1 ,код(INC n + 2),если y1 6 k < y1 + y2 ,······код(INC n + m),если y1 + . .
. + ym−1 6 k < y1 + . . . + ym ,если y1 + . . . + ym 6 k < y1 + . . . + ym + l,код(INC i),¦G(k, y) =и команда с номером k−(y1 + . . . + ym )из P имеет вид INC i,код(DEC i, j + y1 + . . . + ym ), если y1 + . . . + ym 6 k < y1 + . .
. + ym + l,¦и команда с номером k−(y1 + . . . + ym )из P имеет вид DEC i, j,0в остальных случаях.Теперь перепишем эту схему формально, используя только примитивно рекурсивные функции и предикаты. Определим вспомогательные п.р.ф. α(y) = y1 + . . . + ym¦и β(k, y) = k−α(y). Тогда< 0, n + 1 >,< 0, n + 2 >,···< 0, n³ + m >,´< 0, (e)β(k,y) >,G(k, y) =1³´ ³´<1,(e),(e)+α(y) >,β(k,y)β(k,y)120,если 0 6 k < y1 ,если y1 6 k < y1 + y2 ,···если y1 + .
. . +ym−1 6k<y1 + . . . +ym ,если y1 + . . . +ym 6k<y1 + . . . +ym +l³´и (e)β(k,y) = 0,0если y1 + . . . +ym 6k<y1 + . . . +ym +l³´и (e)β(k,y) = 1,0если k > y1 + . . . + ym + l.Отсюда, в силу предложения 24, заключаем, что G(k, y) — п.р.ф. По построениюæns(y) (x) = g(x) = f 0 (x, y) = f (y, x). Таким образом, функция s(y) — искомая.§ 15. Машины Тьюринга59Нам осталось только убедиться в том, что s — инъективная функция. Для этогонеобходимо доказать, что для любого z ∈ range(s) существует единственный наборy ∈ ω m такой, что s(y) = z.
Другими словами, требуется доказать, что существуетобратная функция s−1 : range(s) → ω m . (В этой части доказательства не требуетсяпоказывать, что s−1 частично рекурсивна!)Действительно, если задано z ∈ range(s), то z является кодом программы видаINC n + 1 ···y1 строкINC n + 1···INC n + m ···ym строкINC n + mªPl строкдля некоторых чисел y1 , . . . , ym и известного нам числа l (l — это число строк впрограмме P ). Числа y1 , . .
. , ym можно однозначно восстановить по виду программы,для этого нужно удалить из этой программы последние l строк, т. е. часть P . Тогдаколичество команд INC n+1 в оставшейся части — это y1 , количество команд INC n+2в оставшейся части — это y2 , и так далее. Окончательно получаем, что s−1 (z) =hy1 , . . .
, ym i.Следствие 41 (s-m-n-теорема). Для любых m, n ∈ ω существует разнозначная(m+1)-местная примитивно рекурсивная функция smn (e, y1 , . . . , ym ) такая, чтоæm+n(y1 , . . . , ym , x1 , . . . , xn ) = ænsm(x1 , . . . , xn ).en (e,y1 ,...,ym )Доказательство. Рассмотрим (m+n+1)-местную ч.р.ф. f (e, y, x) = æm+n(y, x). Поeтеореме о параметризации существует разнозначная п.р.ф. s(e, y) такая, что имеетместо f (e, y, x) = æns(e,y) (x). Функция s является искомой s-m-n-функцией.§ 15.Машины ТьюрингаМашины Тьюринга — это еще один подход к формализации понятия вычислимойфункции. Так же как и для машин Шёнфилда, модель для машины Тьюринга имеетмеханическое описание, но в отличие от первых машины Тьюринга более удобны длянепосредственной реализации в виде электротехнических устройств.Существует как минимум две причины, по которым машины Тьюринга можносчитать более «реалистичными», чем машины Шёнфилда.
Во-первых, в модели Тьюринга входные и выходные данные имеют символьный формат, т. е. данные — этослова, составленные из букв, записанных в ячейках ленты. В машинах Шёнфилда,как мы знаем, данные в регистрах могут быть записаны только в виде натуральныхчисел.
С инженерной точки зрения реализация типа данных «натуральные числа»является нетривиальной задачей и в конечном счете сводится к кодированию в видетех же самых слов. Во-вторых, машины Тьюринга — это устройства с последовательным доступом к памяти: чтобы получить доступ к содержащейся в некоторой60Глава III.
Формализации понятия вычислимой функцииячейке информации, машине приходится перебирать одну за другой все ячейки между текущей и требуемой. В отличие от этого, машины Шёнфилда имеют память сослучайным доступом: обращение к каждой ячейке осуществляется напрямую за одиншаг.Исторически машины Тьюринга возникли раньше, чем машины Шёнфилда, но,не смотря на то, что они являются более естественными и классическими устройствами, при доказательстве некоторых теорем удобнее оперировать с машинами Шёнфилда. В частности, теорему Клини о нормальной форме и теорему о параметризации можно доказать, используя терминологию и кодирование машин Тьюринга.Однако такой вариант доказательства этих теорем был бы намного сложнее технически, чем тот, что был предложен в предыдущем параграфе.Перейдем к неформальному описанию машин Тьюринга.Машина Тьюринга состоит из ленты, разбитой на одинаковые ячейки.В ячейках могут содержаться символы из внешнего алфавита A.
Содержимое ячеек может меняться. Лента — это механизм входов и выходов машины. Перед запуском машины входные данные записываются вконечном участке ленты, и в даль¾A ¢¢нейшем на каждом шаге вычислений. . . a2 a0 a0 a1 a3 a1 a7 a5 a0 . . . используется только конечное множество ячеек.
Однако в процессе работы лента может достраиватьсяновыми ячейками как слева, так и справа. Другими словами, лента является потенциально бесконечной в обе стороны.Также машина Тьюринга обладает считывающей головкой, которая в процессеработы машины может обозревать только одну ячейку и распознавать содержимоеэтой ячейки.
В зависимости от исполняемой команды головка способна изменятьсодержимое обозреваемой ячейки и сдвигаться за один шаг на одну ячейку влевоили вправо.Каждая машина Тьюринга имеет конечное число состояний q0 , q1 , . . . , qm , в которых она может находиться. В процессе работы машина может несколько раз возвращаться в одно и то же состояние. Работа всегда начинается с выделенного начального состояния. Кроме этого, есть выделенное конечное состояние. Если когда-нибудьмашина попадает в конечное состояние, то она останавливается, иначе работает бесконечно.Любая конкретная машина Тьюринга имеет свою уникальную программу. Программа — это конечный список команд, каждая из которых есть директива видаqi aj → qk al S, где qi , qk — состояния, aj , al — символы внешнего алфавита, S ∈{R, L, Λ}, причем для каждого неконечного состояния qi и любого символа aj в программе имеется ровно одна команда, начинающаяся с символов qi aj → .
. . Если жеqi — конечное состояние, то команда вида qi aj → . . . отсутствует в программе.Опишем один шаг работы машины Тьюринга. Пусть машина находится в некотором состоянии qi , а головка в текущий момент обозревает ячейку с символом aj .Если qi — конечное состояние, то машина останавливается. В противном случае впрограмме находится единственная команда вида qi aj → qk al S, которая затем исполПрограмма:Команда......
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
