Domanda

In particolare, se ho definito un nuovo $ K_2 $ come$$ k_2 = lambda x. ( lambda y. y) $$invece di$$ k = lambda x. ( lambda y. x) $$sarebbe il $ {S, k_2, i } $-Calculus essere una base di competizione?

La mia ipotesi è "no", solo perché non riesco a essere in grado di costruire il normale combinatori K dal $ S $, $ I $, e $ K_2 $ Combinatori, ma non ho un algoritmo da seguire, né ho una buona intuizione nel fare le cose da questi combinatori.

Sembra che tu possa definire$$ k_2 = ki $$con il normale $ {S, k, (i) } $-Calculus, ma non potrei davvero lavorare all'indietro da quello per ottenere una derivazione di $ K $ in termini di $ K_2 $ e il resto.

Il mio tentativo di prove che non è stato funzionalmente completato essenzialmente tentato di costruire esauriente ogni funzione raggiungibile da questi combinatori per dimostrare che raggiungi un vicolo cieco (una funzione che hai visto prima) indipendentemente dagli combinatori. Mi rendo conto che questo non sarà necessariamente vero per set funzionalmente incompleti di combinatori (ad es. $ K $ Combinator da solo non sarà mai senza uscita quando è stato applicato a se stesso), ma questo è stato il mio pensiero migliore. Sono sempre stato in grado di usare il $ S $ Combinator per sgattaiolare fuori da quello che pensavo fosse finalmente un vicolo cieco, quindi non sono più così sicuro della fattibilità di questo approccio.

Ho fatto questa domanda su Stackoverflow Ma è stato incoraggiato a pubblicarlo qui. Ho ricevuto alcuni commenti su quel post, ma non sono sicuro di averli capiti bene.

Bonus: se non è una base completa, il linguaggio risultante è comunque completa?

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top