Trouver l'équivalence de deux fonctions est-il indécidable?
Est-il impossible de savoir si deux fonctions sont équivalentes? Par exemple, un compilateur veut déterminer si deux fonctions que le développeur a écrites effectuent la même opération, quelles méthodes peut-il utiliser pour comprendre celle-ci? Ou peut-on faire quoi pour découvrir que deux TMs sont identiques? Est-il un moyen de normaliser les machines?
Edit: si le cas général est indécidable, combien d'Informations devez-vous avoir avant de pouvoir dire correctement que deux fonctions sont équivalent?
9 réponses
Donnée une fonction arbitraire, f, nous définissons une fonction , f' qui renvoie 1 sur input n si f s'arrête sur input n. Maintenant, pour un certain nombre x, nous définissons une fonction de g, qui, sur l'entrée n, renvoie 1 if n = x, et sinon appelle f'(n).
Si l'équivalence fonctionnelle ont été decidable, puis décider si g est identique à , f' décide f s'arrête sur entrée x. Cela résoudrait le problème D'arrêt . Cette discussion est liée au théorème de Rice .
Conclusion: l'équivalence fonctionnelle est indécidable.
Il y a une discussion en cours ci-dessous sur la validité de cette preuve. Alors laissez-moi élaborer sur ce que fait la preuve, et donner un exemple de code en Python.
-
La preuve crée une fonction , f', qui sur input n commence à calculer f(n). Lorsque ce calcul se termine, f ' renvoie 1. Ainsi, f'(n) = 1 ssi f s'arrête sur input n, et , f' ne pas s'arrêter sur les n ssi f ne l'est pas. Python:
def create_f_prime(f): def f_prime(n): f(n) return 1 return f_prime -
Ensuite, nous créons une fonction g, qui prend n comme entrée, et la compare à une valeur x. Si n = x , alors g (n) = g (x) = 1, sinon 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 -
Maintenant, l'astuce est, que pour tous n != x, nous avons que g(n) = f'(n). De plus, nous savons que g (x) = 1 . Donc, si g = f', puis f'(x) = 1, et donc f(x) s'arrête. De même, si g != f ' alors nécessairement f'(x) != 1, ce qui signifie que f(x) ne s'arrêtera pas. Donc, de déterminer si les g = f' est équivalent à décider si f s'arrête sur input x. En utilisant une notation légèrement différente pour les deux fonctions ci-dessus, nous pouvons résumez tout cela comme suit:
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...
Je vais aussi jeter une illustration de la preuve dans Haskell (GHC effectue une détection de boucle, et je ne suis pas vraiment sûr si l'utilisation de seq est infaillible dans ce cas, mais de toute façon):
-- 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
Oui, c'est indécidable. C'est une forme du problème d'arrêt .
Notez que je veux dire que c'est indécidable pour le cas général. Tout comme vous pouvez déterminer l'arrêt pour des programmes suffisamment simples, vous pouvez déterminer l'équivalence pour des fonctions suffisamment simples, et il n'est pas inconcevable que cela puisse être utile pour une application. Mais vous ne pouvez pas faire une méthode générale pour déterminer l'équivalence de deux fonctions possibles.
Le cas général est indécidable par le théorème de Rice, comme d'autres l'ont déjà dit (le théorème de Rice dit essentiellement que toute propriété non triviale d'un formalisme complet de Turing est indécidable).
Il existe des cas particuliers où l'équivalence est décidable, l'exemple le plus connu est probablement l'équivalence d'automates à états finis. Si je me souviens bien, l'équivalence des automates pushdown est déjà indécidable en réduisant le problème de correspondance de Post.
Pour prouver que deux les fonctions sont équivalentes dont vous auriez besoin en entrée d'une preuve de l'équivalence dans un certain formalisme, que vous pouvez ensuite vérifier l'exactitude. Les parties essentielles de cette preuve sont les invariants de boucle, car ceux-ci ne peuvent pas être dérivés automatiquement.
Dans le cas général, il est indécidable que deux machines de turing aient toujours la même sortie pour l'entrée identique. Puisque vous ne pouvez même pas décider si un tm s'arrêtera sur l'Entrée, Je ne vois pas comment il devrait être possible de décider si les deux arrêtent et produisent le même résultat...
Cela dépend de ce que vous entendez par "fonction."
Si les fonctions dont vous parlez sont garanties de se terminer-par exemple, parce qu'elles sont écrites dans un langage dans lequel toutes les fonctions se terminent - et fonctionnent sur des domaines finis, c'est "facile" (bien que cela puisse prendre très, très longtemps): deux fonctions sont équivalentes si et seulement si elles ont la même valeur à chaque point de leur domaine partagé.
C'est ce qu'on appelle l'équivalence "extensionnelle" pour la distinguer de l'équivalence syntaxique ou "intentionnelle". Deux fonctions sont extensionally equivalent si elles sont intensionally equivalent, mais l'inverse ne tient pas.
(Toutes les autres personnes ci-dessus notant qu'il est indécidable dans le cas général sont tout à fait correctes, bien sûr, c'est un cas particulier assez rare-et généralement inintéressant dans la pratique -.)
Notez que le problème d'arrêt est décidable pour les automates linéaires délimités. Les ordinateurs réels sont toujours limités, et les programmes pour eux seront toujours en boucle à une configuration précédente après suffisamment d'étapes. Si vous utilisez un ordinateur sans limite (imaginaire) pour suivre les configurations, vous pouvez détecter cette boucle et en tenir compte.
Vous pouvez vérifier dans votre compilateur pour voir si elles sont "exactement" identiques, bien sûr, mais déterminer si elles renvoient des valeurs identiques serait difficile et fastidieux. Vous devrez essentiellement appeler cette méthode et effectuer sa routine sur un nombre infini d'appels possibles et comparer la valeur avec celle de l'autre routine.
Même si vous pouviez faire ce qui précède, vous devrez tenir compte des valeurs globales qui changent dans la fonction, des objets détruits / modifiés dans la fonction qui n'affectent pas le résultat.
Vous ne pouvez vraiment comparer que le code compilé. Alors compilez le code compilé pour refactoriser?
Imaginez le temps d'exécution en essayant de compiler le code avec" ce " compilateur. Vous pourriez passer beaucoup de temps ici à répondre aux questions en disant: "compilation occupée..." :)
Je pense que si vous autorisez les effets secondaires, vous pouvez montrer que le problème peut être transformé en Problème de correspondance Post donc vous ne pouvez pas, en général, montrer si deux fonctions sont même capables d'avoir les mêmes effets secondaires.
Est-il impossible de savoir si deux fonctions sont équivalentes?
Non. Il est possible de savoir que deux fonctions sont équivalentes. Si vous avez des f(x), vous savez f(x) est équivalent à f(x).
Si la question est "il est possible de déterminer si f(x) et g(x) équivaut à f et g étant une fonction quelconque et pour toutes les fonctions g et f", alors la réponse est non.
Cependant, si la question est "un compilateur peut-il déterminer que si f (x) et g (x) sont équivalents à ce qu'ils sont-elles équivalentes?", alors la réponse est oui, si elles sont équivalentes dans les deux sortie et des effets secondaires et l'ordre des effets secondaires. En d'autres termes, si l'un est une transformation de l'autre qui préserve le comportement, alors un compilateur de complexité suffisante devrait être capable de le détecter. Cela signifie également que le compilateur peut transformer une fonction f en une fonction G Plus optimale et équivalente compte tenu d'une définition particulière d'équivalent. Cela devient encore plus amusant si f inclut un comportement indéfini, car alors g peut incluez également un comportement indéfini (mais différent)!