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

Вычислимые функции — это множество функций вида, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию. В качестве множества обычно рассматривается множество — множество слов в двоичном алфавите , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение : где , а — специальный элемент, означающий неопределённость. Роль множества может играть множество натуральных чисел, к которому добавлен элемент , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.Удобно считать, что в качестве могут выступать различные счётные множества — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества и чтобы задача распознавания корректных описаний была вычислима.Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите . В данном определении вместо исполнителя машин Тьюринга можно взять один из Тьюринг-полных исполнителей.Грубо говоря, «эталонным исполнителем» может быть некоторый абстрактный компьютер, подобный используемым персональным компьютерам, но с потенциально бесконечной памятью и особенностями архитектуры, позволяющими использовать эту бесконечную память. Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида несчётно, если счётно.Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций.Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность.