Вычислимая Функция

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

Church), С. Клини (S. Kleene), Э. Постом (Е. Post), А. Тьюрингом (A. Turing) и А. А. Марковым. Общая идея различных подходов к созданию строгих математич. Определений рассматриваемых понятий такова. Проводится детальный анализ уже известных или мыслимых вычислительных процессов, выявляются существенные особенности этих процессов, находятся подходящие математич. Аналоги этих процессов и их особенностей. Реализация различных аспектов этой идеи неоднозначна и приводит к разным вариантам мате-матич. Понятия алгоритма. Основными математич. Моделями понятия алгоритма являются машины Тьюринга, частично рекурсивные функции, нормальные алгоритмы Маркова и др. Машины Тьюринга. Алгоритмы, применяемые в математике, напоминают машину, работающую отдельными тактами и выдающую ответ через конечное число тактов.

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

где - один из символов движения Л, П или С. Конфигурация машины Мв данный момент времени кодируется словом вида где Аи В - нек-рые слова в алфавите (вместо пустого слова Апишут а 0). Конфигурация машины Мв следующий момент времени (после выполнения одного такта работы) также кодируется словом, к-рое зависит от команды . если D = Л, то получается слово если D=С, то получается слово если D = П и В = a р В', то получается слово если D = П и В - пустое слово, то получается слово Aaka0ql B. Работа машины Мможет быть описана следующим образом. Кодируют исходные данные с помощью нек-рой начальной конфигурации (здесь ). Согласно программе машины Мполучают следующую конфигурацию и т. Д., если в какой-либо момент получают конфигурацию, содержащую конечное состояние , то прекращают работу.

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

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

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