Невозможно ли узнать, эквивалентны две функции? Например, автор компилятора хочет определить, выполняют ли две функции, написанные разработчиком, одну и ту же операцию, какие методы он может использовать для вычисления этого? Или можем ли мы сделать, чтобы узнать, что две ТМ идентичны? Есть ли способ нормализовать машины?
Изменить: Если общий случай неразрешим, сколько информации вам нужно, прежде чем вы сможете правильно сказать, что две функции эквивалентны?
Для произвольной функции f мы определяем функцию f ', которая возвращает 1 на входе n, если f останавливается на входе n. Теперь для некоторого числа x определим функцию g, которая на входе n возвращает 1, если n = x, и в противном случае вызывает f '(n).
Если функциональная эквивалентность разрешима, то решение о том, является ли g тождественным f ', решает, останавливается ли f на входе x. Это решило проблему Halting. В связи с этим обсуждением Рисовая теорема.
Заключение: функциональная эквивалентность неразрешима.
Ниже приведено несколько рассуждений о действительности этого доказательства. Поэтому позвольте мне подробно остановиться на том, что делает доказательство, и привести пример кода в Python.
Доказательство создает функцию f ', которая на входе n начинает вычислять f (n). Когда это вычисление завершается, f 'возвращает 1. Таким образом, f' (n) = 1, если f останавливается на входе n, а f 'не останавливается на n, если f не имеет значения. Python:
def create_f_prime(f):
def f_prime(n):
f(n)
return 1
return f_prime
Затем мы создаем функцию g, которая принимает n как входную, и сравнивает ее с некоторым значением x. Если n = x, то g (n) = g (x) = 1, иначе g (n) = f '(n). Python:
def create_g(f_prime, x):
def g(n):
return 1 if n == x else f_prime(n)
return g
Теперь трюк заключается в том, что для всех n!= x мы имеем g (n) = f '(n). Кроме того, мы знаем, что g (x) = 1. Итак, если g = f ', то f' (x) = 1 и, следовательно, f (x) останавливается. Аналогично, если g!= F ', то обязательно f' (x)!= 1, что означает, что f (x) не останавливается. Итак, решая, является ли g = f 'эквивалентным решению о том, что f останавливается на входе x. Используя несколько отличающиеся обозначения для указанных выше двух функций, мы можем суммировать все это следующим образом:
def halts(f, x):
def f_prime(n): f(n); return 1
def g(n): return 1 if n == x else f_prime(n)
return equiv(f_prime, g) # If only equiv would actually exist...
Я также подброшу на иллюстрации доказательства в Haskell (GHC выполняет некоторое обнаружение цикла, и я не уверен, что использование seq является доказательством дурака в этом случае, но в любом случае):
-- Tells whether two functions f and g are equivalent.
equiv :: (Integer -> Integer) -> (Integer -> Integer) -> Bool
equiv f g = undefined -- If only this could be implemented :)
-- Tells whether f halts on input x
halts :: (Integer -> Integer) -> Integer -> Bool
halts f x = equiv f' g
where
f' n = f n `seq` 1
g n = if n == x then 1 else f' n
Да, это неразрешимо. Это форма проблема с остановкой.
Обратите внимание, что я имею в виду, что он неразрешим для общего случая. Так же, как вы можете определить остановку для достаточно простых программ, вы можете определить эквивалентность для достаточно простых функций, и не исключено, что это может быть полезно для приложения. Но вы не можете сделать общий метод для определения эквивалентности любых двух возможных функций.
Общий случай неразрешим по теореме Райса, как уже говорили другие (теорема Риса в сущности говорит о том, что любое нетривиальное свойство формализма Тьюринга является неразрешимым).
Существуют особые случаи, когда эквивалентность разрешима, наиболее известным примером является, вероятно, эквивалентность автоматов конечного состояния. Если я правильно помню, что эквивалентность автоматов отталкивания уже неразрешима путем сокращения до проблемы корреспонденции Post.
Чтобы доказать, что две заданные функции эквивалентны, вам потребуется в качестве доказательства доказательства эквивалентности в каком-то формализме, который вы можете проверить на правильность. Существенными частями этого доказательства являются инварианты цикла, так как они не могут быть получены автоматически.
В общем случае неразрешимо, имеют ли две машины turing всегда один и тот же выход для идентичного ввода. Поскольку вы даже не можете решить, будет ли tm останавливаться на входе, я не вижу, как можно решить, будут ли останавливаться и выводить один и тот же результат...
Это зависит от того, что вы подразумеваете под "функцией".
Если функции, о которых вы говорите, гарантированно завершатся - например, потому что они написаны на языке, на котором все функции завершаются, и работают над конечными доменами, это "легко" (хотя, возможно, очень, очень долгое время): две функции эквивалентны тогда и только тогда, когда они имеют одинаковое значение в каждой точке своего общего домена.
Это называется экстенсиональной эквивалентностью, чтобы отличить ее от синтаксической или "интенсиональной" эквивалентности. Две функции эквивалентны по удвоенности, если они являются наследо- вательно эквивалентными, но обратное не выполняется.
(Все остальные люди, заметив, что они неразрешимы в общем случае, совершенно правильны, конечно, это довольно необычно и обычно неинтересно на практике - особый случай.)
Заметим, что проблема остановки разрешима для линейных ограниченных автоматов. Реальные компьютеры всегда ограничены, и программы для них всегда будут возвращаться к предыдущей конфигурации после достаточно большого количества шагов. Если вы используете неограниченный (мнимый) компьютер для отслеживания конфигураций, вы можете обнаружить этот цикл и принять его во внимание.
Вы можете проверить свой компилятор, чтобы убедиться, что они "точно" идентичны, конечно, но определить, будут ли они возвращать идентичные значения, было бы трудным и трудоемким. Вам придется в основном вызывать этот метод и выполнять свою процедуру по бесконечному числу возможных вызовов и сравнивать значение с тем из другой подпрограммы.
Даже если вы могли бы сделать это, вам нужно будет учитывать, какие глобальные значения изменяются внутри функции, какие объекты уничтожаются/изменяются в функции, которые не влияют на результат.
Вы действительно можете сравнить только скомпилированный код. Итак, скомпилируйте скомпилированный код для рефакторинга?
Представьте себе время выполнения при попытке скомпилировать код с помощью этого "компилятора". Вы могли бы потратить много времени, отвечая на вопросы, говоря: "занят компиляцией...":)
Я думаю, что если вы допустите побочные эффекты, вы можете показать, что проблема может быть изменена в Проблема с корреспонденцией post, чтобы вы не могли, вообще говоря, показывают, что две функции даже способны иметь одинаковые побочные эффекты.
Невозможно ли узнать, эквивалентны две функции?
Нет. Можно знать, что две функции эквивалентны. Если у вас есть f (x), вы знаете, что f (x) эквивалентно f (x).
Если вопрос заключается в "можно определить, являются ли f (x) и g (x) эквивалентными с f, а g - любая функция и для всех функций g и fn, то ответ не равен.
Однако, если вопрос заключается в "может ли компилятор определить, что если f (x) и g (x) эквивалентны, то они эквивалентны?", тогда ответ будет да, если они эквивалентны как выходным, так и побочным эффектам и порядок побочных эффектов. Другими словами, если кто-то является преобразованием другого, сохраняющего поведение, то компилятор достаточной сложности должен иметь возможность его обнаружить. Это также означает, что компилятор может преобразовать функцию f в более оптимальную и эквивалентную функцию g, задав определенное определение эквивалентности. Это становится еще веселее, если f включает в себя поведение undefined, потому что тогда g также может включать поведение undefined (но другое)!