User:Blashyrkh/Crazy J

It's just a draft page with lots of TODO markers. It will be moved to global scope when it's finished. At least, when Turing completeness proof is given. If it happens to be non-Turing-complete, I'll delete the page and abandon the work.

Intro

Crazy J, designed and implemented by User:Blashyrkh in late 2025, is a crippled little brother of Lazy K. It resembles the syntax of its older brother (two of them, actually), uses the same IO model (with tiny modification), but based on different set of combinators. Which makes it slightly... different.

Instructions

Crazy J is based on non-complete JI basis:

   I = λ x . x
   J = λ xyzw . xy(xwz)

TODO: implement cyclic tag system to prove Turing completeness.

Syntax

Syntax of Crazy J is more strict than the one of Lazy K: it doesn't allow to mix styles. The whole program must be written either in combinator calculus style or in unlambda style, but not both.

         Syntax                                Semantics
   
   Program ::= CCExpr                        CCExpr
             | ULExpr                        ULExpr
             | ""                            (λ x . x)
   
   CCExpr  ::= "I"                           (λ x . x)
             | "J"                           (λ xyzw . xy(xwz))
             | CCExpr1 CCExpr2 ... CCExprN   ((CCExpr1 CCExpr2) ... CCExprN)
             | "(" CCExpr ")"                CCExpr
   
   ULExpr  ::= "i"                           (λ x . x)
             | "j"                           (λ xyzw . xy(xwz))
             | "`" ULExpr1 ULExpr2           (ULExpr1 ULExpr2)

Whitespace is ignored. The rest of a string starting from # until the end of line is a comment and is ignored too.

Obviously, Iota and Jot styles are not applicable to Crazy J since it must remain non-complete to justify its existence.

IO model

Almost exactly as of Lazy K. To be precise:

• Input is Church list of Church numerals where each element represents single byte of input stream. Contrary to Lazy K, ASCII character 0 is represented as Church numeral 1, ASCII character 1 - as Church numeral 2, and so on. The input stream is terminated with Church value 257 infinitely repeated.
• The program is called as a function with the input list passed as a parameter.
• Result of program evaluation must be a Church list of Church numerals. First value greater than or equal to 257 marks the end of output. This value minus 257 is the program's exit code. Output list is never examined beyond EOF, and it's not just implementation detail as of Lazy K. It's essential part of Crazy J specification.
• Input is as lazy as possible: next byte is read from standard input only when it's needed to apply it to an argument.

Church numeral 0 is impossible in JI basis, and therefore all input codes are incremented on input and decremented back before output.

Lack of K combinator

Whereas Lazy K's motto is "there's more than one way to do it", Crazy J's motto is "there's no way to do it, but we do it anyway."

To be precise:

• No constant function (known as "K combinator")
• No Church booleans
• No Church zero
• No Scott numerals
• No familiar list access primitives like car, cdr and nth
• You'll have to find JI representation of your favorite combinators (but we can help you here: we bruteforced several common ones)

Some common combinators in JI basis

We performed an exhaustive computer search for expressions of common combinators in JI basis. The table will be appended by new findings since the search is still on.

Linear combinators

Combinator name	LC expression	Bruteforced Crazy J expression
T	λ x y . y x	``jii
Q1	λ x y z . x (z y)	`ji
R	λ x y z . y z x	`j``jii
Q4	λ x y z . z (y x)	``ji``jii
Q3	λ x y z . z (x y)	``j``ji``jiii
Q2	λ x y z . y (z x)	```j``jii`ji`j``jii
F	λ x y z . z y x	```j``jiii`j`j``jii
C	λ x y z . x z y	```j``jii`j``jii`j``jii
Q	λ x y z . y (x z)	```j`j`j``jii```jiii`j`ji
B	λ x y z . x (y z)	```j``jii``ji``jii`j`j``jii
V	λ x y z . z x y	```j``j```jii`j`j``jii``jiiij
F*	λ x y z w . x w z y	```j``jii`j`j``jii`j``jii
V*	λ x y z w . x z y w	```j``jii`j``jii````jiji`ji
C*	λ x y z w . x y w z	```j`j``jii`j``jii``ji`j``jii
G	λ x y z w . x w (y z)	```j``jii``ji`j``jii`j`j``jii
B1	λ x y z w . x (y z w)	````j```jj``j```jiiii`j``jiiiij
D = B'	λ x y z w . x y (z w)	```j`j``jii``ji``jii``ji`j`j``jii
R*	λ x y z w . x z w y	```j`j`j``jiii```j``j```jiiij`ji`jj
C'	λ x y z w . x (y w) z	````````jj```jii`j`j`j`j``jiijiiii`jj

Duplicative combinators

Combinator name or expression	LC expression	Bruteforced Crazy J expression	Notes

TODO: C(BJT)T, BC(C(BJT)T), W, W', M, L, O, XXX, U, M2

Special

Combinator name or expression	LC expression	Bruteforced Crazy J expression	Notes

TODO: Church numerals 1, 2, 3, increments, Y comb.

Abstraction elimination rules

We worked out the following rules of abstraction elimination:

Rule 1

   λ x . Fx = F (if x is not used in F)

Rule 2

   λ x . F(x)G = JTG(λ x . F(x))  (T = λxy.yx = JII, F(x) is a function of x, G is not)

Rule 3

   λ x . FG(x) = JT(JIF)(JT)(λ x . G(x))  (T = JII, G(x) is a function of x, F is not)

Rule 4

   λ x . F(x)G(x) = JTT(JT(λ x . G(x))(JT(λ x . F(x))(JTT(JIJ))))  (T = JII, F(x) and G(x) are both functions of x)

TODO: probably, it's not correct to put equality sign in the formulas. Tromp uses ≡ sign in his paper, maybe I should too.

TODO: make sure I made no mistakes with brackets in the last formula

Examples

Simplest example - program which ignores its input and does nothing more

TODO: it shows the trick. Give more tricks here. Maybe, give only programs here and move explanation to separate pages.

Links

TODO: push my interpreter (written in C) to github, give link here