WikiSort.ru - Не сортированное

Эту страницу предлагается объединить со страницей Рекурсивная функция (теория вычислимости). Пояснение причин и обсуждение — на странице Википедия:К объединению/27 апреля 2016. Обсуждение длится не менее недели (подробнее). Не удаляйте шаблон до подведения итога обсуждения.

Вычислимые функции — это множество функций вида, ${\displaystyle f\colon N\to N,}$ которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции ${\displaystyle f}$ называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможно ли написать алгоритм, вычисляющий эту функцию.

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

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

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

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

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

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида ${\displaystyle f\colon N\to N,}$ несчётно, если ${\displaystyle N}$ счётно. Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций. Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность.

История

Понимание, что часть функций вида ${\displaystyle f\colon B^{*}\to B^{*}}$ вычислима, а часть нет, появилось ещё до появления первых компьютеров. Теория вычислимости берёт своё начало от диссертации Тьюринга (1936), в которой он ввёл понятие абстрактной вычислительной машины, и функций, вычислимых на ней. По мере развития теории вычислимости было сформулировано несколько определений, которые, как оказалось впоследствии, определяют одно и то же множество функций — множество вычислимых функций:

• функции, реализуемые на машинах Тьюринга (Алан Тьюринг);
• функции, реализуемые на нормальных алгоритмах Маркова (А. А. Марков);
• функции, реализуемые на машине Поста;
• частично рекурсивные функции (Курт Гёдель, Стивен Клини);
• функции, реализуемые на регистровой машине^{[[[Шаблон:Не переведено#Действия после появления перевода|убрать шаблон]]]}.

См. также

• Тезис Чёрча — Тьюринга
• Полнота по Тьюрингу
• Частично рекурсивные функции
• Общерекурсивные функции
• Примитивно рекурсивные функции
• Разрешимые множества
• Перечислимые множества
• Невычислимые функции (алгоритмически неразрешимые проблемы):

• Проблема остановки
• Проблема эквивалентности алгоритмов
• Проблема доказательства верности или неверности утверждения
• Десятая проблема Гильберта — разрешимость диофантова уравнения в целых числах
• Самоприменимость

Ссылки

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

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 2 ноября 2016 года.