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

алгоритмов для композиции, разветвления и повторения мы можем получить исходя из формулы (фр) тыорингову программу для алгоритма Евклида. Конечно, эта программа будет более громоздкой, чем функциональная схема рис. 14, но зато ее получение не требует никакой особой изобрета­ тельности.

Коль скоро мы намерены пользоваться входным языком, то вместо четырех частных типов программирующих алго­ ритмов удобнее говорить о едином, объединяющем их, про­ граммирующем алгоритме, который по любой формуле входного языка строит соответствующую ей тыорингову программу. Естественно, предполагается, что наряду с фор­ мулой входного языка заданы и тьюрииговы программы для «элементарных» алгоритмов, встречающихся в формуле.

§11. РЕКУРСИВНЫЕ ФУНКЦИИ

ИФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ

11.1Вычисление функций и алгоритмические пробле­ мы. В этом параграфе речь идет о числовых функциях одно­ местных, т. е. от одной переменной, или, многоместных, т. е. от многих переменных; предполагается, что значениями са­ мой функции, а также ее аргументов являются натуральные числа. Числовую функцию / будем называть вычислимой по Тьюрингу, если существует машина Тьюринга, вычисля­ ющая ее. Конечно, аккуратное определение функции, вы­ числимой по Тьюрингу, должно содержать указание на то,

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

ления топ же функции с использованием десятичного пред­ ставления. Для этого достаточно представить У в виде по­ следовательной композиции трех программ: программы перевода из десятичной системы в унарную, программы % программы перевода из унарной системы в десятичную. (Здесь напрашивается сравнение с электронными вычис­ лительными машинами, работающими в двоичной системе счисления; в них имеется устройство, или программа, для переработки исходных данных из десятичной системы в дво­ ичную, а также устройство, или программа, для перевода окончательной программы опять в десятичную систему.) Что

где х, у, г — изображения соответствующих чисел в избран­ ной системе представления, а * — некоторый специальный символ (разделительный знак). Полезно заметить, что хотя мы намерены уделять главное внимание вычислению число­ вых функций, тем не менее это не ограничивает по существу природы алгоритмических проблем, решаемых на машинах Тьюринга. Дело в том, что если зафиксирован алфавит Л из г букв, то всякое слово R в этом алфавите может рассмат­ риваться как запись некоторого натурального числа в г-н системе счисления. Это позволяет интерпретировать исход­ ные данные, изображенные в виде слова R, как некое первона­ чально заданное натуральное число*1 . Поскольку такое же замечание можно сделать и относительно слова, изобра­ жающего результирующие данные, то ясно, что алгоритм поиска решения задачи можно интерпретировать как ал­ горитм вычисления значения числовой функции по заданно­ му значению ее аргумента. Подобная арифметическая интер­ претация (или короче — арифметизация) часто применяется в математической логике и теории алгоритмов; мы с ней еще встретимся в данном параграфе. Уже в предыдущих пара­ графах были составлены тыоринговы программы или разъяс­ нено, как можно составить таковые для вычисления суммы х + у, произведения х X у и т. п. Мы могли бы без труда

*> Применительно к реальным вычислительным машинам обычно употребляют такие выражения, как «в памяти машины хранятся 1000 24-разрядиых двоичных чисел» и т. п. Ясно, что под числами здесь имеются в виду двоичные слова соответствующей длины. Ма­ шине и впрямь безразлично, интерпретируются ли эти слова как двоичные записи чисел или как записи какой-нибудь другой нечисло­ вой информации.

100

увеличить их список и построить программы для многих других часто встречаемых числовых функций (например, для одноместных функций х2, х3, 2х, х\, для двумест­ ной функции xv и т. п.). Однако для более ясного представ­ ления о том, какие функции вычислимы по Тьюрингу (и как строятся соответствующие программы), целесообразно по­ ступать следующим образом. А1ы рассмотрим ряд естест­ венных н обычно употребляемых операторов, т. е. способов образования новых фунщнй, исходя из ранее определенных функций, и попытаемся выяснить: можно ли (и как?) соста­ вить программы для новых функций, коль скоро уже по­ строены программы для исходных функций?

