Функция вычислимая

Пе все функции вычислимы. Это ясно пз сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счётное множество). Более интересные примеры см. в задачах 1.3-1.5. [c.20]

Может показаться, что машины Тьюринга реализуют более широкий класс функций, чем рекурсивные. Но это не так, потому что все слова, составленные из букв внешнего алфавита, можно перенумеровать, предварительно упорядочив их лексикографически, и тем самым установить соответствие между преобразованиями слов, осуществляемыми машинами Тьюринга, и неотрицательными целочисленными функциями неотрицательных целочисленных аргументов. Доказано, что множество этих функций эквивалентно множеству рекурсивных функций. Для машин Тьюринга тем самым устанавливается тезис Тьюринга, эквивалентный тезису Черча любая вычислимая функция вычислима по Тьюрингу. [c.27]

Пусть Т(п) — максимальное время, которое может пройти до остановки машины Тьюринга с п состояниями и п символами алфавита, если её запустить на пустой ленте. Докажите, что функция Т п) растёт быстрее любой вычислимой всюду определённой функции Ь п), то есть Vn-n[T(n)/h(n)] = +ОС. [c.27]

Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима. [c.20]

По аналогии с предикатами можно определить и функции, вычислимые за полиномиальное время, и функции, вычислимые на полино- [c.22]

Понятия вычислимой функции н разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных. [c.20]

Сейчас мы будем строить такой предикат fip(x), чтобы он был разрешим, но не принадлежал Р. Мы построим такую вычислимую функцию р(п), что любой алгоритм её вычисления работает дольше, чем 2". Другими словами, есть алгоритм распознавания принадлежности языку Я, состоящему из двоичных записей тех чисел п, для которых ip(n) = 1 но время работы в наихудшем случае любого такого алгоритма на словах длины т растёт быстрее, чем 2" . [c.155]

Численные, или поисковые м е т о д ы. Для их применения нужно, чтобы целевая функция была вычислимой должен быть известен алгоритм, по которому можно рассчитать значение критерия оптимальности при заданных значениях факторов. [c.252]

Успенский В. А., Лекции о вычислимых функциях, Физматгиз, 1960. [c.378]

Функцию ДХ], Х2,. .., х ) называют вычислимой, если ее значения могут быть получены (вычислены) с помощью некоторого алгоритма. [c.23]

Рекурсивными функциями называют один частный класс вычислимых функций, который сейчас построим. [c.23]

Американский математик А. Черч высказал гипотезу о том, что понятием рекурсивной функции исчерпывается понятие вычислимой функции. Эта гипотеза известна под названием тезиса Черча какова бы ни была вычислимая неотрицательная целочисленная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей рекурсивная функция. [c.26]

Доказано, что в теоретическом отношении все три рассмотренных понятия алгоритма эквивалентны. Для нормальных алгоритмов Маркова также можно сформулировать тезис, аналогичный тезисам Черча и Тьюринга и называемый принципом нормализации-, для любой вычислимой функции существует нормальный алгоритм Маркова, вычисляющий эту функцию. [c.28]

Под предикатом будем понимать некоторое условие, которое выполняется (предикат истинен) пли пе выполняется (предикат ложен) для каждого слова из А. Определённые таким образом, предикаты легко отождествляются с языками (нодмпожествамп слов в А ) — предикату соответствует множество слов, на которых он пстинен. Каждому предикату сопоставим характеристическую функцию, которая равна 1 иа множестве слов, для которых предикат истинен, п равна О на мпоисестве слов, для которых предикат ложен. Мы будем обозначать характеристическую функцию так же, как и сам предикат. Предикат разрешим, если его характеристическая функция вычислима. О машине Тьюринга, вычисляющей характеристическую функцию предиката, будем говорить, что она даёт ответ ( да илн нет ) на вопрос истинно ли значение предиката на входе а [c.20]

Определение 1.3. Предикат / на множестве Ш принадлежит классу Р (и называется полиномиально вычислимым), если его характеристическая функция вычислима на машине Тьюринга М, для которой Тм(п) = ро1у(п). [c.22]

Определение 1.4. Предикат / на множестве Ж принадлежит классу Р8РАСЕ, если его характеристическая функция вычислима па машине Тьюринга М, для которой Нм п) = ро1у(п). [c.22]

Все три рассмотренные формализованные теории алгоритмов ведут к единому понятию вычислимых функций. Это ставит вопрос о том, являются ли все математические функции вычислимыми. Отрицательный ответ на этот вопрос получен немецким математиком и логиком К. Геделем в виде теоремы о неполноте любой непротиво-28 [c.28]

Вычислимые функции и разрешимые предикаты. Каждая машина Тьюриига М вычисляет частичную функцию (рм нз Л в А, отображающую вход а в результат работы МТ иа входе а ири условии, что результат работы является словом во внешнем алфавите. Для входов, иа которых машина не останавливается илн результат содержит символы из <5 Л, функция 1рм ие определена. Пз определения ясно. [c.19]

Определение 1.1. Частичная функция / пз А в А называется вы-чис.лимой, если сун ествует мангина Тьюринга М, для которой 1рм = / При этом будем говорить, что / вычислима на М. [c.20]

Определение 1.2. Частичная функция / из (Л )" в А называется вычислимой, если существует машина Тьюрпнга М, для которой РМ,п = / [c.20]

Сложностные классы. Не для всякой вычислимой функции можно реально осуществить вычисление её значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма. [c.22]

Докмательство. Достаточно проверить транзитивность сводимости если 1-1 ос 2, 2 ос 1-3, то 1 ос L3. Она следует из того, что композиция двух полиномиально вычислимых функций полиномиально вычислима. [c.34]

Задача о вычислении периода является частным случаем задачи о скрытой подгруппе в Z. Напомним, что реГд(а) = min i 1 а = 1 (mod q) . Фунцня J х i-> а"" mod q удовлетворяет условию (12.1), где D = т реГд(а) т G К . Эта функция иолиномиально вычислима, позтому любой полиномиальный алгоритм нахождения скрытой подгруппы преобразуется в полиномиальный алгоритм решения задачи о вычислении периода. [c.103]

И ещё одно замечание по поводу обозначений мы использовали обозначение Р и для класса полиномиально вычислимых функций, и для класса полиномиально разрешимых предикатов теперь поступим апа-логичио, используя обозиачепия Р, NP и т.п. для классов частично определённых функций. [c.106]

Р, естественно, обозначает класс полипомиальпо вычислимых частично определённых функций. Приведём модифицированное определение класса NP. [c.106]

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

Если для функции Лх) имеется машина, реализующая ее, то говорят, чтоДх) вычислима по Тьюрингу. [c.27]

Теорема Геделя. Существуют математически корректно определенные функции, которые не являются вычислимыми. Другими словами, существуют алгоритмически неразрешимые проблемы. [c.29]

Справочник химика 21

Химия и химическая технология