Равны ли две функции?

Question

[Редактировать]

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

---

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

Допустим, у нас есть

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 не имеют побочных эффектов, которые нас интересуют.

---

[Edit]

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

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

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

function equal (f, g, domain) {

}

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

Можно предположить, что f и g остановятся!

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

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

Answer 1

Это невозможно согласно теореме Райса :

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

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

Answer 2

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

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

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

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

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

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

Answer 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 .Хм ...

Answer 4

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

Answer 5

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