Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Определение [ править ]

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

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

Хотя эти модели используют разные представления функций, их входов и выходов, трансляции существуют между любыми двумя моделями, и поэтому каждая модель описывает по существу один и тот же класс функций, что дает повод считать, что формальная вычислимость является одновременно естественной и не слишком узкой . [2]

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

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

  1. Если задано, то программа завершится при вводе значения, сохраненного в памяти компьютера.
  2. Если не определено, то программа никогда не завершается на входе .

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

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

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

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

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

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

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

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

Вычислимые множества и отношения [ править ]

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

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

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

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

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

Формальные языки [ править ]

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

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

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

Примеры [ править ]

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

  • Каждая функция с конечной областью определения ; например, любая конечная последовательность натуральных чисел.
  • Каждая постоянная функция f  : N kN , f ( n 1 , ... n k ): = n .
  • Сложение f  : N 2N , f ( n 1 , n 2 ): = n 1 + n 2
  • Наибольший общий делитель двух чисел
  • Коэффициент Безу из двух чисел
  • Наименьший простой делитель числа

Если е и г вычислимы, то так являются: е + г , е * г , если F является Унарный , макс ( е , г ), мин ( е , г ), Arg макс { у  ≤  F ( х )} и многие больше комбинаций. ж ∘ грамм {\ displaystyle f \ circ g}

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

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

Тезис Черча – Тьюринга [ править ]

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

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

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

Возможность [ править ]

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

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

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

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

Обратное неверно, поскольку не каждая доказуемо полная функция является примитивно рекурсивной. Действительно, можно перечислить все примитивные рекурсивные функции и определить функцию о , что для все п , м : а ( п , м ) = е п ( м ), где ф п является п-й примитивно рекурсивная функция (для к -арными функциями, будет установлено значение 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 . Мы также можем говорить о е быть вычислимым в г отождествления г с графиком.

Высшая теория рекурсии [ править ]

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

Гипер-вычисление [ править ]

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

См. Также [ править ]

  • Вычислимое число
  • Эффективный метод
  • Теория вычислений
  • Теория рекурсии
  • Степень Тьюринга
  • Арифметическая иерархия
  • Гипервычисления
  • Суперрекурсивный алгоритм
  • Полувычислимая функция

Ссылки [ править ]

  1. ^ Enderton, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 209. ISBN 0-12-238452-0.
  2. ^ Enderton, Герберт (2002). Математическое введение в логику (второе изд.). США: Эльзевир. п. 208 262. ISBN 0-12-238452-0.
  • Катленд, Найджел. Вычислимость . Издательство Кембриджского университета, 1980.
  • Эндертон, Х. Б. Элементы теории рекурсии. Справочник по математической логике (Северная Голландия, 1977), стр. 527–566.
  • Роджерс, Х. Теория рекурсивных функций и эффективных вычислений (McGraw – Hill 1967).
  • Тьюринг А. (1937), О вычислимых числах, в приложении к проблеме Entscheidungs . Труды Лондонского математического общества , серия 2, том 42 (1937), стр.230–265. Перепечатано в M. Davis (ed.), The Undecidable , Raven Press, Hewlett, NY, 1965.