Функциональное равенство на ограниченных функциях

Question

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

Я бы хотел отключить функцию

function equal(f, g, domain) {

}

f & g - функции остановки, которые принимают один аргумент. Их аргумент - натуральное число. Эти функции будут возвращать логическое значение.

Если домен не пропущен, вы можете считать, что домен по умолчанию принимает все натуральные числа.

Структура domain является наиболее удобной для функции equal.

Другим важным фактом является то, что f & g являются детерминированными. и будет последовательно возвращать тот же логический m для f(n).

Можно предположить, что f и g всегда возвращаются и не выдают никаких исключений или сбоев из-за ошибок, если их ввод находится в пределах domain

Вопрос не зависит от языка и требует реализации функции equal. я не уверен, является ли ТАК подходящим местом для этого больше.

f & g не имеют побочных эффектов. и domain не должно быть конечным.

Answer 1

Это все еще невозможно.

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

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

Answer 2

Я полагаю, что следующее, что вы можете сделать лучше всего без статического анализа исходного кода:

function equal(f, g, domain) {
    var n;
    for (n in domain) {
        if (f(domain[n]) != g(domain[n])) return false;
    }
    return true;
}

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

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

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

Подробнее см. мой ответ на предыдущий вопрос .

Answer 3

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

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