One symbol, Turing-complete.
Iota is the simplest known one-combinator basis: a single rewrite rule from which every computable function follows. The Reducer reads any SKI or Iota expression and rewrites it, step by step, to its normal form.
One tiny symbol — ℩ (iota) — is enough to encode any computer program that has ever been written, or ever could be. Like NAND for hardware, but for computation itself: a single primitive from which the rest is just rearrangement.
Iota is defined by one rule: ℩x = xSK, where S and K are the two famous combinators. From a small nest of iotas — ℩(℩(℩℩)) — you can recover K (the constant function). One layer deeper, ℩(℩(℩(℩℩))), you recover S (the substitution function). And once you have S and K, every computable function follows.
This is a proof that Turing-completeness can be reached with ONE primitive operation. It threads logic, computer science and the philosophy of mind: can thought itself be reduced to a single symbol?
In the 1930s Alonzo Church invented the λ-calculus to study what “computable” really meant. Functions are written as λx.M and applied by substitution. A combinator is a closed λ-term: it has no free variables — everything it needs comes through its arguments. Combinators are pure plumbing. Church and Curry showed that the λ-calculus is exactly as powerful as a Turing machine; combinators give us that power without variables.
A combinator is a λ-term with no free variables. It carries no context, only structure.
Moses Schönfinkel, in a 1924 paper that pre-dated Church, found that two combinators are enough. K x y = x throws its second argument away (the constant function). S x y z = x z (y z) takes three arguments, feeds the third to both of the first two, and applies one result to the other (substitution with sharing). These two rewrite rules together can encode every λ-term, every recursive function, every Turing-machine program.
Drop the second argument; keep the first.
Feed z to both x and y; apply the results.
Before they get tangled up in iotas, K and S are just plain functions. K throws its second argument away. S applies its first two arguments to a shared third. Type any three values; the panel shows you the symbolic result on the right.
Hand K any two values and it keeps the first while dropping the second on the floor.
S takes three arguments and rewrites them as x z (y z): both x and y are applied to the shared input z.
In 2001 the linguist and logician Chris Barker asked: how far can we push this? Schönfinkel needed two combinators. Can one suffice? He defined ℩ ≡ λx. x S K — “apply your argument to S and to K, in that order.” That's the whole language: one symbol, one rule. Parentheses are typography, not extra primitives. And yet, as we'll now see, this single rule contains S and K as derived terms — and therefore everything.
One symbol. One rewrite rule: ι x → x S K. The rest of computation falls out as a corollary.
Take ℩(℩(℩℩)). Each outer iota fires the rule ℩x = xSK: the outermost peels off as (℩(℩ι)) S K, then again, and again. After a few S- and K-reductions the dust settles on the bare combinator K. The leftmost-outermost trace runs about nine steps from start to finish — a short chain, all bookkeeping. From four strokes of one symbol, the constant function falls out.
ι (ι (ι ι)) → (ι (ι ι)) S K — outer ι fires, x = ι (ι ι) → (ι ι) S K S K — and again → ι S K S K S K — and again → S S K K S K S K — now S-reductions take over → S K (K K) S K S K → K S (K K S) K S K → S K S K → K K (S K) → K — only K left
The exact chain depends on the reduction strategy; the full Reducer uses leftmost-outermost and lands on K in a small handful of steps.
Now apply iota to a three-deep nest of iotas: ℩(℩(℩(℩℩))). Each outer iota fires the rule ℩x = xSK and pushes another S K onto the spine. After a handful of reduction steps, the leftover terms cancel against one another through S- and K-reductions, and what stays is the bare combinator S. The whole derivation is a few lines of bookkeeping — but the consequence is that S can be expressed in iotas alone.
ι (ι (ι (ι ι))) → (ι (ι (ι ι))) S K — outermost ι fires → (ι (ι ι)) S K S K — repeat on the next layer → … several S and K reductions later … → S — bare combinator S falls out
Five iotas, no other primitives, and S appears. Plug the same expression into the Reducer and walk every step.
Pick a famous derivation (ι (ι (ι ι)) → K, or ι (ι (ι (ι ι))) → S), or type your own expression. Press Step to apply one reduction; the new term replaces the old. The reducer follows leftmost-outermost order — exactly the strategy the textbooks use.
ι (ι (ι ι))
next → ι (ι ι) S KReduction rule applied at each step: ι x → x S K, then K x y → x and S x y z → x z (y z), leftmost-outermost.
Curry and Feys' Combinatory Logic (1958) is a long book whose central theorem is short: every λ-term can be translated into a term built from S and K alone. Combine that with what we just did — iota produces S and iota produces K — and the chain is complete. Anything a Turing machine, a Python program, or a human mathematician can compute, iota can encode. The price is brutal blow-up in length; the payoff is conceptual. Iota stands behind functional programming, type theory, proof assistants, and every implementation of ML-style languages as the ultimate minimal model.
ι — one symbol, one rule ⇒ S, K — both derivable from ι ⇒ λ-calculus — Curry & Feys, 1958 ⇒ recursive — Kleene, 1936 ⇒ Turing — Church-Turing thesis
The last three arrows are textbook results; the first is Barker's contribution. The composition is the proof that ι alone is Turing-complete.
The Reducer lets you type any SKI or iota expression and watch it rewrite, step by step, to its normal form when one exists. The famous derivations are pre-loaded; the rest is yours to discover.
→ Open the Reducer