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

(перенаправлено с «Вычислимые функции»)


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

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

В упрощённом виде в качестве множества обычно рассматривается множество  — множество слов в двоичном алфавите . Это не снижает общности рассмотрения функций с точки зрения разрешимости, если результатом вычисления может быть не только некоторое слово, но и специальное значение — «неопределённость», соответствующее случаю, когда алгоритм вычисления аргумента функции на некотором множестве аргументов «зависает» — то есть никогда не выдает результат. Таким образом, можно дать следующее определение вычислимой функции :

где , а  — специальный элемент, означающий неопределённость.

Роль множества может играть множество натуральных чисел, к которому добавлен элемент , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.

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

В качестве исполнителя алгоритма вместо машин Тьюринга можно взять один из иных Тьюринг-полных исполнителей. Грубо говоря, «абстрактным исполнителем» алгоритма может быть некоторый гипотетический компьютер, подобный персональным компьютерам, но с актуально бесконечным объёмом памяти и архитектурой, обеспечивающей обращение к этой бесконечной памяти.

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно.

Поэтому и множество вычислимых функций счётно, в то время как множество функций вида несчётно, даже если счётно.

Отсюда следует, что существуют невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций.

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

История

править

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

См. также

править

Примечания

править
  1. Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.. — 4-е изд., исправленное.. — М.: МЦНМО, 2012. — 160 с. — ISBN 978-5-4439-0014-8.

Ссылки

править