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

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

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

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

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

Определение

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

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

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

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

Эквивалентно, вычислимые функции могут быть формализованы как функции, которые могут быть вычислены идеализированным вычислительным агентом, таким как машина Тьюринга или регистровая машина . Формально говоря, частичная функция может быть вычислена тогда и только тогда, когда существует компьютерная программа со следующими свойствами: $f:\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 {Синий}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 должна быть вычислимой.)
Каждый конечный сегмент невычислимой последовательности натуральных чисел (такой как функция Busy Beaver Σ) является вычислимым. Например, для каждого натурального числа n существует алгоритм, который вычисляет конечную последовательность Σ(0), Σ(1), Σ(2), ..., Σ( n ) — в отличие от того факта, что не существует алгоритма, который вычисляет всю Σ-последовательность, т. е. Σ( n ) для всех n . Таким образом, «Print 0, 1, 4, 6, 13» — это тривиальный алгоритм для вычисления Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); аналогично, для любого заданного значения n существует такой тривиальный алгоритм (даже если он может быть никогда не известен или не создан никем) для вычисления Σ(0), Σ(1), Σ(2), ..., Σ( n ).

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

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

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

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

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

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

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

Отношение к рекурсивно определенным функциям

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

^ Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Elsevier. стр. 209. ISBN 0-12-238452-0.
^ Эндертон, Герберт (2002). Математическое введение в логику (второе изд.). США: Elsevier. стр. 208,262. ISBN 0-12-238452-0.
^ CJ Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Исследования по логике и основам математики, 2000), стр. 4
^ R. Soare, Computability and Recursion (1995). Доступ 9 ноября 2022 г.
^ Петер, Рожа (1935). «Конструкция nichtrekursiver Funktionen». Математические Аннален . 111 : 42–60. дои : 10.1007/BF01472200. S2CID 121107217.

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