Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

60 Р. В. Рта
ривается как изображение числа /г, если лента содержит п единиц, распределенных на ней любым способом. Наше же соглашение кодировать числа цепочками из 0 и 1 (т. е. в двоичной системе счисления) требует, чтобы выходная лента в точности состояла из двоичного представления числа: только в этом случае она рассматривается как числовой выход.
К счастью, нужное нам видоизменение этой арифметизации оказывается очень простым. Мы должны изменить только функции MR и Corn и отношение Fin. Получающаяся в результате арифметизация дает элементарные U и ТП} такие, что гс-мест-ная функция f вычислима (в двоичной системе счисления) тогда и только тогда, когда существует число z0, такое, что для
Л[, . . . , Xifi
f(\) = U (min у [Тп (г„, х, у)]).
Чтобы выполнить это, переопределяем MR так, чтобы MR (n) было гёделевым номером ленты, которая состоит в точности из двоичного представления /г; переопределяем Corn так, чтобы Corn (я) = п тогда и только тогда, когда MR(/z) = x, и, наконец, переопределяем Fin так, чтобы Fin (л:, z) было верно тогда и только тогда, когда Fin (л;, z) верно в смысле Дэвиса, а также лента, входящая в описание с номером х, есть двоичное представление некоторого числа. Элементарные определения MR, Corn и Fin даны в приложении 1.
Предположим, что га-местная числовая функция f принадлежит F{. Тогда, в частности, она вычислима, так что существует ZQ, ДЛЯ КОТОрОГО
/ (х) = U (min у [Тп (z0, x, у)]).
Для того чтобы показать, что функция f элементарна, достаточно показать, что г/, рассматриваемое как функция от х, ограничено некоторой элементарной функцией g. Ибо тогда
/ (х) = U (min у < g (х) [Тп (з0, х, у)]),
где правая часть элементарна.
Чтобы показать, что существует элементарная функция g, которая ограничивает г/, рассуждаем следующим образом. Максимальное число ячеек ленты, которые могут быть использованы на каком-нибудь шаге вычисления на данной машине Тьюринга Z, есть я/(х). По лемме 3 это меньше, чем /г(х), где
/i(x) = ff_1(/Cmax(x, 1)),
и согласно [3] функция h элементарна. Машина Z имеет конечное число m символов, которые могут появляться на ленте. Таким образом, число различных лент, которые могут возникнуть при вычислении, меньше, чем тл(х), кроме того, у Z

 

1 10 20 30 40 50 60 61 62 63 64 65 66 67 68 69 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика