Iota and Jot
Encyclopedia
Iota and its successor Jot (from Greek
Greek language
Greek is an independent branch of the Indo-European family of languages. Native to the southern Balkans, it has the longest documented history of any Indo-European language, spanning 34 centuries of written records. Its writing system has been the Greek alphabet for the majority of its history;...

 iota
Iota
Iota is the ninth letter of the Greek alphabet. In the system of Greek numerals it has a value of 10. It was derived from the Phoenician letter Yodh . Letters that arose from this letter include the Roman I and J and the Cyrillic І , Yi , Je , and iotified letters .Iota represents...

, Hebrew yodh
Yodh
Yodh is the tenth letter of many Semitic alphabets, including Phoenician, Aramaic, Hebrew Yud , Syriac and Arabic...

, the smallest letters in those two alphabets) are Turing tarpit
Turing tarpit
A Turing tarpit is any programming language or computer interface that allows for a great deal of flexibility in function but is difficult to learn and use because it offers little or no support for common tasks...

s, esoteric programming language
Esoteric programming language
An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...

s that are designed to be as small as possible but still Turing-complete. Each uses two symbols and involves two operations, with simple denotational semantics defined in terms of lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

. Zot is a continuized version of Iota that includes input and output.

Iota's universal combinator is the lambda term
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

 . Then one can recover the usual SKI basis combinators as follows: .

Because of its minimalism, it has influenced research concerning Chaitin's constant
Chaitin's constant
In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly constructed program will halt...

.

See also

  • Lambda calculus
    Lambda calculus
    In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

  • Combinatory logic
    Combinatory logic
    Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It 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...

  • Binary combinatory logic
    Binary combinatory logic
    Binary combinatory logic is a formulation of combinatory logic using only the symbols 0 and 1. BCL has applications in the theory of program-size complexity .-Syntax:Backus–Naur form:* ::= 00 | 01 | 1...

  • SKI combinator calculus

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK