Est-il possible de prouver qu'une fonction est idempotente?

12

Est-il possible d'utiliser des types statiques ou dépendants pour prouver qu'une fonction est idempotente?

J'ai cherché sur Google et à divers endroits sur StackOverflow / StackExchange la réponse sans succès. Le plus proche que j'ai trouvé était cette conversation sur Idris: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

Malheureusement, cette discussion me dépasse un peu.

haskell bmaddy
la source
3
Je ne poste pas cela comme réponse parce que je ne suis pas sûr à 100%, mais je pense que c'est impossible en raison du théorème de Rice .
gardenhead
4
C'est une question fascinante, et mon intuition indique que cela devrait être possible dans un langage restreint et non complet de Turing. Cependant, les programmeurs se concentrent sur les questions concernant le cycle de vie du développement logiciel (voir le centre d'aide pour plus de détails), alors que cela semble être une question informatique. Le site informatique peut être mieux adapté et conduire à de meilleures réponses.
amon
2
Le théorème de @gardenhead Rice stipule que, compte tenu de toute propriété que pourrait avoir le comportement d'un programme, il est parfois impossible de déterminer si un programme possède ou non cette propriété. Il y a une grande différence entre "c'est parfois impossible" et "c'est impossible".
Tanner Swett
2
Mon dernier commentaire était assez vague. En tout cas, voici ce que le théorème de Rice a à dire: il n'y a pas d'algorithme qui classe correctement toutes les fonctions comme étant idempotentes ou non idempotentes. Cependant, il existe encore des algorithmes utiles qui classent certaines fonctions comme étant idempotentes ou non.
Tanner Swett
2
L'OP a demandé de prouver qu'une fonction est idempotente, de ne pas avoir d'algorithme classer les fonctions comme idemptotentes ou non. La principale différence étant qu'une preuve peut être rédigée par une personne. Quant à l'exhaustivité de Turing, ce n'est en effet pas un problème .
gallais

Réponses:

3

Pour certaines fonctions, c'est le cas. Surtout quand vous connaissez la fonction ;-)

Si vous entendez par votre question "existe-t-il un algorithme pour décider automatiquement si une fonction arbitraire est idempotente ou non", la réponse est non, en raison des théorèmes déjà mentionnés dans les commentaires. Cependant, pour des classes spécifiques de fonctions, on peut - en théorie - très facilement décider si la fonction est idempotente ou non. Par exemple, si la fonction est pure (signifie: sans aucun effet secondaire), et que l'on sait qu'elle renvoie toujours une valeur dans un laps de temps fini pour une entrée donnée, alors l'idempotence peut être décidée simplement en essayant si f(f(x))=f(x)pour une entrée possible xà la fonction. Non pas que ce sera très efficace, il pourrait fonctionner jusqu'à la fin de l'univers.

Donc, si ce n'est pas la réponse que vous cherchiez, écrivez une meilleure question, actuellement il est assez difficile de savoir exactement ce que vous recherchez vraiment.

Doc Brown
la source
Merci d'avoir répondu. La capacité de "décider automatiquement" était exactement ce que je recherchais.
bmaddy
2
Pour développer la déclaration `` pour certaines fonctions, c'est '' : l'idempotence peut être prouvée pour toute fonction qui n'accepte qu'une quantité finie d'entrées (en les essayant toutes), ou un type d'entrée défini de manière récursive (comme naturel ou listes liées), ce qui signifie que vous n'avez qu'à prouver que l'idempotence est vraie pour le ou les cas de base et les cas récursifs.
Qqwy