In
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
theory and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, Iota and Jot (from
Greek
Greek may refer to:
Greece
Anything of, from, or related to Greece, a country in Southern Europe:
*Greeks, an ethnic group.
*Greek language, a branch of the Indo-European language family.
**Proto-Greek language, the assumed last common ancestor ...
iota
Iota (; uppercase: Ι, lowercase: ι; ) is the ninth letter of the Greek alphabet. It was derived from the Phoenician letter Yodh. Letters that arose from this letter include the Latin I and J, the Cyrillic І (І, і), Yi (Ї, ї), and ...
ι,
Hebrew
Hebrew (; ; ) is a Northwest Semitic language of the Afroasiatic language family. Historically, it is one of the spoken languages of the Israelites and their longest-surviving descendants, the Jews and Samaritans. It was largely preserved ...
yodh
Yodh (also spelled jodh, yod, or jod) is the tenth letter of the Semitic abjads, including Phoenician Yōd /𐤉, Hebrew Yōd , Aramaic Yod , Syriac Yōḏ ܝ, and Arabic . Its sound value is in all languages for which it is used; in many l ...
י, the smallest letters in those two alphabets) are languages, extremely minimalist
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A form ...
s, designed to be even simpler than other more popular alternatives, such as the
lambda calculus and
SKI combinator calculus
The SKI combinator calculus is a combinatory logic system and a computational system. 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 o ...
. Thus, they can also be considered minimalist computer
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s, or
Turing tarpit
A Turing tarpit (or Turing tar-pit) is 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 ...
s,
esoteric programming language
An esoteric programming language (sometimes shortened to esolang) is a programming language designed to test the boundaries of computer programming language design, as a proof of concept, as software art, as a hacking interface to another language ...
s designed to be as small as possible but still
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any ...
. Both systems use only two symbols and involve only two operations. Both were created by professor of linguistics
Chris Barker
Christopher Andrew Barker (2 March 1980 – 1 January 2020) was an English professional footballer who played as a defender. He represented Alfreton Town, Barnsley, Cardiff City, Stoke City, Colchester United, Queens Park Rangers, Plymouth Arg ...
in 2001. Zot (2002) is a successor to Iota that supports input and output.
Note that this article uses
Backus-Naur form to describe syntax.
Universal iota
Chris Barker's universal iota combinator has the very simple λf.fSK structure defined here, using
denotational semantics in terms of the
lambda calculus,
From this, one can recover the usual
SKI expressions, thus:
Because of its minimalism, it has influenced research concerning
Chaitin's constant
In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will ...
.
Iota
Iota is the
LL(1)
In computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.
An LL parser is called an ...
language that
prefix orders trees of the aforementioned
Universal iota combinator leafs,
cons
In computer programming, ( or ) is a fundamental function in most dialects of the Lisp programming language. ''constructs'' memory objects which hold two values or pointers to two values. These objects are referred to as (cons) cells, conses, ...
ed by
function application ,
iota = "1" , "0" iota iota
so that for example denotes
, whereas denotes
.
Jot
Jot is the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
consisting of all sequences of 0 and 1,
jot = "" , jot "0" , jot "1"
The semantics is given by translation to SKI expressions.
The empty string denotes
,
denotes
,
where