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

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

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

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

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

Определение

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

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

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

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

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

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

Если определено, то программа завершится на вводе со значением, сохраненным в памяти компьютера. ${\ displaystyle f (\ mathbf {x})}$ $\mathbf {x}$ ${\ displaystyle f (\ mathbf {x})}$
Если не определено, то программа никогда не завершается на входе . ${\ displaystyle 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 $определяется$ f $(n) тогда$ и только тогда, когда $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 ^k → N , f ( n ₁ ,... n _k ) := n .
Сложение f : N ² → N , f ( n ₁ , n ₂ ) := n ₁ + n ₂
Наибольший общий делитель двух чисел
Коэффициент Безу из двух чисел
Наименьший простой делитель числа

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

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

Функция f такая, что f ( n ) = 1, если в десятичном разложении числа $π$ существует последовательность не менее n последовательных пятерок , и 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), ..., Σ( н ).

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

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

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

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

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

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

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

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

В функции, определенной рекурсивным определением , каждое значение определяется фиксированной формулой первого порядка других, ранее определенных значений той же функции или других функций, которые могут быть просто константами. Их подмножеством являются примитивно-рекурсивные функции . Каждая такая функция является доказуемо полной: для такой k-арной функции f каждое значение может быть вычислено, следуя определению в обратном порядке, итеративно, и после конечного числа итераций (что можно легко доказать) достигается константа. $f(n_{1},n_{2}...n_{k})$

Обратное неверно, поскольку не каждая доказуемо полная функция является примитивно-рекурсивной. Действительно, можно перечислить все примитивно-рекурсивные функции и определить функцию en такую , что для всех n , m : en ( n , m ) = fn ₍ m ), где fn — _n -я примитивно-рекурсивная функция (для k -арных функций, это будет установлено в f _n ( m , m ... m )). Теперь g ( n ) = en ( n , n )+1 доказуемо тотально, но не примитивно рекурсивно, по аргументу диагонализации : если бы существовал j такой, что g = f _j , мы бы получили g ( j ) = en ( j , j )+1 = f _j ( j )+1= g ( j )+1, противоречие. ( Числа Гёделя всех примитивно-рекурсивных функций могут быть перечислены примитивно-рекурсивной функцией, а значения примитивно-рекурсивных функций — нет.)

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

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

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

Если все вычислимые функции перечисляются с помощью машин Тьюринга, которые их производят, то приведенное выше утверждение можно продемонстрировать, если система доказательства надежна, с помощью аргумента диагонализации, аналогичного использованному выше, с использованием перечисления доказуемо полных функций, приведенного ранее. Используется машина Тьюринга, которая перечисляет соответствующие доказательства, и для каждого входа 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-рекурсивной функции.

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

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