«Вычислимая функция»

одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует Алгоритм, перерабатывающий всякий объект х, для которого определена функция f,в объект f(x) и не применимый ни к какому x, для которого f не определена. Примеры: х — натуральное число, f(x) = х²; x — пара рациональных чисел x₁ и x₂, f(x) = x₁: x₂ (эта функция определена лишь для тех x, у которых x₂ ≠0); X — пара матриц (См. Матрица) X₁ и X₂ с целочисленными элементами, f(X) = X₁X₂ (эта функция определена лишь для тех X, у которых число стоблцов в X₁ совпадает с числом строк в X₂). Аргументами и значениями В. ф. могут быть лишь так называемые конструктивные объекты (см. Конструктивное направление в математике) (ибо лишь с такими объектами могут оперировать алгоритмы); таким образом, функция f такая, что f(x) ≡ х не является вычислимой, если её рассматривать на всей действительной прямой, но является вычислимой, если её рассматривать как функцию натурального или рационального аргумента. В. ф., областью определения которой служит натуральный ряд, называется вычислимой последовательностью.

В. А. Успенский.

computable function

calculable function

ВЫЧИСЛИМАЯ ФУНКЦИЯ

одно из основных понятий теории алгоритмов. См. Алгоритм.

функция, вычисление значений к-рой может быть проведено с помощью заранее заданной эффективной процедуры, или алгоритма. Характерная черта вычислительных процессов - вычисление искомых величин задач происходит последовательно из данных исходных величин по определенным, заранее заданным, правилам и инструкциям. На основании многочисленных примеров вычислительных процессов в математике оформилось интуитивное понятие вычислительной процедуры. В связи с общей программой обоснования математики в 20 в. возникла задача создания не интуитивного, а точного понятия алгоритма. Строгое определение В. ф., эффективных процедур и алгоритмов было дано в различных формах Д. Гильбертом (D. Hilbert), К. Гёделем (К. Godel), А. Чёрчем (A. Church), С. Клини (S. Kleene), Э. Постом (Е. Post), А. Тьюрингом (A. Turing) и А. А. Марковым.

Общая идея различных подходов к созданию строгих математич. определений рассматриваемых понятий такова: проводится детальный анализ уже известных или мыслимых вычислительных процессов, выявляются существенные особенности этих процессов, находятся подходящие математич. аналоги этих процессов и их особенностей.

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

Машины Тьюринга. Алгоритмы, применяемые в математике, напоминают машину, работающую отдельными тактами и выдающую ответ через конечное число тактов. А. Тьюринг и Э. Пост описали понятия вычислительных машин абстрактных, на к-рых можно моделировать вычислительные процессы. Машина Тьюринга (иногда говорят машина Тьюринга - Поста) Мсостоит из:

конечного алфавита где произвольные символы; конечные упорядоченные последовательности символов алфавита наз. словами в алфавите ; с помощью слов в алфавите кодируются исходные данные задачи, промежуточные вычисления и получаемые ответы;

конечного списка элементарных состояний, в к-рых машина Мможет находиться; при этом считается начальным состоянием, в к-ром находится М, когда начинает работу, а - конечным состоянием: если Мприходит в состояние , то она останавливает свою работу;

программы, составленной из отдельных команд , имеющих один из видов: где - один из символов движения Л, П или С.

Конфигурация машины Мв данный момент времени кодируется словом вида где Аи В - нек-рые слова в алфавите (вместо пустого слова Апишут а ₀). Конфигурация машины Мв следующий момент времени (после выполнения одного такта работы) также кодируется словом, к-рое зависит от команды:

если D = Л, то получается слово

если D=С, то получается слово

если D = П и В = a _р В', то получается слово

если D = П и В - пустое слово, то получается слово Aa_ka₀q_l B.

Работа машины Мможет быть описана следующим образом: кодируют исходные данные с помощью нек-рой начальной конфигурации (здесь ); согласно программе машины Мполучают следующую конфигурацию и т. д., если в какой-либо момент получают конфигурацию, содержащую конечное состояние , то прекращают работу; заключительная конфигурация декодируется в ответ; если машина никогда не останавливается, то считают ответ в задаче неопределенным.

