3 ms·

Related: Iota, Jot and Zot by Chris Barker: https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot http://cleare.st/code/iota-j

Related: Iota, Jot and Zot by Chris Barker: https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot http://cleare.st/code/iota-jot-zot http://cleare.st/code/iota-jot-zot > Every combination of 0's and 1's is a syntactically valid Jot program, including the null program.

tromp 4y ago
While these are very simple universal languages, as is a simple binary language based on S K combinators (see Section 3.2 of [1]), they don't yield the very compact programs that BLC does. [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
potiuper 4y ago
Iota appears to be the same as the "X" combinator as found by Jeroen Fokker: The Systematic Construction of a One-Combinator Basis (1989) that amounts to concatenating/applying (material) implication's reduction & distributivity axioms ("S" & "K") in addition to first binding another variable "x", which is "f" in the Iota definition. Shorter than "x" locally complete & consistent (indecisive) single implication axioms exist as one found by Meredith and listed by the now deceased Dolph Ulrich: https://web.ics.purdue.edu/~dulrich/C-pure-intuitionism-page.htm https://web.ics.purdue.edu/~dulrich/C-pure-intuitionism-page... See also: https://math.stackexchange.com/questions/153163/what-is-the-shortest-function-of-lambda-calculus-that-generates-all-functions-of https://math.stackexchange.com/questions/153163/what-is-the-... The shortest single implication axiom appears to be an open question (though translating to implication the McCune/Fitelson/Wos/Wolfram shortest 6 NAND axiom work https://en.wikipedia.org/wiki/Minimal_axioms_for_Boolean_algebra https://en.wikipedia.org/wiki/Minimal_axioms_for_Boolean_alg... seems to be a proof for 3 variables) along with if distributivity is the shortest local completeness (weakening) axiom (see Robbins axiom & associativity & commutativity 3-basis) in addition to having to analyze Meredith's & others on Ulrich's list for self-interpreter lengths. But, a self-interpreter seems unlikely to be shorter compared to lambda calculus given the pattern of decreasing self-interpreter length with increasing complexity of the underlying axiom system.
- deleted 4y ago
  [deleted]

tromp 4y ago

While these are very simple universal languages, as is a simple binary language based on S K combinators (see Section 3.2 of [1]), they don't yield the very compact programs that BLC does. [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf

potiuper 4y ago

Iota appears to be the same as the "X" combinator as found by Jeroen Fokker: The Systematic Construction of a One-Combinator Basis (1989) that amounts to concatenating/applying (material) implication's reduction & distributivity axioms ("S" & "K") in addition to first binding another variable "x", which is "f" in the Iota definition. Shorter than "x" locally complete & consistent (indecisive) single implication axioms exist as one found by Meredith and listed by the now deceased Dolph Ulrich: https://web.ics.purdue.edu/~dulrich/C-pure-intuitionism-page.htm https://web.ics.purdue.edu/~dulrich/C-pure-intuitionism-page... See also: https://math.stackexchange.com/questions/153163/what-is-the-shortest-function-of-lambda-calculus-that-generates-all-functions-of https://math.stackexchange.com/questions/153163/what-is-the-... The shortest single implication axiom appears to be an open question (though translating to implication the McCune/Fitelson/Wos/Wolfram shortest 6 NAND axiom work https://en.wikipedia.org/wiki/Minimal_axioms_for_Boolean_algebra https://en.wikipedia.org/wiki/Minimal_axioms_for_Boolean_alg... seems to be a proof for 3 variables) along with if distributivity is the shortest local completeness (weakening) axiom (see Robbins axiom & associativity & commutativity 3-basis) in addition to having to analyze Meredith's & others on Ulrich's list for self-interpreter lengths. But, a self-interpreter seems unlikely to be shorter compared to lambda calculus given the pattern of decreasing self-interpreter length with increasing complexity of the underlying axiom system.

deleted 4y ago
[deleted]