Kombinatoren für die primitiven rekursiven Funktionen

19

Es ist bekannt, dass die S- und K-Kombinatoren Turing Complete sind. Gibt es Kombinatoren, die ausreichen, um (nur) die primitiven rekursiven Funktionen zu liefern?

NietzscheanAI
quelle
1
Ist es das was du fragst? mathoverflow.net/questions/48006/…
Andrej Bauer

Antworten:

17

Ja, aber Sie müssen typisierte Kombinatoren berücksichtigen. Das heißt, Sie müssen und K die folgenden Typschemata geben: K : A B A S : ( A B C ) ( A B ) ( A C ) wobei A , B und C sind Metavariablen, die bei jeder Verwendung zu einem beliebigen konkreten Typ instanziiert werden können.SK

K:ABAS:(ABC)(AB)(AC)
A,BC

Dann wollen Sie den Typ hinzufügen der natürlichen Zahlen auf die Sprache der Typen und fügen Sie die folgenden combinators: z : N s u c c : NN i t e r : N( NN ) NNN

z:Nsucc:NNiter:N(NN)NN

Die Gleichheitsregeln für die Zusätze sind:

iterifz=iiterif(succe)=f(iterife)

iter:A(AA)NA
iter

iter

pred=λk.iter(z,z)(λ(n,n).(succn,n))kpred=λk.snd(predk)

NN×N

Neel Krishnaswami
quelle
Das ist also weniger als Turing-complete aufgrund der Beschränkung auf typisierte Kombinatoren? Können die Typvariablen (rekursiv) Funktionen über Typvariablen bezeichnen (z. B. A = D -> E für einige Typen D und E)?
NietzscheanAI
2
SK
Neel, danke. Würde ich zu Recht annehmen, dass es möglich ist, z, succ und iter in Bezug auf S und K über die Zahlencodierung der Kirche darzustellen?
NietzscheanAI
00(succx)x
@Xoff: Die Vorgängerfunktion hat eine bekannte lineare Zeitdefinition in Bezug auf iter. Dies könnte Gegenstand einer Frage auf cs.stackexchange.com sein ...
cody