Improvisation Under Constraints

Field notes on complexity theory, computation, and aesthetics, written between cities, songs, and photographs.

  • Solomonoff Induction over a Combinatory Logic

    Idea: I want to create a combinatory logic which gives rise to efficient programs that are capable of recognising the a^nb^n language. I want to study if shorter programs (low Kolmogorov complexity) generalise better than longer programs (high Kolmogorov complexity).

    What is a combinatory logic?

    A combinatory logic is a simplified model of computation, an early rival to lambda calculus. In expressiveness, it is equivalent to the lambda calculus, but less human readable, given that it does away with variables and abstraction.

    Formally, it is a set A equipped with operators of signature A^m -> A. That is, we take an ordered tuple of m elements from A and assign an element of A as a result. A famous example is the SKI combinator calculus, where we require S, K and I to satisfy the following relations (I use the @ sign to mean application):

    1. I @ x -> x
    2. K @ x @ y -> x
    3. S @ x @ y @ z -> x @ z @ (y @ z).

    We call this SKI basis Turing complete because we can take any lambda calculus term and find an equivalent element in the SKI combinator calculus. The translation function (i.e., the “compiler”) is also well-defined. This is well known, but I have written about it in a previous post.

    Why would it be interesting to do Solomonoff Induction on combinatory logics?

    Universal AI and Solomonoff Induction are famously hard to implement. Solomonoff Induction when done on Turing Machines is uncomputable, although approximable. However, the goal we set off for ourselves is to recognise the a^nb^n language, which is only context-free (2 levels below Turing Machines in the Chomsky Hierarchy). Would it be possible to first synthesise a combinatory logic that is perhaps less expressive than SKI but still powerful enough to give rise to useful programs that recognise a^nb^n? Perhaps Solomonoff Induction becomes efficient in such a reduced setting?

    Starting point

    So what do we need? In principle, I want to find a program P that when applied to an input I (this input comes from the {a,b}* set) terminates with

    References

    1. https://en.wikipedia.org/wiki/Combinatory_logic
    2. https://en.wikipedia.org/wiki/SKI_combinator_calculus
    3. https://en.wikipedia.org/wiki/Kleene_star