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

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

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

До точного определения вычислимой функции математики часто использовали неформальный термин «эффективно вычислимая» . С тех пор этот термин стал отождествляться с вычислимыми функциями. Эффективная вычислимость этих функций не означает, что их можно эффективно вычислить (т. е. вычислить за разумное время). Фактически, для некоторых эффективно вычисляемых функций можно показать, что любой алгоритм, который их вычисляет, будет очень неэффективен в том смысле, что время работы алгоритма увеличивается экспоненциально (или даже суперэкспоненциально ) с длиной входных данных. Области допустимой вычислимости и вычислительной сложности изучают функции, которые можно эффективно вычислить.

Аксиомы Блюма можно использовать для определения абстрактной теории сложности вычислений на множестве вычислимых функций. В теории сложности вычислений проблема определения сложности вычислимой функции известна как функциональная задача .

Определение

Вычислимость функции — неформальное понятие. Один из способов описать это — сказать, что функция вычислима, если ее значение можно получить с помощью эффективной процедуры . Более строго, функция $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ вычислим тогда и только тогда, когда существует эффективная процедура, которая для любого $k$ - кортежа $\mathbf {x}$ натуральных чисел, даст значение $f(\mathbf {x} )$ . ^[1] В соответствии с этим определением в оставшейся части статьи предполагается, что вычислимые функции принимают в качестве аргументов конечное число натуральных чисел и возвращают значение, которое представляет собой одно натуральное число.

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

Машины Тьюринга
μ-рекурсивные функции
Лямбда-исчисление
Почтовые машины ( машины Пост-Тьюринга и меточные машины ).
Регистрация машин

Хотя эти модели используют разные представления функций, их входных и выходных данных, между любыми двумя моделями существуют преобразования, и поэтому каждая модель описывает по существу один и тот же класс функций, что порождает мнение, что формальная вычислимость является одновременно естественной и не слишком узкий. ^[2] Эти функции иногда называют «рекурсивными», в отличие от неформального термина «вычислимые». ^[3] это различие вытекает из дискуссии 1934 года между Клини и Гёделем. ^[4]^стр.6

Например, можно формализовать вычислимые функции как µ-рекурсивные функции , которые являются частичными функциями , которые принимают конечные кортежи и натуральных чисел возвращают одно натуральное число (как и выше). Это наименьший класс частичных функций, который включает функции константы, преемника и проекции и замкнут при композиции , примитивной рекурсии и операторе μ .

Эквивалентно, вычислимые функции могут быть формализованы как функции, которые могут быть вычислены идеализированным вычислительным агентом, таким как машина Тьюринга или регистровая машина . Формально говоря, частичная функция $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ можно вычислить тогда и только тогда, когда существует компьютерная программа со следующими свойствами:

Если $f(\mathbf {x} )$ определено, то программа завершится на вводе $\mathbf {x}$ со значением $f(\mathbf {x} )$ хранится в памяти компьютера.
Если $f(\mathbf {x} )$ не определено, то программа никогда не завершается на вводе $\mathbf {x}$ .

Характеристики вычислимых функций

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

Эндертон [1977] дает следующие характеристики процедуры вычисления вычислимой функции; аналогичные характеристики были даны Тьюрингом [1936], Роджерсом [1967] и другими.

«Для процедуры должны существовать точные инструкции (т.е. программа) конечной длины». Таким образом, каждая вычислимая функция должна иметь конечную программу, которая полностью описывает, как функция должна быть вычислена. Функцию можно вычислить, просто следуя инструкциям; не требуется никаких догадок или особого понимания.
«Если процедуре задан k -кортеж x в области определения f , то после конечного числа дискретных шагов процедура должна завершиться и выдать f ( x )». Интуитивно понятно, что процедура выполняется шаг за шагом с конкретным правилом, описывающим, что делать на каждом этапе расчета. Только конечное число шагов может быть выполнено, прежде чем функция вернет значение.
«Если процедуре задан k -кортеж x, который не находится в области определения f , то процедура может продолжаться вечно, никогда не останавливаясь. Или она может застрять в какой-то момент (т. е. одна из ее инструкций не может быть выполнена) , но он не должен претендовать на получение значения f в точке x ». Таким образом, если значение f ( x ) когда-либо будет найдено, оно должно быть правильным значением. Вычислительному агенту не обязательно отличать правильные результаты от неправильных, поскольку процедура определяется как правильная тогда и только тогда, когда она дает результат.

