ВЫЧИСЛИМАЯ ФУНКЦИЯ это:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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


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

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

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

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

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

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

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ВЫЧИСЛИМАЯ ФУНКЦИЯ" в других словарях:

  • ВЫЧИСЛИМАЯ ФУНКЦИЯ — одно из основных понятий теории алгоритмов. См. Алгоритм. Философская Энциклопедия. В 5 х т. М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960 1970 …   Философская энциклопедия

  • вычислимая функция — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN computable function …   Справочник технического переводчика

  • Вычислимая функция —         одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует Алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект f (x) и не применимый ни к какому x, для которого f не… …   Большая советская энциклопедия

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

  • РЕКУРСИВНАЯ ФУНКЦИЯ — ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я, одно из математич. уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями.… …   Математическая энциклопедия

  • Существование перечислимого неразрешимого множества — В данной статье будет доказан теорема о существовании перечислимого, но неразрешимого множества. Напомню, что по теореме Поста перечислимое множества разрешимо тогда и только тогда, когда его дополнение перечислимо.Основные определения, такие как …   Википедия

  • РЕКУРСИВНАЯ ТЕОРИЯ МНОЖЕСТВ — раздел тео рии рекурсивных функций, в к ром рассматриваются и классифицируются подмножества натуральных чисел с алгоритмич. точки зрения, а также исследуются структуры, возникающие в результате такой классификации. Для каждого множества А, к рое… …   Математическая энциклопедия

  • АЛГОРИТМА СЛОЖНОСТЬ — вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… …   Математическая энциклопедия

  • Константа Чейтина — Эта статья или секция грубый перевод статьи на другом языке (см. Проверка переводов). Он мог быть генерирован программой переводчиком или человеком со слабыми познаниями в языке статьи оригинала Пожалуйста, не поленитесь улучшить перевод.… …   Википедия

  • Константа Хайтина — Эта статья или раздел  грубый перевод статьи на другом языке (см. Проверка переводов). Он мог быть сгенерирован программой переводчиком или сделан человеком со слабыми познаниями в языке оригинала. Вы можете помочь …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»