Применяя входной язык и программирующие алгоритмы, описанные в предыдущем параграфе, мы сравнительно легко обнаружим, что в ряде важных случаев действительно удает­ ся построить такие программы. Тем самым выяснится, что класс тыориигово вычислимых функций необычайно широк и охватывает все функции, которые описываются посред­ ством так называемых индуктивных определений, основан­ ных на переходе от п к п + 1. Такие определения называют еще рекуррентными, что в буквальном смысле означает «возвратное определение» (от латинского слова recurso — бегу назад, возвращаюсь). Так как самое построение нату­ ральных чисел носит рекурсивный, т.,е. возвратный ха­ рактер (чтобы определить число 4, нужно сначала опреде­ лить число 3, чтобы определить число 3, нужно сначала определить 2 и т. д. вплоть до 1), то и определение числовых функций при помощи «возвращения» от неизвестного к из­ вестному весьма естественно. Именно так обычно опреде­ ляются или могут быть определены наиболее употребитель­ ные в арифметике и теории чисел функции: сумма, произ­ ведение, число сочетаний из т элементов по п и т. д. Воз­ можны различные варианты рекурсивных определений, все они, однако, естественным образом объединяются в оп­ ределении рекурсивной функции (точнее—общерекурсивной или частично-рекурсивной функции, в зависимости от того, предполагается ли, что функция всюду определена пли нет). Итак, будет показано, что класс тыорингово вычислимых функций настолько широк, что ои охватывает все рекурсивные функции. Переходим к реализации наме­ ченного плана.

Ниже всюду обозначения вида 21, имеют следующий смысл: тыорингова программа, вычисляющая функцию f.

101

Наша ближайшая цель - описать операторы трех ти­ пов — простейшие, примитивной рекурсии и (.i-оператор — и показать, что класс вычислимых функции замкнут отно­ сительно этих операторов. Иначе говоря, если мы распо­ лагаем программами 21,,, -lf! ( ... и функция / получается в результате применения какого-нибудь из указанных опе­ раторов к функциям fv /2 , то может быть построена

ипрограмма

П.2 Простейшие операторы. К ним относятся операторы супер­ позиции н введения фиктивных аргументов. Хотя мы рассматриваем здесь эти операторы применительно к функциям, аргументы и зна­ чения которых — натуральные числа, на самом деле они имеют смысл для функций с любыми областями задания н значении. Путем введе­ ния фиктивных аргументов заданная функция I может быть преоб­ разована в функцию h от большего числа аргументов; фиктивность (несущественность) вновь присоединенных аргументов означает, что при их изменении значение функции не изменяется (коль скоро за­ фиксированы значения «старых» аргументов).

Например, по заданной одноместной функции [t (х) определяем двуместную функцию Л условием h (х, y) — f, (х). Можно ввести одно­ временно несколько фиктивных переменных, например h (х, у , и, v) =>

переменными. Однако такое различение не только полезно, но во многих случаях и необходимо. В частности, как будет видно даль­ ше, за счет введения фиктивных переменных можно достичь боль­

сложные функции, или функции от функций); в этом и заключается

и несколько сложнее, строится программа в случае суперпозиции

102

Вовсе не обязательно, чтобы функции [л , [ 2 , ... (внутренние функ­ ции суперпозиции) зависели от одних и тех же аргументов или даже, чтобы число аргументов было у них одним и тем же. Пусть, напри­

лано выше. Однако здесь удобнее поступать иначе. Сначала состав­

=Ъ (*. и, г),

получаемых введением фиктивных переменных. Далее строим про­ грамму 3(ф исходя из «стандартной» суперпозиции

лись так называемые инфиксные обозначения, в которых функ­

J 03