Эндертон далее перечисляет несколько пояснений к этим трем требованиям процедуры для вычислимой функции:

Теоретически процедура должна работать для сколь угодно больших аргументов. Не предполагается, что аргументы меньше, чем, например, количество атомов в Земле.
Чтобы получить результат, процедура должна остановиться после конечного числа шагов, но перед остановкой она может выполнить произвольное количество шагов. Никаких ограничений по времени не предполагается.
Хотя во время успешного вычисления процедура может использовать только ограниченный объем памяти, объем используемого пространства не ограничен. Предполагается, что процедуре может быть предоставлено дополнительное пространство для хранения всякий раз, когда процедура этого требует.

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

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

Область вычислительной сложности изучает функции с заданными ограничениями на время и/или пространство, допускаемые при успешном вычислении.

Вычислимые множества и отношения

Множество $натуральных чисел A$ называется вычислимым (синонимы: рекурсивный , разрешимый ), если существует вычислимая полная функция $f$ такая, что для любого натурального числа $n$ , $f (n) = 1$ если $n$ находится в $A$ и $f (n) = 0,$ n $не$ находится в $A.$ если

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

$B$ — область определения вычислимой функции.
$B$ — образ полной вычислимой функции. Если $B$ бесконечно, то функцию можно считать инъективной .

Если набор $B$ является диапазоном функции $f$ , то функцию можно рассматривать какперечисление $B$ , потому что список $f (0), f (1), ...$ будет включать каждый элемент $B$ .

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

Формальные языки

В теории вычислимости в информатике принято рассматривать формальные языки . Алфавит – это произвольный набор. Слово алфавита — это конечная последовательность символов алфавита; один и тот же символ может использоваться более одного раза. Например, двоичные строки — это в точности слова алфавита ${0, 1}$ . Язык . — это подмножество совокупности всех слов фиксированного алфавита Например, совокупность всех двоичных строк, содержащих ровно 3 единицы, представляет собой язык, основанный на двоичном алфавите.

Ключевым свойством формального языка является уровень сложности, необходимый для принятия решения о том, присутствует ли данное слово в этом языке. Необходимо разработать некоторую систему кодирования, позволяющую вычислимой функции принимать на вход произвольное слово языка; обычно это считается рутиной. Язык называется вычислимым (синонимы: рекурсивный , разрешимый ), если существует вычислимая функция $f$ такая, что для каждого слова $w$ в алфавите $f (w) = 1$ , если слово находится в языке, и $f (w) = 0$ , если этого слова нет в языке. Таким образом, язык является вычислимым только в том случае, если существует процедура, способная правильно определить, присутствуют ли в языке произвольные слова.

Язык является вычислимо перечислимым (синонимы: рекурсивно перечислимый , полуразрешимый ), если существует вычислимая функция $f$ такая, что $f (w)$ определена тогда и только тогда, когда слово $w$ есть в языке. Термин «перечислимый» имеет ту же этимологию, что и термин «вычислимо перечислимые множества натуральных чисел».

Примеры

Следующие функции вычислимы:

Каждая функция с конечной областью определения ; например, любая конечная последовательность натуральных чисел.
Каждая постоянная функция f : N ^к → N , ж ( п ₁ ,... п _k ) знак равно п .
Дополнение f : N ² → N , ж ( п ₁ , п ₂ ) := п ₁ + п ₂
Наибольший общий делитель двух чисел
Коэффициент Безу из двух чисел
Наименьший простой делитель числа

