Combinatory logic (CL for short) is a universal model of computation.
Terms in the language of CL are built out of variables x, y, . . ., constants
S and K, and applications (M N). More precisely, terms are generated by
the grammar
M,N ::= x | S | K | (M N)
The standard notational conventions are used to avoid brackets: Applications associate to the left, and we do not write the outermost brackets. For
instance, we write Kxy for the term ((K x) y).
There are two computation rules in combinatory logic:
Kxy → x
Sxyz → x z (y z)
a) Using the rules above, there is a sequence of reduction steps
SKKx →∗ x
Show all the reduction steps in this sequence.
b) The term SKK can be seen as the implementation of the identity
function in this system since, for any argument x, the term SKKx
evaluates to x.
Show that SKM, where M is an arbitrary term, also defines the identity function.
c) Consider the system of combinatory logic without the second computation rule (that is, only the rule Kxy → x may be used). We call this
weaker system CL−.
We call CL+ the system of combinatory logic with an additional constant I and rule Ix → x.
Indicate whether each of the following statements is true or false and
why.
i. In CL−, all the reduction sequences are finite.
ii. The system CL+ has the same computational power as the system
CL.
iii. The system CL− is Turing complete.