Iota Language Renders All Combinators as Turing-Complete Trees

@tritlo How does this relate to the tree calculus?

Source and examples:

https://github.com/Tritlo/MicroHs/blob/iota-render/iota-examples/README.md

Every combinator can be rendered as an iota tree. Iota is a programming language.

Defined as iota = 1 | 0 iota iota, where iota = \f.((\a.\b.\c.((ac)(bc)))\d.\e.d).

Iota is turing complete! So you can represent *all computable functions* with iota trees

PL theory is amazing!

@tritlo Beautiful!

@tritlo If you can find the time, I'd find it cool to see what the long reductions from https://dl.acm.org/doi/10.1145/2505341.2505348 would look like.

higher res for printing (by request)

I missed the f!!

should be

iota = \f.((f\a.\b.\c.((ac)(bc)))\d.\e.d).

TL;DR

You can encode numbers as programs and then compile those programs down to just two symbols, S and K. You can further further compile those programs into just one symbol i (iota), and represent it with 0 | 1 iota iota. Then you can render that program as a tree

fixed some issues: +non-minimal I + naive bracketing

much smaller and clearer now!

@jhemann ooo, showing reductions, that’s very interesting

let me cook something up

As you compute you are just applying these transformation rules on S and K and rewritews of S and K (called combinators) and slowly reducing the program into the program representation of true

@yminsky this is a bit simpler than the tree calculus, equivalent to S and K (so lambda calculus). No triage/reflection

@etorreborre the beauty was there all along, this is just making it visible

@tritlo That's interesting, so it's \f.(fSK) which is basically an "open" form of an SK expression. Clever.

@tritlo @VictorTaelin

@tritlo Pretty. Exactly the type of esoteric stuff I enjoyed in uni 🗿

@tritlo Turing complete is essential meaning every logical function can be expressed within a fixed N-bit binary space, as long as N is big enough.

@tritlo @d0rc Вот это реально интересно

@tritlo @TyrantsMuse beyond my maths, in case of interest

@tritlo But why SK(I) as your basis? And why not Jot?