Вычислимые функции - NiNa.Az

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

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

В упрощённом виде в качестве множества ${\displaystyle N}$ обычно рассматривается ${\displaystyle B^{*}}$ — множество слов в двоичном алфавите ${\displaystyle B=\{0,1\}}$. Это не снижает общности рассмотрения функций с точки зрения разрешимости, если результатом вычисления может быть не только некоторое слово, но и специальное значение — «неопределённость», соответствующее случаю, когда алгоритм вычисления аргумента функции на некотором множестве аргументов «зависает» — то есть никогда не выдает результат. Таким образом, можно дать следующее определение вычислимой функции ${\displaystyle N}$:

${\displaystyle N=B^{*}\cup \{\top \}}$,

где ${\displaystyle B=\{0,1\}}$, а ${\displaystyle \top }$ — специальный элемент, означающий неопределённость.

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

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

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

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

Поэтому и множество вычислимых функций счётно, в то время как множество функций вида ${\displaystyle f\colon N\to N}$ несчётно, даже если ${\displaystyle N}$ счётно.

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

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

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

Литература

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

Ссылки

• Курсы по теории вычислимости