Iota
From Esolang
Iota is a Turing tarpit designed by Chris Barker. It uses only two symbols, * and i, but not every combination of them is syntactically correct; e.g. *i*ii is correct but *iii is not.
Iota can be defined as follows:
*ix --> **xsk **kxy --> x ***sxyz --> **xz*yz
Or, if you prefer:
i = λx.xsk k = λxy.x s = λxyz.xz(yz)
*xy where x and y are functions denotes the function (xy). These can be "nested", such that (for example) *x*yz denotes x(yz).
Only the i function and the * operator can actually appear in a program's source code.
[edit] See also
- Jot, Iota's "sister language" from the same article
- Binary combinatory logic
- Lambda calculus
