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

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

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

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

конечного алфавита α = {а₀, а₁, ..., а_n), где а_i произвольные символы; конечные упорядоченные последовательности символов алфавита α наз. словами в алфавите α; с помощью слов в алфавите α кодируются исходные данные задачи, промежуточные вычисления и получаемые ответы;

конечного списка Q = {q₀, q₁, ..., q_m) элементарных состояний, в к-рых машина М может находиться; при этом q₁ считается начальным состоянием, в к-ром находится М, когда начинает работу, а q₀ - конечным состоянием: если М приходит в состояние q₀, то она останавливает свою работу;

программы, составленной из отдельных команд T_ij, имеющих один из видов: a_iq_j → a_kDq_l, где 0 ≤ i, k ≤ n, 0 < j ≤ m, 0 ≤ l ≤ m, D - один из символов движения Л, П или С.

Конфигурация машины М в данный момент времени кодируется словом вида Аа_iй_jВ, где А и В - нек-рые слова в алфавите α (вместо пустого слова А пишут a₀). Конфигурация машины М в следующий момент времени (после выполнения одного такта работы) также кодируется словом, к-рое зависит от команды T_ij: если D = Л, то получается слово Aq_la_kB, если D = C, то получается слово Aa_kq_lB, если D = П и В = а_pВ', то получается слово Aa_ka_pq_lB', если D = П и В - пустое слово, то получается слово Aa_ka₀q_lB.

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

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

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

суперпозиция функций: если f, α₁, ..., α_m ∈ F, то говорят, что функция

φ(x₁, ..., x_n) = f (α₁(x₁, ..., x_n), ..., α_n(x₁, ..., x_n))

получается из f, α₁, ..., α_n с помощью суперпозиции;

μ-оnератор: пусть f₁, f₂ ∈ F; говорят, что функция ψ получается из f₁ и f₂ с помощью μ-оператора, и записывают

ψ(x₁, ..., x_n) = μy[f₁(x₁, ..., x_n, y) = f₂(x₁, ..., x_n, у)],

если f₁(x₁, ..., x_n, z) и f₂(x₁, ..., x_n, z) определены и неравны между собой при z < y, а

f₁(x₁, ..., x_n, y) = f₂(x₁, ..., x_n, y) и ψ(x₁, ..., x_n) = у.

Ясно, что если эти операции применяются к функциям, значение к-рых мы умеем вычислять, то имеются алгоритмы, вычисляющие значения функций φ и ψ. Следующие функции считаются простейшими: +, ×, Iⁿ_i(x₁, ..., x_n) = x_i и

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

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

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

Нормальный алгорифм φ состоит из нек-рого алфавита α = {а₀, а₁, ..., а_n) и конечного упорядоченного списка правил вида А → В, где А и В - нек-рые слова в алфавите α. Часть правил выделена и названа заключительными. Правило А → В применяется к слову Р следующим образом: слово Р представляется в виде QAR, где Q и R - слова в алфавите α, возможно пустые, и из всех таких представлений выбирается то, в к-ром слово Q имеет наименьшую длину; тогда результатом применения данного правила к слову Р наз. слово QBR. Нормальный алгорифм φ применяется к слову Р следующим образом: применяют к слову Р первое правило из тех, к-рые к Р можно применить, получают слово Р₁; применяют к Р₁ первое правило из тех, к-рые к Р₁ можно применить, получают слово Р₂ и т. д. В результате получается последовательность слов, к-рая обрывается после применения какого-либо заключительного правила.

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

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

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

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

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.