문제

Specifically, if I defined a new $K_2$ as $$K_2 = \lambda x. (\lambda y. y)$$ instead of $$K = \lambda x. (\lambda y. x)$$ would the $\{S, K_2,I\}$-calculus be a compete basis?

My guess is "no," just because I can't seem to be able to construct the regular K combinator from the $S$, $I$, and $K_2$ combinators, but I don't have an algorithm to follow, nor do I have good intuition about making things out of these combinators.

It seems like you can define $$K_2 = K I$$ with the regular $\{S, K, (I)\}$-calculus, but I couldn't really work backwards from that to get a derivation of $K$ in terms of $K_2$ and the rest.

My attempt at a proof that it was not functionally complete essentially attempted to exhaustively construct every function attainable from these combinators in order to show that you reach a dead end (a function you've seen before) no matter what combinators you use. I realize that this isn't necessarily going to be true of functionally incomplete sets of combinators (e.g. the $K$ combinator on its own will never dead end when applied to itself), but this was my best thought. I was always able to use the $S$ combinator to sneak out of what I thought was finally a dead end, so I'm no longer so sure of the feasibility of this approach.

I asked this question on StackOverflow but was encouraged to post it here. I received a few comments on that post, but I'm not sure I understood them right.

Bonus: if it isn't a complete basis, is the resulting language nonetheless Turing-complete?

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top