Являются ли две функции равными?

[изменить]

Общий вопрос кажется невероятно трудным для решения. Вот значительно ограниченная версия этого вопроса.

Как определить равенство функций?

скажем, что

function f() {
    // black box code.
}

function g() {
    // black box code.
}

Мы берем математическое определение функции. Итак,

if for all x in domain, f(x) === g(x) then f === g

Как мы обрабатываем домены?
Как мы можем иначе определить, если f === g

Проверки по исходному коду глупы, потому что

function f(i) {
     return i % 2;
}

function g(i) {
     var returnVal = i % 2;
     return returnVal;
}

Явно равны. Это тривиальные примеры, но вы можете себе представить, что более сложные функции равны, но не равны источнику.

Вы можете предположить, что f и g не имеют побочных эффектов, о которых мы заботимся.

[изменить]

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

Нет смысла спрашивать, равны ли две функции, не определяя где-то их домен.

Чтобы просто решить проблему, мы можем предположить, что домен является множеством всех целых чисел или подмножеством этого, поэтому нам нужна функция:

function equal (f, g, domain) {

}

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

Вы можете предположить, что f и g halt!

Снова @Pointy указывает хороший пример недетерминированных функций

Что делать, если мы ограничиваем f и g детерминированными.

Ответ 1

Это невозможно согласно Теорема риса:

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

Если вы ограничиваете область функций конечными, вы можете тривиально проверить, если ∀x: f (x) = g (x), используя грубую силу, но это невозможно в бесконечной области.

Ответ 2

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

Это связано с проблемой, которую вы пытаетесь решить, эквивалентной Проблема с остановкой. ^{(источник, страница 4)}

Конечно, вы можете сделать эвристику, чтобы сделать это, но всегда бывают случаи, когда они не смогут ее определить.

Предполагая, что вы ограничиваете его до остановки функций в ограниченном домене, все же не так просто определить быстро. Если предположить, что вход лежит в {1,..., n}, а вывод лежит в {1,..., m}, существуют m ⁿ возможные функции (для каждого входа есть n возможных выходов). Если вы пробуете k точек, вы сузите их и сделаете вероятность того, что они будут больше, но есть еще m ^(n-k) различные функции, которые он может быть. Таким образом, вы можете определить, насколько вероятно, что они равны достаточно быстро, но, чтобы быть уверенным, вам нужно будет проверить все n возможных входных значений.

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

Кроме того, если область не является конечной, Теорема Райса предотвращает существование такого алгоритма.

Ответ 3

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

function a(n) {
  var today = new Date();
  if (today.getFullYear() === 2012 && today.getMonth() === 1 && today.getDate() === 3)
    return 0;
  return n * n;
}

Эта функция выглядит очень похожей на

function b(n) { return n * n; }

За исключением 3 февраля 2012 года, когда он будет выглядеть так:

function c(n) { return 0; }

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

edit — Я просто подумал о чем-то: что, если ваши две функции возвращают функции? Теперь, чтобы определить, есть ли f == g, вам сначала нужно выяснить, равны ли функции, возвращаемые f (n) для всех n, функциям, возвращаемым g (n) для всех n. Хм...

Ответ 4

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

Ответ 5

Системы проверки достоверности, такие как Coq и Agda может выполнять то, что вы ищете.