Cтраница 1
Понятие вычислимой функции является весьма важным во всей математике и центральным - в прикладной математике. [1]
Часто при введении понятия интуитивно вычислимой функции сначала описывают понятие алгоритма ( алгоритм в интуитивном смысле - это точное предписание о выполнении в определенном порядке некоторой системы операций для решения всех задач данного типа), а затем называют интуитивно вычислимой ту функцию, для которой существует алгоритм ( в интуитивном смысле) вычисления ее значений. [2]
Одним из уточнений понятия интуитивно вычислимой функции является понятие частично рекурсивной функции, к введению которого мы приступаем. [3]
Дайте ( естественное) определение понятия вычислимой функции трех аргументов, универсальной для класса вычислимых функций двух аргументов, и докажите ее существование. [4]
Теперь мы можем воспользоваться тем, что понятие вычислимой функции было уточнено с помощью понятия регулярно вычислимой арифметической функции одного аргумента. Тогда вопрос о возможности общего решения проблемы разрешимости для исчисления предикатов приобретет следующую более точную формулировку: можно ли для исчисления предикатов и установленной для него нумерации формул указать какую-либо регулярно вычислимую разрешающую функцию. [5]
Черч высказал мнение о том, что понятием рекурсивной функции исчерпывается понятие вычислимой функции. Это мнение является гипотезой, подтверждающейся всем предыдущим опытом математиков. Она известна под названием тезиса Черча. [6]
Тезис Черча невозможно ни доказать, ни опровергнуть, так как понятие вычислимой функции не определено формально. [7]
Итак, нельзя считать, что понятие рекурсивной функции совпадает с понятием вычислимой функции. Однако определение вычислимой функции тесно связано с понятием рекурсивной функции. Вводится понятие обще-рекурсивной функции. В отличие от общерекурсивных функций, введенные выше рекурсивные функции часто называют примитивно рекурсивными функциями. [8]
Можно, однако, предполагать, что как А. А. Марков, так и авторы различных обсуждаемых нами определений понятия вычислимой функции оставляют некоторые операции неограниченного объема нерасчлененными лишь в силу очевидной возможности их расчленения на действительно элементарные шаги. [9]
Чтобы в противовес этому подозрению подчеркнуть широту введенного нами понятия, мы сравним его с другим уточнением понятия вычислимой функции, представляющим собой некоторое обобщение понятия рекурсивной функции. [10]
Полученный нами результат о представимости регулярно вычислимых арифметических функций одного аргумента при помощи термов а ( рхЬ ( п, х)) формализма ( Z) может вызвать подозрение, что понятие регулярно вычислимой функции было определено нами слишком узко. [11]
Как мы указывали выше, под термином вычисли мая функция подразумевается, что для этой функции задан алгоритм, позволяющий для каждого значения аргумента определить значение функции. Задача же состоит в уточнении понятия вычислимой функции, так как понятие алгоритма, на которое оно опирается, здесь пока употребляется лишь в интуитивном понимании, без всякого определения. Определение вычислимой функции формулируется следующим образом. [12]
Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. [13]
Уточнение это было произведено посредством трех существенно отличных друг от друга понятий, относительно которых впоследствии было установлено, что они описывают одну и ту же совокупность функций. Это - восходящее к Эрбрану и Геделю понятие общерекурсивной функции, принадлежащее Черчу и Клини понятие Я-определимой функции и введенное А. М. Тьюрингом и Э. Л. Постом понятие вычислимой функции. [14]
К пятидесятым годам относятся и замыслы Андрея Николаевича, связанные с понятием алгоритма. Их цель - дать возможно более общее математическое определение этого понятия, но так, чтобы это общее определение не привело к расширению уже сформировавшегося понятия вычислимой функции. Разработке замыслов Андрея Николаевича была посвящена дипломная работа В.А. Успенского Общее определение алгоритмической вычислимости и алгоритмической сводимости, выполненная в первой половине 1952 г. ( см. комментарий В.А. Успенского и А.Л. Семенова [ BiKH-50, с. В совместной статье А.Н. Колмогорова и В. А. Успенского 1958 го да К определению алгоритма [ Б: - 151 ] ( а также в упомянутом комментарии) дан подробный анализ развития этих идей и изложено современное состояние этой проблематики. [15]