Всякая вычислительная процедура, к-рая может быть сведена к работе подходящей машины Тьюринга, является эффективной в интуитивном смысле. Обращение предыдущего высказывания получило название т е-з и с а Тьюринга: всякая эффективная вычислительная процедура может быть реализована на соответствующей машине М. Этот тезис нельзя доказать, так как он объединяет два понятия - строгое математич. понятие машины Тьюринга и расплывчатое, интуитивное понятие эффективной процедуры. Если моделировать на машинах Тьюринга вычисление значений функции, области определения и значений к-рой суть множества натуральных чисел, то приходят к понятию вычислимой (на машинах Тьюринга) функции. См. также Тьюринга машина.

Частично рекурсивные функции. Все известные примеры алгоритмов можно свести к вопросу вычисления значений подходящей функции. Считая эту черту алгоритмов основной, А. Чёрч, К. Гёдель и С. Клини выделили широкий класс функций, названных частично рекурсивными. Пусть F - класс частичных функций, области определения и значения к-рых суть множества натуральных чисел. На множестве Fопределяют следующие операции:

суперпозиция функций: если то говорят, что функция

получается из с помощью суперпозиции; m-оператор: пусть говорят, что функция получается из и с помощью , и записывают

если и определены п неравны между собой при , а

Ясно, что если эти операции применяются к функциям, значение к-рых мы умеем вычислять, то имеются алгоритмы, вычисляющие значения функций и Следующие функции считаются простейшими: и

Имеются легкие алгоритмы, вычисляющие значения простейших функций.

Функция f наз. частично рекурсивной, если она за конечное число шагов может быть получена из простейших с помощью суперпозиции и -оператора. Всюду определенная частично рекурсивная функция наз. общерекурсивной. Значение всякой частично рекурсивной функции может быть вычислено эффективно в интуитивном смысле. Обращение этого высказывания. получило название тезиса Чёрча: всякая функция, значение к-рой может вычисляться эффективно, является частично рекурсивной. Таким образом, согласно тезису Чёрча, вычислимыми функциями являются частично рекурсивные функции.

Нормальные алгорифмы Маркова. Всякий конкретный алгоритм имеет дело с нек-рым алфавитом, и решение конкретной задачи сводится к переработке слов данного алфавита по нек-рым заранее заданным правилам. Такой подход к теории алгоритмов развит А. А. Марковым, предложившим концепцию нормального алгорифма в качестве математич. модели понятия вычислительной процедуры.

Нормальный алгорифм j состоит из нек-рого алфавита и конечного упорядоченного списка правил вида , где - нек-рые слова в алфавите . Часть правил выделена и названа заключительными. Правило применяется к слову Рследующим образом: слово Рпредставляется в виде , где и - слова в алфавите , возможно пустые, и из всех таких представлений выбирается то, в к-ром слово Qимеет наименьшую длину; тогда результатом применения данного правила к слову Рназ. слово QBR. Нормальный алгорифм применяется к слову Рследующим образом: применяют к слову Рпервое правило из тех, к-рые к Рможно применить, получают слово ; применяют к первое правило из тех, к-рые к можно применить, получают слово и т. д. В результате получается последовательность слов, к-рая обрывается после применения какого-либо заключительного правила.

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

Обращение этого высказывания носит название тезиса Маркова: всякая эффективная вычислительная процедура может быть промоделирована с помощью подходящего нормального алгорифма. Если моделировать с помощью нормальных алгорифмов вычисление значений функций из класса F, то приходят к еще одному понятию вычислимой функции. Были предложены и другие уточнения понятия алгоритмов (см. Алгоритм, а также Нормальный алгорифм).

Доказан следующий результат о равносильности различных концепций понятия алгоритма: классы функций, вычислимых на машинах Тьюринга, частично рекурсивных функций, вычислимых с помощью нормальных алгорифмов Маркова (аналогичные классы функций при других концепциях понятия алгоритма), совпадают. По мнению большинства современных математиков, этот класс функций адекватен классу интуитивно В. ф. и отождествляется с ним. Такое ¹ отождествление позволяет придать математичность алгоритмическим проблемам.

Лит.:[1] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [3] Тuring A. M., "Ргос. London Math. Soc.", 1937, v. 42, № 2, p. 230-65; [4] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [5] Марков А. А., Теория алгорифмов, М., 1954 ("Тр. матем. ин-та АН СССР", т. 42).

И. А. Лавров, А. Д. Тайманов.

calculable function

обчи́слювана фу́нкція

обчи́слювана фу́нкція