Jot

Jot is a Turing tarpit designed by Chris Barker, described as "a better Goedel-numbering". It is based in combinatory logic. Every combination of 0's and 1's is a syntactically valid Jot program, including the null program.

Semantics of Jot

[]      ->   I
[F0]    ->   [F]SK
[F1]    ->   λxy.[F](xy)  ->  S(K[F])

(Above, [F] converts the Jot program F into lambda calculus/combinatory logic)

Converting combinatory logic to Jot

{K}     ->   11100
{S}     ->   11111000
{AB}    ->   1{A}{B}

(Above, {X} converts the combinatory logic expression X into Jot)

Note that to make the {AB} rule work, this translation satisfies the stronger property [F{A}] = [F](A).

This proves Jot is Turing-complete.

Related languages

• Iota, Jot's "sister language", described in the same article.
• Zot, Jot with I/O.

External resources

• Jot: a better Goedel-numbering