Математическая энциклопедия - вычислимая функция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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