Iota is a Turing tarpit designed by Chris Barker, based in combinatory logic. It uses only two symbols,
i, but not every combination of them is syntactically correct; e.g.
*i*ii is correct but
*iii is not, as opposed to its "sister language" Jot in which every string of symbols is valid.
An Iota program is either an
i, or a
* followed by two Iota (sub-)programs.
Iota execution can be defined as repeating the following rewriting rules, which make use of the auxiliary subprograms
s, and where
x,y,z represent subprograms:
*ix --> **xsk **kxy --> x ***sxyz --> **xz*yz
Alternatively it can be defined by translation to lambda calculus:
i = λx.xsk k = λxy.x s = λxyz.xz(yz)
y are functions denotes the function
(xy). These can be "nested", such that (for example)
i function and the
* operator can actually appear in a program's source code.