Если f и g вычислимы, то вычислимы также: f + g , f * g , $\color {Blue}f\circ g$ если f унарный ) , max( f , g ), min( f , g , $arg max {y \leq f (x)}$ и многие другие комбинации.

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

Функция f такая, что f ( n существует последовательность не менее n ) = 1, если в десятичном разложении числа $π$ последовательных пятерок , и f ( n ) = 0 в противном случае, является вычислимой. (Функция f — это либо функция с константой 1, которая вычислима, либо существует k такое, что f ( n ) = 1, если n < k, и f ( n ) = 0, если n ≥ k . Каждая такая функция вычислима. Неизвестно, есть ли в десятичном разложении π сколь угодно длинные серии пятерок, поэтому мы не знаем, какая из этих функций является f . Тем не менее мы знаем, что функция f должна быть вычислимой.)
Каждый конечный сегмент невычислимой последовательности натуральных чисел (такой как функция Бизи Бивера Σ) вычислим. Например, для каждого натурального числа n существует алгоритм, который вычисляет конечную последовательность Σ(0), Σ(1), Σ(2), ..., Σ( n ) — в отличие от того факта, что не существует алгоритм, который вычисляет всю Σ-последовательность, т.е. Σ( n ) для всех n . Таким образом, «Напечатать 0, 1, 4, 6, 13» — это тривиальный алгоритм вычисления Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); аналогично, для любого данного значения n такой тривиальный алгоритм существует (даже если он никогда не будет известен или никем не создан) для вычисления Σ(0), Σ(1), Σ(2), ..., Σ( н ).

Тезис Чёрча – Тьюринга

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

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

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

Доказуемость

Учитывая функцию (или, аналогично, набор), может интересоваться не только то, вычислима ли она, но и можно ли это доказать в конкретной системе доказательства (обычно первого порядка арифметике Пеано ). Функция, вычислимость которой может быть доказана, называется доказуемо полной .

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

Связь с рекурсивно определенными функциями

В функции, определенной рекурсивным определением , каждое значение определяется фиксированной формулой первого порядка других, ранее определенных значений той же функции или других функций, которые могут быть просто константами. Их подмножеством являются примитивно-рекурсивные функции . Другим примером является функция Аккермана , которая определяется рекурсивно, но не является примитивно-рекурсивной. ^[5]

Чтобы определения этого типа избегали цикличности или бесконечной регрессии, необходимо, чтобы рекурсивные вызовы одной и той же функции внутри определения осуществлялись с аргументами, меньшими по некоторому частичному порядку в области определения функции. Например, для функции Аккермана $A$ , всякий раз, когда определение $A(x,y)$ относится к $A(p,q)$ , затем $(p,q)<(x,y)$ относительно лексикографического порядка пар натуральных чисел . В этом случае, как и в случае примитивно-рекурсивных функций, хороший порядок очевиден, но некоторые отношения «ссылаются на» нетривиально доказать, что они являются хорошими. Любая функция, определенная рекурсивно и упорядоченным образом, вычислима: каждое значение можно вычислить путем расширения дерева рекурсивных вызовов функции, и это расширение должно завершиться после конечного числа вызовов, потому что в противном случае лемма Кенига привела бы к бесконечному числу вызовов. нисходящая последовательность вызовов, что нарушает предположение о правильном порядке.

Тотальные функции, которые не являются доказуемо полными

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

Если все вычислимые функции перечисляются с помощью машин Тьюринга, которые их производят, то приведенное выше утверждение можно продемонстрировать, если система доказательства надежна, с помощью аргумента диагонализации, аналогичного использованному выше, с использованием перечисления доказуемо полных функций, приведенного ранее. Используется машина Тьюринга, которая перечисляет соответствующие доказательства, и для каждого входа n вызывает f _n ( n ) (где f _n - n -я функция по этому перечислению), вызывая машину Тьюринга, которая вычисляет ее в соответствии с n-м доказательством. . Такая машина Тьюринга гарантированно остановится, если система доказательства работает.

Невычислимые функции и нерешаемые проблемы

