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?
lo.logic
computability
NietzscheanAI
quelle
quelle
Antworten:
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.S K
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 : N → N i t e r : N → ( N → N ) → N → NN
Die Gleichheitsregeln für die Zusätze sind:
quelle
iter
. Dies könnte Gegenstand einer Frage auf cs.stackexchange.com sein ...