Ist der Satz von smn dasselbe Konzept wie das Curry?

Ich studiere den smn-Satz und das Konzept erinnerte mich an Curry.

Aus dem Wikipedia-Artikel über den Satz von smn :

Der Satz besagt, dass es für eine gegebene Programmiersprache und positive ganze Zahlen m und n einen bestimmten Algorithmus gibt, der den Quellcode eines Programms mit m + n freien Variablen zusammen mit m Werten als Eingabe akzeptiert. Dieser Algorithmus generiert einen Quellcode, der die Werte für die ersten m freien Variablen effektiv ersetzt und den Rest der Variablen frei lässt.

Aus einem Artikel über Curry :

Intuitiv sagt Currying: "Wenn Sie einige Argumente korrigieren, erhalten Sie eine Funktion der verbleibenden Argumente."

Scheint mir die gleiche Idee zu sein. Der einzige Grund, warum ich mir nicht sicher bin, ist, dass die Materialien, auf die ich bei smn gestoßen bin, kein Curry erwähnen (und umgekehrt). Deshalb wollte ich es konsultieren, um sicherzustellen, dass ich es tatsächlich bekomme.

computability Emanek
quelle

Tatsächlich. Einige Berechenbarkeitsnachweise haben einen lambdischen Geschmack. Der smn-Satz erlaubt sehr grob vorzutäuschen, dass Indizes rekursiver Funktionen Lambda-Terme sind, so dass wir mit

das informelle

und behaupten, dass

primitiv rekursiv ist. Sogar der zweite Beweis des Rekursionssatzes (der smn ausnutzt) ist Churchs verdeckter Fixpunktkombinator, der hinter

versteckt ist.

ϕ_{i} (-, -)

$\phi_i(-,-)$

g (x) = # λ y . ϕ_{i} (x, y)

$g(x) = \#\lambda y. \phi_i(x,y)$

g

$g$

s ()

$s()$ Verwendet. Der entscheidende Punkt hierbei ist, dass wir , selbst wenn die Aufzählung

definiert ist, die beispielsweise TMs (oder Java oder ...) auflistet, immer noch so tun können, als hätten wir Lambdas!

ϕ_{i}

$\phi_i$

Chi

Nun, smn gibt eine existenzielle Aussage ab, während die Existenz einer Curry-Funktion den "Compiler" liefert . Aber die Idee ist dieselbe.

Raphael

Antworten:

Ja, es ist das gleiche.

Currying ist ein Konzept aus Kalkül. Es ist eine Transformation zwischen und . Stellen Sie sich dies als "Wenn wir eine Funktion von zwei Argumenten vom Typ und , können wir das erste Argument (vom Typ ) korrigieren und erhalten eine Funktion des verbleibenden Arguments (vom Typ )". Tatsächlich ist diese Transformation ein Isomorphismus. Dies wird mathematisch präzisiert durch mathematische Modelle des (typisierten) Kalküls, die kartesische geschlossene Kategorien sind . $\lambda$ $A \times B \to C$ $A \to (B \to C)$ $A$ $B$ $A$ $B$ $\lambda$

Es gibt eine Kategorie von nummerierten Sätzen. Eine nummerierte Menge ist ein Paar wobei eine Menge ist und eine partielle Surjektion ist, dh eine Abbildung von Zahlen auf , die auch undefiniert sein kann. Wenn dann sagen wir, dass von teilweise berechenbaren Funktionen ist, so dass die Zahl ist, die durch die von codierte teilweise berechenbare Funktion berechnet wird $(A, \nu_A)$ $A$ $\nu_A : \mathbb{N} \to A$ $A$ $\nu_A(n) = x$ $n$ ein Code von . In der Berechenbarkeitstheorie gibt es viele Beispiele. Immer wenn wir Informationen mit einer Nummer codieren, erhalten wir einen nummerierten Satz. Zum Beispiel gibt es eine Standardnummerierung $x$ $\varphi$ $\varphi_n(k)$ $n$ wenn sie auf angewendet wird . (Das Ergebnis ist möglicherweise undefiniert.) $k$

Ein Morphismus nummerierter Mengen ist eine realisierte Abbildung , was bedeutet, dass so dass für alle in der Domäne von $f : (A, \nu_A) \to (B, \nu_B)$ $n \in \mathbb{N}$ $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ $k$ $\nu_A$ . Das sieht kompliziert aus, aber alles, was es sagt, ist, dass $\varphi_n$ tut, um zu codieren, was mit Elementen macht. Es ist die mathematische Art zu sagen, dass "Programm die Funktion implementiert ". $f$ $\phi_n$ $f$

Hier ist die Pointe: Die Kategorie der nummerierten Sätze ist kartesisch geschlossen. Wir können daher den typisierten Kalkül darin interpretieren und fragen, welches Programm die Currying-Operation implementiert. Die Antwort lautet: das vom smn-Theorem gegebene Programm. $\lambda$

Andrej Bauer
quelle

Interessant. Ist diese Kategorie eng mit

scheint einen PER zu induzieren.

P E R (A)

$PER(A)$

ν_{A}

$\nu_A$

Chi

Ja, die beiden Kategorien sind äquivalent, und die dritte äquivalente Version ist die von bescheidenen Mengen (suchen Sie nach "bescheidenen Mengen und Baugruppen").

Andrej Bauer