Ist es möglich zu beweisen, dass eine Funktion idempotent ist?

Ist es möglich, statische oder abhängige Typen zu verwenden, um zu beweisen, dass eine Funktion idempotent ist?

Ich habe Google und verschiedene Orte auf StackOverflow / StackExchange nach der Antwort durchsucht, ohne Erfolg. Am ehesten habe ich dieses Gespräch über Idris gefunden: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

Leider geht mir diese Diskussion etwas über den Kopf.

haskell bmaddy
quelle

Ich poste dies nicht als Antwort, weil ich nicht 100% sicher bin, aber ich glaube, dass dies aufgrund des Satzes von Rice unmöglich ist .

Gardenhead

Dies ist eine faszinierende Frage, und meine Intuition zeigt, dass dies in einer eingeschränkten, nicht Turing-vollständigen Sprache möglich sein sollte. Programmierer konzentrieren sich jedoch auf Fragen zum Lebenszyklus der Softwareentwicklung ( Einzelheiten finden Sie in der Hilfe ), während dies eine Frage der Informatik zu sein scheint. Die Website für Informatik könnte besser passen und zu besseren Antworten führen.

Amon

Der Satz von @gardenhead Rice besagt, dass es bei jeder Eigenschaft, die das Verhalten eines Programms haben könnte, manchmal unmöglich ist, zu bestimmen, ob ein Programm diese Eigenschaft hat oder nicht. Es gibt einen großen Unterschied zwischen "das ist manchmal unmöglich" und "das ist unmöglich".

Tanner Swett

Mein letzter Kommentar war ziemlich vage. In jedem Fall sagt der Satz von Rice Folgendes: Es gibt keinen Algorithmus, der alle Funktionen korrekt als idempotent oder nicht idempotent einstuft . Es gibt jedoch immer noch nützliche Algorithmen, die einige Funktionen als idempotent einstufen oder nicht.

Tanner Swett

Das OP wollte beweisen, dass eine Funktion idempotent ist und dass kein Algorithmus Funktionen als idemptotent einstuft oder nicht. Der Hauptunterschied besteht darin, dass ein Beweis von einer Person geschrieben werden kann. Was die Vollständigkeit betrifft, so ist dies in der Tat kein Problem .

Gallais

Antworten:

Für bestimmte Funktionen ist es. Besonders wenn man die Funktion kennt ;-)

Wenn Sie mit Ihrer Frage "Gibt es einen Algorithmus, der automatisch entscheidet, ob eine beliebige Funktion idempotent ist oder nicht" meinen, lautet die Antwort aufgrund der bereits in den Kommentaren erwähnten Theoreme "Nein". Für bestimmte Funktionsklassen kann man jedoch theoretisch sehr leicht entscheiden, ob die Funktion idempotent ist oder nicht. Wenn die Funktion beispielsweise rein ist (dh ohne Nebenwirkungen) und man weiß, dass sie für eine bestimmte Eingabe immer einen endlichen Wert zurückgibt, kann die Idempotenz einfach durch Ausprobieren f(f(x))=f(x)einer möglichen Eingabe bestimmt werden xzur Funktion. Nicht, dass dies sehr effizient wäre, es könnte bis zum Ende des Universums laufen.

Wenn das also nicht die Antwort ist, nach der Sie gesucht haben, schreiben Sie eine bessere Frage. Derzeit ist ziemlich unklar, wonach genau Sie suchen.

Doc Brown
quelle

Danke für die Antwort. Die Fähigkeit, "automatisch zu entscheiden", war genau das, wonach ich gesucht hatte.

bmaddy

Um die Aussage „für bestimmte Funktionen ist es“ zu erweitern : Idempotenz kann für jede Funktion bewiesen werden, die entweder nur eine begrenzte Anzahl von Eingaben akzeptiert (indem alle ausprobiert werden) oder eine Art von Eingabe, die rekursiv definiert ist (wie natürlich) Zahlen oder verknüpfte Listen), was bedeutet, dass Sie nur beweisen müssen, dass die Idempotenz für den (die) Basisfall (e) und den (die) rekursiven Fall (e) wahr ist.

Qqwy