Konstruktionsrechnung: Komprimieren Sie den Ausdruck auf seine kleinste Form

11

Ich bin mir bewusst, dass sich der Kalkül der Konstruktionen stark normalisiert, was bedeutet, dass jeder Ausdruck eine Normalität hat, die nicht Beta sein kann, sondern weiter reduziert wird. Tatsächlich ist dies der effizienteste Ausdruck, der denselben Wert wie der ursprüngliche Ausdruck berechnet.

In bestimmten Fällen kann die Normalisierung einen kleinen Ausdruck auf einen großen Ausdruck (in Bezug auf die Größe) reduzieren.

Gibt es eine kleinste Form von Ausdrücken? Ein Formular, das denselben Wert mit der kleinsten Größe berechnet.

Mit anderen Worten, anstelle einer zeiteffizienten Normalform eine platzsparende.

user47376
quelle

Antworten:

8

Es gibt ein bisschen Freiheit in dem, was wir als "den gleichen Wert" betrachten. Lassen Sie mich zeigen, dass es keinen solchen Algorithmus gibt, wenn "der gleiche Wert" "beobachtungsäquivalent" bedeutet. Ich werde ein Fragment des Konstruktionskalküls verwenden, nämlich Gödels System T (einfach Kalkül, natürliche Zahlen und primitive Rekursion), daher gilt das Argument bereits für einen viel schwächeren Kalkül.λ

Bei einer Anzahl , lassen ¯ n das entsprechende Bezugszeichen repräsentiert es, das heißt, n - Anwendungen von s u c c auf 0 . Bei einem Turing-Mahcin M sei M die Zifferncodierung M in einer vernünftigen Weise.nn¯nsucc0MMM

Sagen , dass zwei geschlossene Begriffe sind äquivalent , geschrieben t u , wenn für alle n N , tt,u:natnattunN undstn¯ normalisieren sich beide auf dieselbe Ziffer (sie normalisieren sich auf eine Ziffer, weil wir uns in einem stark normalisierenden Claculus befinden).sn¯

Angenommen, wir hätten einen Algorithmus, der bei jedem geschlossenen Term vom Typ einen minimalen äquivalenten Term berechnet. Dann können wir das Halting-Orakel wie folgt lösen.natnat

Es ist ein Begriff , , so dass für alle n N und alle Turingmaschinen M , S ( M , ¯ n ) normalisiert auf ¯ 1 , wenn T stoppt in n Schritten und es normalisiert auf ¯ 0 sonst. Dies ist bekannt, da die Simulation einer Turingmaschine für eine feste Anzahl von Schritten n primitiv rekursiv ist.S:nat×natnatnNMS(M,n¯)1¯Tn0¯n

Es gibt endlich viele geschlossene Terme die minimale Terme sind, die λ x : n a t entsprechen .Z1,,Zk . Unser Minimierungsalgorithmus gibt einen von ihnen zurück, wenn wir ihm λ x : n a t geben .λx:nat.0 , und es kann sogar der Fall sein, dass λ x : n a t .λx:nat.0 ist in der Tat der einzige solche minimale Term. All dies spielt keine Rolle, das einzige, was zählt, ist, dass es endlich viele minimale Terme gibt, die λ x : n a t entsprechen .λx:nat.0 .λx:nat.0

Betrachten Sie nun bei jeder Maschine den Term u : = λ x : n a t .M Wenn M für immer läuft,normalisiert sich u ¯ n für jedes n auf ¯ 0 und entspricht λ x : n a t .

u:=λx:nat.S(M,x)
Mun¯0¯n . Um zu entscheiden, ob M für immer läuft, geben wir u in unseren Minimierungsalgorithmus ein und prüfen, ob der Algorithmus einen von Z 1 , , Z k zurückgegeben hat . Wenn ja, dannläuft M für immer. Wenn dies nicht der Fall ist, wird es angehalten. (Hinweis: Der Algorithmus muss Z 1 , , Z k nicht selbst berechnen, diese können fest in den Algorithmus codiert werden.)λx:nat.0MuZ1,,ZkMZ1,,Zk

Es wäre schön, ein Argument zu kennen, das mit einem schwächeren Begriff der Äquivalenz funktioniert, zum Beispiel nur mit Reduzierbarkeit.β

Andrej Bauer
quelle
Wie berechnet man Z1, .. Zk?
user47376
Das musst du nicht. Das heißt, der Algorithmus, den ich beschreibe, ist da draußen, und wir wissen nicht genau, was es ist, aber das ist irrelevant. Ich versuche nicht wirklich, den Algorithmus auszuführen, ich brauche nur seine Existenz, um zu zeigen, dass Ihr Algorithmus nicht existiert.
Andrej Bauer
Ja, aber Ihr Argument besagt, dass wir das Stoppproblem lösen können, wenn mein Algorithmus existiert. Um festzustellen, ob eine Turingmaschine M anhält, normalisiert Ihr Algorithmus u und prüft, ob es sich um Z1, .. Zk handelt. Es muss also in der Lage sein, diese aufzulisten, sonst kann es nicht aufhören.
user47376
Z1,,ZkkZkZ[i]
7

(λx:T.C x x) uβC u u
u

In diesem Sinne ist bekannt, wie untypisierte Begriffe auf optimale Weise reduziert werden können, um das Teilen so weit wie möglich zu reduzieren. Dies wird hier erklärt: /programming//a/41737550/2059388 und das relevante Zitat ist J. Lampings Ein Algorithmus zur optimalen Reduzierung des Lambda-Kalküls . Es besteht kaum ein Zweifel, dass der Satz für den untypisierten Kalkül auf den CIC ausgedehnt werden kann.

Eine andere relevante Frage ist die Menge an Typinformationen, die bei der Typkonvertierung gelöscht werden können, oder wie eine effiziente Konvertierung durchgeführt werden kann, die ein aktives Forschungsfeld darstellt, siehe z. B. Mishra-Linger-These .

Cody
quelle
6

Lassen Sie mich auf dem Standpunkt bestehen, der von Codys Antwort berührt wird.

λλλλ

Mf

Mx¯l(|x|)f(x)¯
l(|x|)l(n)=O(nk)kf

λΘ(n)Θ(2n)λλ

λλ

λ

Dieselbe Syntax kann verwendet werden, um zu beweisen, dass die Antwort auf die obige Frage im Gegensatz zur naiven Intuition tatsächlich Ja lautet: Die Anzahl der Schritte ganz links zur Normalform ist ein angemessenes Kostenmaß, selbst wenn die Größe explodiert, weil Es gibt tatsächlich eine andere Möglichkeit, dieselbe Berechnung (unter Verwendung linearer expliziter Substitutionen) darzustellen, bei der:

  1. die Größe explodiert nicht ;
  2. λ

Dies alles wird in Accattolis und Dal Lagos Artikel "Beta-Reduktion ist in der Tat unveränderlich" (LICS 2014 und dann denke ich, dass es eine neuere Journalversion gibt) erklärt.

λ

Damiano Mazza
quelle
Was ich mir vorgestellt habe, ist zum Beispiel ein Begriff, der eine Million Schritte ausführt, um eine Liste mit Millionen Elementen zu generieren. Dies normalisiert sich auf die tatsächliche Liste, die die effizienteste Darstellung dieses Werts darstellt (es ist das tatsächliche Endergebnis, es sind keine weiteren Schritte erforderlich). Aber der Entfaltungsbegriff selbst kann sehr klein sein.
user47376
β
Ja, das ist unmöglich, wie Andrej sagte. Das hat meine Frage beantwortet.
user47376