I studied some of these things, so I hope that I get the following right ...
As nm mentions that the fact that Haskell is printed is of great importance to this issue; of the type, restrict which expressions can be formed, and, in particular, the basic type systems for lambda calculus prohibit self-application, which ultimately gives you a complete language without Turing. Turing completeness is added over the base system as an additional function for the language (either the fix :: (a -> a) -> a operator, or recursive types).
This does not mean that you cannot implement this at all in Haskell, but rather that such an implementation will not have only one statement.
Approach # 1: implement the second sample combinational logic base here and add fix :
iota' :: ((t1 -> t2 -> t1) -> ((t5 -> t4 -> t3) -> (t5 -> t4) -> t5 -> t3) -> (t6 -> t7 -> t6) -> t) -> t iota' x = xksk where kxy = x sxyz = xz (yz) fix :: (a -> a) -> a fix f = let result = f result in result
Now you can write any program in terms of iota' and fix . The explanation of how this works is a bit related. ( EDIT: note that this iota' does not match the λx.x SK in the original question, it is λx.x KSK , which is also the end of Turing. In this case, the iota' programs will be different from the iota programs. I tried defining iota = λx.x SK in Haskell, it's typechecks, but when you try k = iota (iota (iota iota)) and s = iota (iota (iota (iota iota))) you get type errors.)
Approach # 2: Untyped notations for lambda calculus can be built into Haskell using this recursive type:
newtype D = In { out :: D -> D }
D is basically a type whose elements are functions from D to D We have In :: (D -> D) -> D to convert the function D -> D to regular D and out :: D -> (D -> D) to do the opposite. So, if we have x :: D , we can apply it ourselves by doing out xx :: D
Give it, now we can write:
iota :: D iota = In $ \x -> out (out xs) k where k = In $ \x -> In $ \y -> x s = In $ \x -> In $ \y -> In $ \z -> out (out xz) (out yz)
This requires some “noise” from In and out ; Haskell still forbids you to apply D to D , but we can use In and out to get around this. In fact, you cannot use anything with values of type D , but you can create a useful type around the same template.
EDIT: iota is basically λx.x SK , where K = λx.λy.x and S = λx.λy.λz.xz (yz) . Ie, iota accepts a function with two arguments and applies it to S and K; therefore, passing a function that returns its first argument, you get S, and passing a function that returns your second argument, you get K. Therefore, if you can write "return first argument" and "return second argument" with iota, you can write S and K with iota. But S and K are enough to get Turing completeness , so you also get Turing completeness in the transaction. It turns out that you can write the necessary selector functions using iota, so iota is enough to complete Turing.
Thus, it reduces the problem of understanding iota for understanding SK calculus.