Каждая вычислимая функция имеет конечную процедуру, дающую явные и недвусмысленные инструкции о том, как ее вычислить. Более того, эта процедура должна быть закодирована в конечном алфавите, используемом вычислительной моделью, поэтому существует только счетное количество вычислимых функций. Например, функции могут быть закодированы с использованием строки битов (алфавит $Σ = {0, 1$ }).

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

Точно так же большинство подмножеств натуральных чисел не вычислимы. Проблема остановки была первым построенным подобным набором. Проблема Entscheidungsproblem , предложенная Дэвидом Гильбертом , задавалась вопросом, существует ли эффективная процедура для определения того, какие математические утверждения (закодированные как натуральные числа) верны. Тьюринг и Чёрч независимо друг от друга показали в 1930-х годах, что этот набор натуральных чисел не вычислим. Согласно тезису Чёрча-Тьюринга, не существует эффективной процедуры (с алгоритмом), которая могла бы выполнять эти вычисления.

Расширения вычислимости

Относительная вычислимость

Понятие вычислимости функции можно релятивизировать произвольному набору натуральных чисел A. к Функция f считается вычислимой в A (эквивалентно A -вычислимой или вычислимой относительно A ), если она удовлетворяет определению вычислимой функции с модификациями, позволяющими получить доступ к A как к оракулу . Как и в случае с понятием вычислимой функции, относительной вычислимости можно дать эквивалентные определения во многих различных моделях вычислений. которая спрашивает, является ли данное целое число членом A. Обычно это достигается путем дополнения модели вычислений дополнительной примитивной операцией , Мы также можем говорить о том, f что вычислимо в g, отождествляя g с его графиком.

Теория высшей рекурсии

Гиперарифметическая теория изучает те множества, которые можно вычислить по вычислимому порядковому числу итераций тьюринговского скачка пустого множества. Это эквивалентно множествам, определяемым как универсальной, так и экзистенциальной формулой на языке арифметики второго порядка, а также некоторым моделям гипервычислений . Были изучены даже более общие теории рекурсии, такие как теория E-рекурсии , в которой любое множество может использоваться в качестве аргумента E-рекурсивной функции.

Гипервычисления

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

См. также

Ссылки

^ Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 209. ИСБН 0-12-238452-0 .
^ Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 208 262. ISBN 0-12-238452-0 .
^ CJ Эш, Дж. Найт, Вычислимые структуры и гиперарифметическая иерархия (Исследования в области логики и основы математики, 2000), стр. 4
^ Р. Соаре, Вычислимость и рекурсия (1995). По состоянию на 9 ноября 2022 г.
^ Петер, Рожа (1935). «Построение нерекурсивных функций». Математические летописи . 111 : 42–60. дои : 10.1007/BF01472200 . S2CID 121107217 .

Катленд, Найджел. Вычислимость . Издательство Кембриджского университета, 1980.
Эндертон, Х.Б. Элементы теории рекурсии. Справочник по математической логике (Северная Голландия, 1977), стр. 527–566.
Роджерс, Х. Теория рекурсивных функций и эффективных вычислений (McGraw – Hill 1967).
Тьюринг, А. (1937), О вычислимых числах с применением к проблеме Entscheidungs . Труды Лондонского математического общества , серия 2, том 42 (1937), стр. 230–265. Перепечатано в М. Дэвисе (редактор), The Undecidable , Raven Press, Hewlett, NY, 1965.

[1] Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 209. ИСБН 0-12-238452-0 .

[2] Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 208 262. ISBN 0-12-238452-0 .

[3] CJ Эш, Дж. Найт, Вычислимые структуры и гиперарифметическая иерархия (Исследования в области логики и основы математики, 2000), стр. 4

[4] Р. Соаре, Вычислимость и рекурсия (1995). По состоянию на 9 ноября 2022 г.

[5] Петер, Рожа (1935). «Построение нерекурсивных функций». Математические летописи . 111 : 42–60. дои : 10.1007/BF01472200 . S2CID 121107217 .

[1]

[2]

[3]

[4]

[5]

v т и Классы сложности
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes