Iota and Jot (nonfiction)

In formal language theory and computer science, Iota and Jot (from Greek iota ι, Hebrew yodh י, the smallest letters in those two alphabets) are languages, extremely minimalist formal systems, designed to be even simpler than other more popular alternatives, such as the lambda calculus and SKI combinator calculus. Thus, they can also be considered minimalist computer programming languages, or Turing tarpits, esoteric programming languages designed to be as small as possible but still Turing-complete. Both systems use only two symbols and involve only two operations. Both were created by professor of linguistics Chris Barker in 2001. Zot (2002) is a successor to Iota that supports input and output.

Universal iota combinator

Question: How can the iota combinator be universal if its definition includes S and K?

Answer by Mark Gritter:

The reason we say Iota is universal is because any (computable) function can be expressed in terms of just ι. No S or K are necessary to write a function in Iota.

Iota’s denotational semantics are defined in terms of auxiliary programs S and K, but the language itself has only the symbol ι (and parentheses, or some other tree structure such as the star notation given here: Iota - Esolang) So to interpret what an Iota expression means, you might have to use S and K, but then you’ve crossed into being an interpreter, not a programmer.

https://www.quora.com/How-can-the-iota-combinator-be-universal-if-its-definition-includes-S-and-K

See also

• Binary combinatory logic (nonfiction) - a formulation of combinatory logic using only the symbols 0 and 1. BCL has applications in the theory of program-size complexity (Kolmogorov complexity).
• Combinatory logic (nonfiction) - a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions - and to remove any mention of variables - particularly in predicate logic. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.
• Computer science (nonfiction)
• Lambda calculus (nonfiction) - a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing lambda terms and performing reduction operations on them.
• SKI combinator calculus (nonfiction) - a combinatory logic, a computational system that may be perceived as a reduced version of the untyped lambda calculus. It can be thought of as a computer programming language, though it is not convenient for writing software. Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language. It was introduced by Moses Schönfinkel and Haskell Curry. All operations in lambda calculus can be encoded via abstraction elimination into the SKI calculus as binary trees whose leaves are one of the three symbols S, K, and I (called combinators). Although the most formal representation of the objects in this system requires binary trees, they are usually represented, for typesetability, as parenthesized expressions, either with all the subtrees parenthesized, or only the right-side children subtrees parenthesized.
• Turing tarpit (nonfiction) - any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks. The phrase was coined in 1982 by Alan Perlis in the Epigrams on Programming: "54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." In any Turing complete language, it is possible to write any computer program, so in a very rigorous sense nearly all programming languages are equally capable. Showing that theoretical ability is not the same as usefulness in practice, Turing tarpits are characterized by having a simple abstract machine that requires the user to deal with many details in the solution of a problem. See also:

Greenspun's tenth rule (nonfiction), [[Zawinski's law of software envelopment (nonfiction).