Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 143

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ров, которые, будучи

примененными

к заданным (или,

как

говорят,

исходным) функциям, порождают

новые функции. Допустим, что раз

и навсегда

зафиксирована какая-то

система

Q исходных

функций;

тогда имеет смысл рассматривать класс

Q1

всех

тех

функции ср,

каждая

из которых может быть определена, исходя

из

Q,

при­

менением

 

наших операторов

в

нужном

количестве

и в

нужном

порядке.

Учитывая

специфику

этих

операторов,

ясно,

что

такое

определение функции ср записывается формально

как система

всех

равенств,

 

входящих

в

фактически

употребленные схемы

супер­

позиции,

примитивных

рекурсий

и

(х-операторов.

Условимся

на­

зывать эту

систему

равенств

рекурсивным

описанием

функции ср.

Внимательный просмотр примеров, разобранных в предыдущих раз­

делах,

показывает,

что для

всех

встречавшихся

там

функций

воз­

можны рекурсивные описания при трех исходных функциях:

 

 

 

1)

константа

нуль:

0(л:) = 0,

 

 

 

 

 

 

s(x)=x+l,

 

 

 

2)

функция

непосредственного

следования:

 

 

 

 

3)

функция

непосредственного

предшествования:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

( х— 1

при

х

> О,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

0

при

х = 0.

 

 

 

 

 

 

 

 

Эти

функции

чрезвычайно просты и очевидным образом

вычислимы

по Тьюрингу. Заметим, что вычислимость s(x)

и s (х)

по существу

оз­

начает

способность

прямого

и

обратного

счета чисел

натурального

ряда.

 

 

 

 

 

 

 

 

функцию ср (у)

 

 

 

 

 

 

 

 

 

 

 

Рассмотрим, например,

=

[log2 (/]. Она

была

оп­

ределена

как

цл; (2A'"*"'

>

у)

с привлечением

показательной

функции

тр (А-) =

 

2х

и

так

называемой

диагональной

функции

J

(у)

=

у.

Очевидно,

J

{у)

= 1

(s (у)),

а 2* =

Я (х,

2),

где X (х,

п)

 

—

степенно-

показательная функция пх.

 

Как мы уже видели, X (0, я) =

1,

X (х

+

+

1, л) =

п

(X (х,

л),

л),

р Д е П °Д 3 1

(*> ") следует

понимать

произ­

ведение

х

X

п.

Наконец,

произведение

определялось

через

сумму:

 

О х

я

=

О,

(.V +

1) X

я =

а

(х

X п, л),

где

а

(х,

 

л) =

х

+

л,

а сумма — через функции

J (л)

и

s : 0 +

л =

л,

(х

 

+

1) +

я —

<=

s (х +

я).

Сведя все эти

равенства вместе,

получаем

рекурсивное

описание (вернее, одно из возможных рекурсивных описаний функ­ ции [log2 ]).

J(x)=7(s(x)),

Г0(0, n) = J(n),

\a(x+\

 

 

n) =

s(o(x,

n));

 

(n(0,

 

n) = Q,

 

 

 

\л(х

+ 1,

л) =

а ( я ( х ,

л),

я),

! X (0,

 

n) =

l,

 

 

 

(X(x

+

\.

n) =

n(X (x,

л),

n).

•ty(x) =

X(x,

2),

 

 

 

Ф (y) =

ц^(г|>(* +1)>J

Щ.

Любая функция, для которой возможно рекурсивное описание при исходных функциях 0 (х), 5 (.V), s (х), называется общерекурсивион, или просто рекурсивной. Рекурсивное описание называется

109

примитивно рекурсивным, если в нем ле участвует u-оператор, т.е. допускаются только операторы суперпозиции введения фиктивных переменных п примитивной рекурсии. Функция называется примитив­ но рекурсивной, если для нее существует примитивно-рекурсивное описание. Предложенное нами описание функции [log2 ] показывает, что эта функция рекурсивна; поскольку в нем встречается (i-оператор, это не дает нам основания утверждать, то [log,] примитивно рекур­ сивна. Однако это также не дает нам основания утверждать, что

функция [log2 ]

наверняка

 

не примитивно рекурсивна,

ибо заранее

не исключено,

что можно

придумать другое описание,

которое при­

митивно-рекурсивно (и н

самом деле такое можно

придумать!).

«Начальные куски» рассмотренного нами описания являются рекур­ сивными и даже примитивно рекурсивными описаниями промежу­ точных функций, возникших по пути определения [log2 ], а именно суммы, произведения и т. п.

По смыслу операторов суперпозиции, примитивной рекурсии и (.(.-оператора ясно, что рекурсивное описание некоторой функции может рассматриваться как своего рода программа — ее можно на­ зывать рекурсивной программой — для вычисления функции <р. Например, для вычисления [log,7| нужно приступать к вычислению значений 2°, 21 , 1", .... что возвращает нас к функции 1Х~ Вычисление значений этой функции сводится к вычислению значений произведе­ ния п так далее, вплоть до исходных функций. Однако, подытожи­

вая материал предыдущих разделов, мы

можем

теперь

высказать

более

точное утверждение.

Справедлива

 

 

 

 

 

Т е о р е м а .

Всякая

рекурсивная

функция

вычислима

по

Тью­

рингу;

существует

алгоритм,

который

по любой рекурсивной

про­

грамме

строит

тыорингову

программу,

вычисляющую

ту

оке

функцию.

 

 

 

 

 

 

 

 

 

На первый взгляд, выбор функции 0

( A - ) , S

( Л - )

И S

( А - )

В каче

исходных может

показаться

случайным.

В некотором

смысле

это

на самом деле так; можно было бы рассматривать

и другие

исходные

функции. Однако

весьма

примечательным

и глубоким

является то

обстоятельство, что даже при нашем бедном выборе исходных функции можно получать рекурсивные описания для всех функций, наиболее употребительных в арифметике и в теории чисел; следова­ тельно, расширение запаса исходных функций за счет присоедние

ния

других

естественно

напрашивающихся

«кандидатов»

не приве­

дет

к

расширению

класса

функций,

допускающих

 

рекурсивные

описания.

Мы ограничимся

здесь

еще

некоторыми

иллюстрациями

широты

класса рекурсивных

а значит

и класса

функций, вычисли­

мых

по

Тьюрингу.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Конечные

функции.

Так

мы называет функции, которые почти

константны

в

следующем

смысле:

 

существует

такая

константа

с,

что I принимав: значения,

отличные от с не

более, чем конечное чис­

ло раз.

Пусть,

например,

I (0) =

2;

\

(1) =

Б, /;

( А

)

=

7 при

х > 3.

Тогда посредством примитивных рекурсий (типа ( # ) на

стр. 105)

по­

следовательно

определяем

f,

(0) = 5 ,

fa

(х +

1) =

7;

ft (0) =

2,

I (х

-\- 1) =

[Л

( А ) .

Показать,

что

все конечные

 

функции

прими­

тивно рекурсивны! Запомним следующие конечные функции, назы­ ваемые сигнум и антисигнум:

при х ф 0, при А ' = 0.

110

Арифметические функции и отношения. Мы уже установили при­ митивную рекурсивиость суммы, произведения, показательной функ­ ции и др. Применением суперпозиций можно получить всевозможные

многочлены с натуральными

коэффициентами,

а также более

слож­

ные выражения

типа

 

 

 

 

 

((5**+ 4 г)* , + 1 7 +2xyz)-2^v

+

5

 

и т.п.

 

 

 

 

 

Некоторые

затруднения

возникают в связи

с описанием

обрат­

ных операций: вычитания, деления и т.п. Поскольку они не всегда выполнимы, обычно их доопределяют дополнительными соглаше­ ниями, рассматривают так называемые арифметические варианты функций и т. п. Например, вместо разности я — х рассматривают

арифметическую

разность

п х =

{

~0 Х

при я

<

х

к 0

Т 0 Р а я

определяется

примитивной

рекурсией!

 

 

 

 

 

 

 

 

 

 

п — 0 — n п - (х + 1) = s (л

я).

 

 

 

 

Отсюда

видно,

что суперпозиция

sgn

(л — х)

описывает

предикат

Мн (х,

л), а

суперпозиция

sgn (л — х) X

sgn

(х

л)

определяет

предикат Рв

(л,

х). Следовательно,

функции

част (х,

л)

и ост

( А - , л),

при определении которых с помощью совместной примитивной ре­ курсии (11.3) использовались предикаты Мн и Рв, также примитив­ но рекурсивны.

Отношение делимости и свойство быть простым числом прими­ тивно рекурсивны в том смысле, что примитивно рекурсивны их характеристические функции

1, если х нацело делится на я,

Ов противном случае.

1.если х простое число.

пр (х) = О в противном случае.

Действительно, х\п = Рв (ост (х, л), 0); напомним, что в соот­ ветствии с принятым ранее определением функции ост (х, л) мы долж­ ны считать х\ 0 = 1.. Что же касается пр (А-), то здесь можно посту­ пать по-разному, но мы остановимся на следующем описании! сум­ ма v (и, х) вида ( * : 0 ) + (л-- 1) + ... + ( * ' : ") равна числу делителей числа х, не превосходящих и. Эта сумма может быть описана рекур­ сивно:

v (0, х) = 1, v (и + 1, х) = v (и, х) + (х\ {и + I)). Поэтому функция п (х), равная числу всех делителей числа х, может

быть выражена так: n(x)=v

(х, х).

Наконец, х—простое число, когда

оно больше 1 и имеет в точности

три

делителя (а именно 0, 1 и само

х). Следовательно,

пр (х) =

Мн (1,

х) X Рв (л (х),

3).

 

Пусть функция

П (Л) пересчитывает в порядке возрастания все

простые числа, т. е. П ( 0 ) = 2 , П (1) = 3,

П ( 2 ) = 5,

...

Очевидно,

произведение пр {у)

X Мн (Я (х), у)

равно

единице

в том

и только

в том случае, когда у — простое число, превосходящее П (х). Следо­

вательно

функция П (х) рекурсивна

ибо ее

можно определить

так:

 

 

 

/7(0)

= 2 . Я ( А - + 1 ) = ( . 1 ( / ( ( П Р ( ( / ) Х М Н ( / 7 ( Л )

< / ) ) = 1)

I I I

11.6. Рекурсивное программирование функций, вычислимых по Тьюрингу. Вычислимы ли на машинах Тьюринга такие функции, которые не рекурсивны? Отрицательный ответ па &тот вопрос оытекает из следующей теоремы, доказательству которой и посвящен

данный параграф.

Пусть

машина

Тьюринга

 

вычисляет

функцию

 

Т е о р е м а .

9)f

f {х\,

* т ) ;

тогда

по заданной

функциональной

схеме машины 9Л

(по

заданной

тыорин.'оеоп

программе) можно

построить

рекурсив­

ное описание

этой

функции

f (х\,

хт).

степени примечательный

 

Таким образом,

выясняется

в высшей

факт, что два класса функций, первоначально описанные в разных терминах, а именно, класс тыорингово вычислимых функций и класс рекурсивных функций, совпадают. Доказательство теоремы само по

себе очень поучительное,

ибо оно основано на весьма любопытном

методе арифметической

интерпретации

(арифметизации),

который

уже упоминался

бегло

в н .

11.1 В нашем

случае

арифметизация на­

чинается с того, что с каждой конечной конфигурацией

К машины 9Л

сопоставляются

четверка

натуральных

чисел

s (К),

q (К),

т (К),

п (К) — координаты этой

конфигурации. Хорошо известно, сколь

плодотворным является применение координатного метода в геомет­ рии; он позволяет (в рамках аналитической геометрии) применять к решению геометрических задач хорошо разработанные алгебраи­ ческие и аналитические методы. При этом в каждой конкретной ситуации успех дела и простота решения в значительной мере за­ висят от того, насколько удачно выбрана система координат. В на­ шем случае (в отличие от аналитической геометрии!) в качестве коор­ динат используются не любые действительные числа, а натуральные числа; соответственно, на смену алгебраическим и аналитическим методам приходят теоретико-числовые (арифметические) конструк­ ции и методы.

Пусть К' — конфигурация, непосредственно следующая за /(; обозначим через s, q т п координаты «текущей» конфигурации /( и через s', q', т', п' —- координаты конфигурации К'. Наша ближай­ шая цель — описать такую координатизацнго, для которо.н выполне­ но следующее условие которое можно называть условием коррект­ ности: функции

s' = s' (s, q. m, n)\ q' = q' (s, q, m, n)\ m' •= m' (s q, т. я); n' = n' (s, q, m, n)

примитивно рекурсивны Именно такой удачный выбор «системы координат» — корректная координатизация — и обеспечит успех дела в целом, т. е. доказательство теоремы в полном объеме. Заметим

сначала, что любая конечная тыорингова

конфигурация К однознач­

но определена четверкой (si. qj, Ki,

Кр),

где$г — обозреваемый сим­

вол, qj — внутреннее

состояние.

/С; и

Кр — соответственно левое

и правое крыло конфигурации, т. е.

слова

(возможно

пустые),

располагающиеся на

ленте левее

и правее

обозреваемой

ячейки.

Разъясним это несколько подробнее. Если левее обозреваемой ячей­

ки — сплошь

пустые

символы

Л,

то /<; = л ;

в противном

случае

/<; — слово,

простирающееся

от

самого

левого

непустого

символа

до той ячейки, которая непосредственно левее оборзеваемой

Напри­

мер, для конфигурации К (рис. 27)

 

 

 

 

si=i

?/ = ?з

/</ = ! * * .

Кр =

* Л 1

 

112

Смотрите также файлы