Действительно ли открытие является эквивалентностью двух неразрешимых функций?
Едва ли - единственная вещь, которую Вы могли реалистично сделать, дают совет на сайте; возможно, перед их первым разом, регистрируясь, Вы могли показать им форму с информацией, указывающей, что не рекомендуется, чтобы они позволили браузеру хранить пароль.
Тогда пользователь сразу последует совету, запишет пароль на постэтом, отмечают и записывают на ленту его к их монитору.
8 ответов
Для произвольной функции f мы определяем функцию f ', которая возвращает 1 на входе n , если f останавливается на входе n . Теперь для некоторого числа x мы определяем функцию g , которая на входе n возвращает 1 , если n = x , а в противном случае вызывает f '(n).
Если функциональная эквивалентность разрешима, то решение о том, идентично ли g f' , определяет, является ли f останавливается на входе x . Это решит проблему остановки . С этим обсуждением связана теорема Райса .
Заключение: функциональная эквивалентность неразрешима.
Ниже будет обсуждаться справедливость этого доказательства. Итак, позвольте мне подробнее рассказать о том, что делает доказательство, и приведу пример кода на Python.
Доказательство создает функцию f ', которая на входе n начинает вычислять f (n) . Когда это вычисление завершается, f 'возвращает 1. Таким образом, f' (n) = 1 iff f останавливается на входе n , и f » не останавливается на n , если f не останавливается. Python:
def create_f_prime (f): , который на входе n начинает вычислять f (n) . Когда это вычисление завершается, f 'возвращает 1. Таким образом, f' (n) = 1 iff f останавливается на входе n , и f » не останавливается на n , если f не останавливается. Python:def create_f_prime (f): , который на входе n начинает вычислять f (n) . Когда это вычисление завершается, f 'возвращает 1. Таким образом, f' (n) = 1 iff f останавливается на входе n , и f » не останавливается на n , если f не останавливается. Python:def create_f_prime (f): def f_prime (n): f (n) возврат 1 вернуть 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): вернуть 1, если n == x иначе f_prime (n) вернуть гТеперь фокус в том, что для всех 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): определение f_prime (n): f (n); возврат 1 def g (n): вернуть 1, если n == x, иначе f_prime (n) return Equiv (f_prime, g) # Если бы на самом деле существовал только эквивалент ...
Я также добавлю иллюстрацию доказательства в 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
Да, это неразрешимо. Это форма проблемы остановки .
Обратите внимание, что я имею в виду, что она неразрешима для общего случая. Так же, как вы можете определить остановку для достаточно простых программ, вы можете определить эквивалентность для достаточно простых функций, и не исключено, что это может быть полезно для приложения. Но вы не можете создать общий метод для определения эквивалентности любых двух возможных функций.
Общий случай неразрешим с помощью теоремы Райса, как уже говорили другие (теорема Райса по существу утверждает, что любое нетривиальное свойство полного по Тьюрингу формализма неразрешимо).
Существуют частные случаи где эквивалентность разрешима, наиболее известным примером, вероятно, является эквивалентность конечных автоматов. Если я правильно помню, эквивалентность выталкивающих автоматов уже неразрешима путем сведения к проблеме соответствия Поста.
Чтобы доказать, что две заданные функции эквивалентны, вам потребуется в качестве входных данных доказательство эквивалентности в некотором формализме, которое вы затем можете проверить на правильность . Существенной частью этого доказательства являются инварианты петель, так как они не могут быть получены автоматически.
В общем случае непонятно, всегда ли две машины Тьюринга имеют один и тот же вывод для идентичного ввода. Поскольку вы даже не можете решить, остановится ли tm на входе, я не понимаю, как можно решить, будут ли оба остановлены И выводить один и тот же результат ...
Вы можете проверить свой компилятор, чтобы убедиться, что они «в точности» идентичны, но определение того, возвращают ли они одинаковые значения, было бы трудным и трудоемким. Вам нужно будет вызвать этот метод и выполнить его процедуру для бесконечного числа возможных вызовов и сравнить значение со значением из другой процедуры.
Даже если бы вы могли сделать вышеописанное, вам пришлось бы учитывать, какие глобальные значения изменяются внутри функции, какие объекты уничтожаются / изменяются в функции, которые не влияют на результат.
Вы действительно можете сравнить только скомпилированный код. Так скомпилируйте скомпилированный код для рефакторинга?
Представьте себе время выполнения при попытке скомпилировать код с «этим» компилятором. Вы можете потратить МНОГО времени, отвечая на вопросы, например: "занято компиляцией ..." :)
Я думаю, если вы разрешите побочные эффекты, вы сможете показать, что проблема может быть преобразована в проблему с перепиской сообщений , чтобы вы могли » t, как правило, показывают, могут ли две функции иметь одинаковые побочные эффекты.
Невозможно узнать, эквивалентны ли две функции ?
Нет. Можно знать, что две функции эквивалентны. Если у вас есть f (x), вы знаете, что f (x) эквивалентно f (x).
Если вопрос: «можно определить, эквивалентны ли f (x) и g (x) с f и g является любой функцией и для всех функций g и f ", тогда ответ отрицательный.
Однако, если вопрос:" может ли компилятор определить, что если f (x) и g (x) эквивалентны, то они эквивалентны ? ", то ответ будет положительным, если они эквивалентны как по выходным, так и по побочным эффектам и порядку побочных эффектов. Другими словами, если одно является преобразованием другого, которое сохраняет поведение, тогда компилятор достаточной сложности должен уметь его обнаружить. Это также означает, что компилятор может преобразовать функцию f в более оптимальную и эквивалентную функцию g с конкретным определением эквивалента. Будет еще интереснее, если f включает неопределенное поведение, потому что тогда g может также включать неопределенное (но другое) поведение!
Это зависит от того, что вы подразумеваете под «функцией».
Если функции, о которых вы говорите, гарантированно завершают свою работу - например, потому что они написаны на языке, в котором все функции завершаются - и работают в конечных доменах, это «просто» (хотя это может занять очень и очень много времени): две функции эквивалентны тогда и только тогда, когда они имеют одинаковое значение в каждой точке их общего домена.
Это называется «экстенсиональной» эквивалентностью, чтобы отличать ее от синтаксической или «интенсиональной» эквивалентности. Две функции экстенсивно эквивалентны, если они интенсионально эквивалентны, но обратное неверно.
(Все остальные люди, отмечавшие, что это неразрешима в общем случае, конечно, совершенно правы,