Question

Plus précisément, si j'ai défini un nouveau $ K_2 $ comme$$ k_2 = lambda x. ( lambda y. y) $$à la place de$$ k = lambda x. ( lambda y. x) $$le serait le $ {S, k_2, i } $-Calculus être une base de compétition?

Je suppose que c'est "non", juste parce que je n'arrive pas à pouvoir construire le K Combinator régulier du $ S $, $ I $, et $ K_2 $ Combinateurs, mais je n'ai pas d'algorithme à suivre, et je n'ai pas non plus une bonne intuition à faire des choses à partir de ces combinateurs.

Il semble que vous puissiez définir$$ k_2 = ki $$avec le régulier $ {S, k, (i) } $-Calculus, mais je ne pouvais pas vraiment travailler à l'envers pour obtenir une dérivation de $ K $ sur le plan de $ K_2 $ et le reste.

Ma tentative de preuve qu'il n'a pas été complète qui a essentiellement tenté de construire de manière exhaustive toutes les fonctions réalisables de ces combinateurs afin de montrer que vous atteignez une impasse (une fonction que vous avez vue auparavant), quels que soient les combinateurs que vous utilisez. Je me rends compte que cela ne sera pas nécessairement vrai pour les ensembles de combinateurs fonctionnellement incomplets (par exemple, $ K $ Le combinateur à lui seul ne sera jamais impliqué lorsqu'il est appliqué à lui-même), mais c'était ma meilleure pensée. J'ai toujours pu utiliser le $ S $ Combinator pour me faufiler de ce que je pensais enfin une impasse, donc je ne suis plus sûr de la faisabilité de cette approche.

J'ai posé cette question sur Stackoverflow mais a été encouragé à le publier ici. J'ai reçu quelques commentaires sur ce post, mais je ne suis pas sûr de les comprendre correctement.

Bonus: s'il n'est pas une base complète, la langue résultante est-elle néanmoins Turing-Complete?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top